Quanti

Il nuovo algoritmo supera il limite di velocità per la risoluzione di equazioni lineari



<p> Sfruttando la casualità, un nuovo algoritmo raggiunge un modo fondamentalmente nuovo e più veloce di eseguire uno dei calcoli più elementari in matematica e informatica. </p>
<p> Il post <a href= New Algorithm Breaks Il limite di velocità per la risoluzione di equazioni lineari è apparso per la prima volta su Quanta Magazine .

“>

Gli studenti di matematica delle scuole elementari hanno probabilmente familiarità con gli insegnanti che li ammoniscono a non indovinare solo la risposta a un problema. Ma una nuova dimostrazione stabilisce che, in effetti, il giusto tipo di ipotesi a volte è il modo migliore per risolvere sistemi di equazioni lineari, uno dei calcoli fondamentali in matematica.

Di conseguenza, la dimostrazione stabilisce il primo metodo in grado di superare quello che in precedenza era stato un limite rigido sulla rapidità con cui alcuni di questi tipi di problemi possono essere risolti.

"Questo è uno dei problemi fondamentali dell'informatica", ha affermato Mark Giesbrecht dell'Università di Waterloo. "Ora abbiamo la prova che possiamo andare più veloci."

Il nuovo metodo, di Richard Peng e Santosh Vempala del Georgia Institute of Technology, è stato pubblicato online a luglio e presentato a gennaio all'annuale ACM-SIAM Symposium on Discrete Algorithms , dove ha vinto il premio per la migliore carta.

I sistemi lineari coinvolgono due o più equazioni con variabili che specificano i diversi modi in cui le cose si relazionano tra loro. Sono "lineari" perché l'unica potenza ammissibile è esattamente 1 e i grafici delle soluzioni alle equazioni formano piani.

Un esempio comune di sistema lineare, probabilmente familiare anche agli studenti di matematica, riguarda un cortile pieno di polli e maiali. Se sai solo che ci sono 10 teste e 30 piedi, quanti polli ci sono e quanti maiali? Man mano che gli studenti di algebra imparano, c'è una procedura prestabilita per capirlo: scrivi due equazioni algebriche e risolvile insieme.

Ma i sistemi lineari possono fare di più che contare solo polli e maiali. Affiorano in molti contesti pratici, dove la costruzione di un ponte più robusto o di un aereo più furtivo può comportare la risoluzione di sistemi con milioni di equazioni lineari interdipendenti. Più fondamentalmente, i sistemi lineari sono presenti in molti problemi di ottimizzazione di base in informatica che implicano la ricerca dei valori migliori per un insieme di variabili all'interno di un sistema di vincoli. Se riusciamo a risolvere i sistemi lineari più velocemente, allora possiamo risolvere anche quei problemi più velocemente.

"I sistemi lineari sono il cavallo di battaglia del calcolo moderno", ha affermato Vempala.

La nuova dimostrazione trova un modo più rapido per risolvere un'ampia classe di sistemi lineari eludendo una delle principali tecniche tipicamente utilizzate nel processo. Quella tecnica, chiamata moltiplicazione di matrici, in precedenza impostava un limite di velocità rigido sulla rapidità con cui i sistemi lineari potevano essere risolti. È ancora presente nel lavoro, ma in un ruolo complementare. Gli autori lo accoppiano con un nuovo approccio che, in sostanza, è una forma di divinazione addestrata.

"Puoi indovinare la strada per le soluzioni", ha detto Peng. E nessun insegnante sarebbe arrabbiato con te per questo.

Matematica da cortile

Per avere un'idea dei sistemi lineari e di come potresti risolverli, torna nell'aia, ma immagina che ora sia più un serraglio: galline, rinoceronti con 1 corna e capre con 2 corna. Fai un rapido conteggio e stabilisci che ci sono 12 teste, 38 piedi e 10 corna. Riuscite a capire quanti ce ne sono di ogni animale?

