Gli informatici sono un gruppo esigente. Per loro, ottenere la risposta giusta a un problema non è sufficiente: l'obiettivo, quasi sempre, è ottenere la risposta nel modo più efficiente possibile.

Prendi l'atto di moltiplicare matrici o matrici di numeri. Nel 1812, il matematico francese Jacques Philippe Marie Binet formulò l’insieme di regole di base che ancora insegniamo agli studenti. Funziona perfettamente, ma altri matematici hanno trovato il modo di semplificare e accelerare il processo. Ora il compito di accelerando il processo La moltiplicazione delle matrici si trova all’intersezione tra matematica e informatica, dove i ricercatori continuano ancora oggi a migliorare il processo, anche se negli ultimi decenni i progressi sono stati piuttosto modesti. Dal 1987, i miglioramenti numerici nella moltiplicazione delle matrici sono stati “piccoli e… estremamente difficili da ottenere”, ha affermato François Le Gall, uno scienziato informatico dell'Università di Nagoya.

Ora, tre ricercatori – Ran Duan e Renfei Zhou della Tsinghua University e Hongxun Wu dell’Università della California, Berkeley – hanno fatto un importante passo avanti nell’affrontare questo annoso problema. Loro nuovi risultati, presentati lo scorso novembre alla conferenza Foundations of Computer Science, derivano da una nuova tecnica inaspettata, ha affermato Le Gall. Sebbene il miglioramento in sé fosse relativamente piccolo, Le Gall lo definì “concettualmente più grande di altri precedenti”.

La tecnica rivela una fonte di potenziali miglioramenti precedentemente sconosciuta e quindi non sfruttata, e ha già dato i suoi frutti: Un secondo documento, pubblicato a gennaio, si basa sul primo per mostrare come la moltiplicazione delle matrici possa essere ulteriormente potenziata.

"Si tratta di un importante passo avanti tecnico", ha detto William Kuszmaul, uno scienziato informatico teorico dell'Università di Harvard. "È il più grande miglioramento nella moltiplicazione delle matrici che abbiamo visto in più di un decennio."

Inserisci la matrice

Può sembrare un problema oscuro, ma la moltiplicazione di matrici è un'operazione computazionale fondamentale. È incorporato in gran parte degli algoritmi che le persone utilizzano ogni giorno per una varietà di compiti, dalla visualizzazione di grafica computerizzata più nitida alla risoluzione di problemi logistici nella teoria delle reti. E come in altre aree del calcolo, la velocità è fondamentale. Anche piccoli miglioramenti potrebbero alla fine portare a notevoli risparmi di tempo, potenza di calcolo e denaro. Ma per ora, i teorici sono principalmente interessati a capire quanto velocemente potrà essere il processo.

Il modo tradizionale di moltiplicare due n-By-n matrici, moltiplicando i numeri di ciascuna riga della prima matrice per i numeri delle colonne della seconda, richiede n³ moltiplicazioni separate. Per le matrici 2 per 2, ciò significa 2³ o 8 moltiplicazioni.

Nel 1969, il matematico Volker Strassen scoprì una procedura più complicata che poteva moltiplicare matrici 2 per 2 in soli sette passaggi moltiplicativi e 18 addizioni. Due anni dopo, l'informatico Shmuel Winograd dimostrò che sette è, in effetti, il minimo assoluto per le matrici 2 per 2.

Strassen ha sfruttato la stessa idea per mostrarlo tutto più grande n-By-n le matrici possono anche essere moltiplicate per meno di n³ passi. Un elemento chiave di questa strategia prevede una procedura chiamata decomposizione, ovvero la scomposizione di una matrice di grandi dimensioni in sottomatrici successivamente più piccole, che potrebbero finire per essere piccole come 2 per 2 o addirittura 1 per 1 (si tratta solo di numeri singoli).