Per procedere, assegna una variabile a ciascun animale ( c per i polli, r per i rinoceronti, g per le capre) e scrivi un'equazione per ogni attributo. I numeri, o coefficienti, davanti a ciascuna variabile riflettono la quantità di quell'attributo posseduto da ciascun animale.

c + r + g = 12 teste

2 c + 4 r + 4 g = 38 piedi

0 c + 1 r + 2 g = 10 corna

Ora hai tre equazioni e tre incognite.

Un modo per risolverli è manipolare un'equazione e definire una variabile in termini di altre due. Ad esempio, 0 c + 1 r + 2 g = 10 si trasforma in r = 10 – 2 g . Sostituisci quel valore con r nelle altre due equazioni e continua in questo modo finché non hai definito tutte le variabili in termini di una sola variabile, che puoi quindi risolvere esattamente. Quindi puoi ripetere il processo, sfruttando l'unica variabile per cui hai risolto per risolvere per la successiva.

Ma un altro modo, più sofisticato, di procedere è creare una matrice le cui voci siano i coefficienti delle equazioni. Le tre equazioni si trasformano in questa matrice.

$ latex sinistra $

Successivamente, rappresentiamo il numero imprecisato di polli, rinoceronti e capre con un'altra matrice.

$ latex sinistra $

Infine, rappresentiamo il numero osservato di teste, piedi e corna con una terza matrice.

$ latex sinistra $

Possiamo combinare queste tre matrici in un unico sistema lineare, dove la prima matrice moltiplicata per i valori sconosciuti della seconda matrice è uguale alla terza matrice – a quel punto possiamo usare l'algebra lineare per risolvere la seconda matrice.

$ latex left $ × $ latex left $ = $ latex left $

Sia che tu manipoli le equazioni o prenda il percorso della matrice, finirai per eseguire lo stesso numero totale di passaggi computazionali per risolvere il problema. Quel numero è il cubo del numero di variabili nel sistema ( n 3 ). In questo caso abbiamo tre variabili, quindi sono necessari 3 3 o 27 passaggi di calcolo. Se avessimo quattro animali e quattro equazioni, ci vorrebbero 4 3 o 64 passaggi per risolverli.

Negli ultimi 50 anni i ricercatori hanno trovato modi per eseguire questa procedura in modo più efficiente. Spesso ci sono scorciatoie che possono utilizzare – modi per riutilizzare o combinare operazioni – che consentono loro di risolvere sistemi lineari in meno passaggi.

Nel 1969 Volker Strassen ha ideato un algoritmo per eseguire la moltiplicazione di matrici in soli n 2.81 passi. Da allora matematici e informatici hanno cercato di abbassare ulteriormente l'esponente. Il progresso più recente , fatto lo scorso ottobre da Virginia Vassilevska Williams del Massachusetts Institute of Technology e Josh Alman , ricercatore post-dottorato presso l'Università di Harvard, ha dimostrato che è possibile eseguire la moltiplicazione di matrici in n 2,37286 passi, un miglioramento dell'esponente di 0,00001 su il miglior voto precedente.

Il risultato di tutto ciò è che qualsiasi sistema lineare che si desidera risolvere può essere ridotto a una domanda sulla moltiplicazione di matrici e, per ora, la moltiplicazione di matrici può essere eseguita almeno teoricamente in n 2,37286 passi.

Ma varie caratteristiche tecniche suggeriscono che dovrebbe essere possibile risolvere sistemi lineari più velocemente di così – potenzialmente in n 2 passaggi. Usiamo la moltiplicazione di matrici perché è stato il miglior strumento disponibile, ma ciò non significa che non ci sia uno strumento ancora migliore in attesa di essere scoperto.

"Non c'è motivo per cui questo problema di risoluzione dei sistemi lineari dipenda da miglioramenti nella moltiplicazione di matrici", ha affermato Vempala.

Indovinare soluzioni

Per comprendere lo strumento nuovo e migliorato, è necessario tenere presente un altro metodo consolidato per la risoluzione dei sistemi lineari. È intuitivo, quello che potresti raggiungere quando ti confronti per la prima volta con uno stormo di polli, uno stormo di rinoceronti e un viaggio di capre mescolati insieme: indovina i numeri per ciascuno, inseriscili nelle equazioni, guarda quanto sei lontano e indovina di nuovo.

Questo "approccio iterativo" è spesso utilizzato da ingegneri e scienziati. Funziona bene per molti problemi pratici perché gli esperti in genere non indovinano alla cieca, il che riduce il numero di ipotesi ripetute che devono fare prima di trovare la soluzione.

"Per i problemi di calcolo scientifico del mondo reale, gli esseri umani hanno un'ottima intuizione per quali dovrebbero essere le risposte", ha detto Peng.

I metodi iterativi sono utili in casi specifici in cui l'intuizione può fornire un certo supporto. Sono anche utili più in generale ogni volta che il sistema lineare che stai cercando di risolvere ha un gran numero di variabili i cui coefficienti sono zero.

Questa caratteristica è presente – e utile – nell'esempio del cortile, dove l'attributo più semplice da risolvere sono le corna. Perché? Perché i polli non hanno le corna, il che azzera il termine pollo e riduce un problema che coinvolge tre animali a un problema che coinvolge davvero due. E una volta che hai tolto le corna, puoi usare queste informazioni per risolvere rapidamente i piedi e le teste.

In sistemi lineari più complicati, questo tipo di relazione, in cui non tutti gli attributi appartengono a tutte le variabili, può essere pervasivo. Potresti avere milioni di variabili e milioni di equazioni, ma ogni equazione potrebbe coinvolgere solo un piccolo numero di variabili complessive. Questi tipi di sistemi lineari sono chiamati "sparsi" e riflettono il modo in cui la maggior parte delle variabili assume un valore zero nella maggior parte delle equazioni. Questa è una situazione che si presenta spesso nei sistemi lineari del mondo reale. Ed è uno in cui i metodi iterativi possono battere la moltiplicazione di matrici.

"Funziona solo quando la tua matrice è abbastanza scarsa", ha detto Williams.

Ma prima di questo nuovo lavoro nessuno era riuscito a dimostrare che i metodi iterativi sono sempre più veloci della moltiplicazione di matrici per tutti i sistemi lineari sparsi.

Casualità coordinata

La nuova tecnica di Peng e Vempala impiega una versione migliorata della strategia di indovinare ripetuta: invece di fare una sola ipotesi, il loro algoritmo fa molte ipotesi in parallelo. Questo approccio accelera la ricerca, proprio come troverai una gemma in una foresta più velocemente se hai molte persone che guardano contemporaneamente.

"Il parallelismo è dove avviene la magia", ha detto Giesbrecht.

Può sembrare ovvio che il marshalling di più ipotesi contemporaneamente sia utile, ma far funzionare la strategia non è così semplice. L'efficacia del nuovo algoritmo si basa in gran parte sull'essere intelligenti su come fare le ipotesi iniziali che avviano il processo iterativo e sulla ricerca di modi intelligenti per combinare i frutti delle ipotesi parallele in un'unica risposta finale.

Per tornare all'esempio del cortile, l'algoritmo potrebbe fare tre ipotesi iniziali, in cui ciascuna ipotesi è una matrice 3 per 1 che specifica un numero di polli, rinoceronti e capre. L'algoritmo osservava quanto era lontana ciascuna ipotesi, quindi eseguiva più ipotesi, continuando le discussioni di ipotesi parallele.