La logica per dividere un array gigante in piccoli pezzi è piuttosto semplice, secondo Virginia Vassilievska Williams, scienziato informatico presso il Massachusetts Institute of Technology e coautore di uno dei nuovi articoli. "È difficile per un essere umano guardare una matrice di grandi dimensioni (diciamo, dell'ordine di 100 per 100) e pensare al miglior algoritmo possibile", ha detto Vassilevska Williams. Anche le matrici 3 per 3 non sono state ancora completamente risolte. “Tuttavia, è possibile utilizzare un algoritmo veloce già sviluppato per matrici piccole per ottenere un algoritmo veloce anche per matrici più grandi”.

La chiave per accelerare, hanno determinato i ricercatori, è ridurre il numero di passaggi di moltiplicazione, abbassando l'esponente n³ (per il metodo standard) il più possibile. Il valore più basso possibile, n², è sostanzialmente il tempo necessario solo per scrivere la risposta. Gli informatici si riferiscono a quell'esponente come omega, ω, con n^ω essendo il minor numero di passaggi possibili necessari per moltiplicare con successo due n-By-n matrici come n diventa molto grande. “Lo scopo di questo lavoro”, ha detto Zhou, che è anche coautore del documento del gennaio 2024, “è vedere quanto ci si può avvicinare a 2 e se in teoria è possibile raggiungerlo”.

Una messa a fuoco laser

Nel 1986, Strassen fece un'altra grande svolta quando lui introdotto quello che viene chiamato il metodo laser per la moltiplicazione delle matrici. Strassen lo usò per stabilire un valore superiore per omega di 2.48. Anche se il metodo rappresenta solo un passo nelle moltiplicazioni di matrici di grandi dimensioni, è uno dei più importanti perché i ricercatori hanno continuato a migliorarlo.

Un anno dopo, Winograd e Don Coppersmith introdussero un nuovo algoritmo che integrava magnificamente il metodo laser. Questa combinazione di strumenti è stata presente praticamente in tutti gli sforzi successivi volti ad accelerare la moltiplicazione delle matrici.

Ecco un modo semplificato di pensare a come questi diversi elementi si incastrano. Cominciamo con due grandi matrici, A e B, che vuoi moltiplicare insieme. Innanzitutto, li scomponi in molte sottomatrici più piccole, o blocchi, come vengono talvolta chiamati. Successivamente, puoi utilizzare l'algoritmo di Coppersmith e Winograd come una sorta di manuale di istruzioni per la gestione e, in definitiva, l'assemblaggio dei blocchi. "Mi dice cosa moltiplicare, cosa aggiungere e quali voci vanno dove" nella matrice del prodotto C, ha detto Vassilevska Williams. "È solo una ricetta per costruire C da A e B."

C'è però un problema: a volte ci si ritrova con blocchi che hanno voci in comune. Lasciarli nel prodotto sarebbe come contare due volte quelle voci, quindi a un certo punto dovrai eliminare quei termini duplicati, chiamati sovrapposizioni. I ricercatori lo fanno “uccidendo” i blocchi in cui si trovano, impostando i loro componenti uguali a zero per rimuoverli dal calcolo.

È qui che entra finalmente in gioco il metodo laser di Strassen. "Il metodo laser in genere funziona molto bene e generalmente trova un buon modo per uccidere un sottoinsieme di blocchi per rimuovere la sovrapposizione", ha detto Le Gall. Dopo che il laser ha eliminato, o “bruciato via”, tutte le sovrapposizioni, è possibile costruire la matrice del prodotto finale, C.

Mettendo insieme queste varie tecniche si ottiene un algoritmo per moltiplicare due matrici con un numero di moltiplicazioni complessivamente volutamente esiguo, almeno in teoria. Il metodo laser non vuole essere pratico; è solo un modo per pensare al modo ideale di moltiplicare le matrici. "Non eseguiamo mai il metodo [su un computer]", ha detto Zhou. "Lo analizziamo."