Una chiave del successo finale dell'algoritmo è che fa le tre ipotesi iniziali in modo casuale. La casualità potrebbe non sembrare una buona base per indovinare, ma come metodo generico ha i suoi vantaggi, specialmente quando lavori con problemi enormi. Vale a dire, la casualità ti assicura di non finire accidentalmente per orientare la tua ricerca verso una parte del problema, trascurando potenzialmente lo spazio in cui si trova la soluzione effettiva.

"Devo assicurarmi che tutte le mie ipotesi siano sufficientemente casuali in modo da coprire tutte le possibili combinazioni", ha detto Peng. "È questo modo terribile di fare ipotesi che finisce per essere il metodo preferito quando il problema diventa molto grande."

Gran parte del difficile lavoro tecnico nel documento di Peng e Vempala implica la dimostrazione che anche i diversi filoni di ipotesi casuali lavorano insieme, inclusa qualsiasi ipotesi particolare che è in realtà la risposta al problema.

"C'è casualità coordinata", ha detto Vempala.

Ciò significa che le ipotesi casuali non solo tengono conto dei valori esatti delle ipotesi stesse, ma coprono anche tutte le ipotesi potenziali che si trovano tra di loro. È simile nello spirito a come due persone che cercano in una foresta non si limitano a cercare il terreno su cui camminano; coprono anche l'intera linea di vista tra di loro.

"Anche tutto ciò che si trova tra due è coperto", ha detto Vempala.

Questa funzione di ricerca garantisce che l'algoritmo incontrerà la soluzione da qualche parte. Ma da solo non identifica quale sia effettivamente la soluzione. Per farlo – per mettere le mani sulla soluzione – Peng e Vempala devono dimostrare qualcos'altro.

L'algoritmo tiene traccia delle sue ipotesi casuali come voci in una matrice. Trovare la soluzione tra le voci nella matrice diventa una questione di moltiplicazione di matrici, che ovviamente è il blocco stradale che si erano prefissati di aggirare. Ma anche qui sfruttano la casualità che hanno usato per seminare le voci nella matrice.

Poiché le voci nella matrice sono casuali e il coordinamento avviene tra di loro, la matrice stessa finisce con determinate simmetrie. Queste simmetrie consentono scorciatoie di calcolo. Proprio come con qualsiasi oggetto altamente simmetrico, devi solo sapere che aspetto ha una parte di esso per dedurre il tutto.

Di conseguenza, l'algoritmo di Peng e Vempala può trovare la soluzione all'interno della matrice più velocemente di quanto potrebbe in una matrice con lo stesso numero di voci, ma nessuna delle simmetrie utili. Le simmetrie della matrice trasmettono anche un altro importante vantaggio: aiutano a garantire che le ipotesi non crescano mai così grandi da diventare ingombranti dal punto di vista dell'efficienza algoritmica.

"Abbiamo dovuto controllare quanto è grande un numero visualizzato mentre indoviniamo e coordiniamo", ha detto Peng.

Peng e Vempala dimostrano che il loro algoritmo può risolvere qualsiasi sistema lineare sparse in n 2.332 passi. Questo batte l'esponente per il miglior algoritmo per la moltiplicazione di matrici ( n 2,37286 ) di circa quattro centesimi. L'eliminazione della moltiplicazione di matrici non avrà importanza per le applicazioni pratiche in qualsiasi momento presto, ma come prova del concetto, questo leggero miglioramento è un abisso: mostra che c'è un modo completamente migliore di risolvere i sistemi lineari.

"Filosoficamente non sapevamo prima se puoi andare più veloce della moltiplicazione di matrici", ha detto Vempala.

Adesso lo facciamo.

Il post New Algorithm Breaks Speed ​​Limit for Solving Linear Equations è apparso per la prima volta su Quanta Magazine .


Questa è la traduzione automatica di un articolo pubblicato su Quanta Magazine all’URL https://www.quantamagazine.org/new-algorithm-breaks-speed-limit-for-solving-linear-equations-20210308/ in data Mon, 08 Mar 2021 16:04:47 +0000.