E quell’analisi è ciò che ha portato al più grande miglioramento dell’omega in più di un decennio.

Viene riscontrata una perdita

Il documento dell'estate scorsa, di Duan, Zhou e Wu, ha dimostrato che il processo di Strassen potrebbe ancora essere accelerato in modo significativo. Tutto era a causa di un concetto che chiamavano perdita nascosta, sepolto in profondità nelle analisi precedenti – “un risultato dell’uccisione involontaria di troppi blocchi”, ha detto Zhou.

Il metodo laser funziona etichettando i blocchi con sovrapposizioni come rifiuti destinati allo smaltimento; altri blocchi sono ritenuti meritevoli e verranno salvati. Il processo di selezione, tuttavia, è alquanto casuale. Un blocco classificato come spazzatura potrebbe, in effetti, rivelarsi utile. Questa non è stata una sorpresa totale, ma esaminando molte di queste scelte casuali, il team di Duan ha stabilito che il metodo laser sottovalutava sistematicamente i blocchi: più blocchi dovrebbero essere salvati e meno buttati via. E, come spesso accade, meno rifiuti si traducono in maggiore efficienza.

"Essere in grado di mantenere più blocchi senza sovrapposizioni porta quindi a... un algoritmo di moltiplicazione delle matrici più veloce", ha affermato Le Gall.

Dopo aver dimostrato l'esistenza di questa perdita, il team di Duan ha modificato il modo in cui il metodo laser etichettava i blocchi, riducendo sostanzialmente gli sprechi. Di conseguenza, hanno fissato un nuovo limite superiore per omega a circa 2.371866 – un miglioramento rispetto al precedente limite superiore di 2.3728596, ambientato nel 2020 di Josh Alman e Vassilevska Williams. Potrebbe sembrare un cambiamento modesto, poiché abbassa il limite di circa 0.001. Ma è il singolo miglioramento più grande che gli scienziati hanno visto dal 2010. Il risultato del 2020 di Vassilevska Williams e Alman, in confronto, è migliorato solo di 0.00001 rispetto al suo predecessore.

Ma ciò che è più entusiasmante per i ricercatori non è solo il nuovo record in sé, che non è durato a lungo. È anche il fatto che il documento ha rivelato una nuova strada per il miglioramento che, fino ad allora, era passata del tutto inosservata. Da quasi quattro decenni tutti si affidano allo stesso metodo laser, spiega Le Gall. "Poi hanno scoperto che, beh, possiamo fare meglio."

L’articolo del gennaio 2024 ha perfezionato questo nuovo approccio, consentendo a Vassilevska Williams, Zhou e ai loro coautori di ridurre ulteriormente la perdita nascosta. Ciò ha portato a un ulteriore miglioramento del limite superiore di omega, riducendolo a 2.371552. Gli autori hanno anche generalizzato la stessa tecnica per migliorare il processo di moltiplicazione per rettangolari (n-By-m) matrici: una procedura che ha applicazioni nella teoria dei grafi, nell'apprendimento automatico e in altre aree.

Alcuni ulteriori progressi in questa direzione sono quasi certi, ma ci sono dei limiti. Nel 2015, Le Gall e due collaboratori dimostrato che l’approccio attuale – il metodo laser abbinato alla ricetta Coppersmith-Winograd – non può produrre un omega inferiore a 2.3078. Per apportare ulteriori miglioramenti, ha affermato Le Gall, “è necessario migliorare l’[approccio] originale di Coppersmith e Winograd che non è realmente cambiato dal 1987.. " Ma finora nessuno ha trovato un modo migliore. Potrebbe non essercene nemmeno uno.

"Migliorare gli omega è in realtà parte della comprensione di questo problema", ha detto Zhou. “Se riusciamo a comprendere bene il problema, allora possiamo progettare algoritmi migliori. [E] le persone sono ancora nelle primissime fasi della comprensione di questo annoso problema”.