BARTOLO LUQUE – Quan multipliquem dues matrius quadrades A i B de N files i N columnes (el que en llenguatge de matrius anomenem “d’ordre N”), cadascun dels NxN elements de la matriu resultant prové del producte escalar d’una fila de A amb una columna de B. Algorítmicament realitzem N productes i sumem N nombres per obtenir una entrada de la nova matriu resultant. Els matemàtics diuen que l’ordre de complexitat d’aquesta operació és O(N). Com que hem de realitzar N×N = N2 operacions com aquesta, la matriu producte té un cost de O(N3).
Què significa això en un nivell pràctic? Suposem que un programa d’ordinador multiplica dues matrius de 1000 x 1000, amb aquest algoritme clàssic, en T unitats de temps. Aleshores, podem esperar que si multipliquem dues matrius del 2000 x 2000, el temps d’execució s’incremente 23 = 8 vegades. El temps d’execució creix amb el cub de la mida N de la matriu.
Fins al 1969 es pensava que aquest seria realment l’ordre de complexitat del producte de matrius. Però el professor alemany Volker Strassen, per a sorpresa de tots, va corregir aquest límit en proposar un algoritme capaç de rebaixar la complexitat fins a O(N2,807). Seguint amb el nostre exemple anterior, en doblar la mida de la matriu, amb l’algoritme de Strassen tardaríem 22,807 = 6,998… vegades més i no 8, com en l’algoritme clàssic. Es va obrir així la recerca de noves millores que van semblar culminar amb l’algoritme de Coppersmith-Winograd el 1990, que va establir un límit pràctic en O(N2,376), que s’ha mantingut durant més de 20 anys i que s’explica des d’aleshores a les aules universitàries. (Si insistim en el nostre exemple: 22,376 = 5,190…).
Virginia Vassilevska Williams
No obstant això, l’any passat, l’estudiant doctorand Andrew Stothers va aconseguir rebaixar encara més aquest límit que semblava definitiu. El va rebaixar de O(N2,376) a O(N2,374). Sorprenentment l’èxit va passar desapercebut a la comunitat matemàtica perquè el seu autor no va publicar el resultat fora de la seua tesi doctoral i va deixar la matemàtica per a dedicar-se a l’empresa privada. De fet, ni tan sols se’n feia esment en el resum de resultats importants de la tesi, com si Stothers i el seu director de tesi no foren conscients de la importància del resultat. L’èxit s’ha conegut finalment gràcies a l’estudiant postdoctoral Virginia Vassilevska Williams, que aquest passat 28 de novembre ha proposat un nou mètode amb nova rebaixa a O(N2,3727).
La millora des del rècord del 1990 al nou del 2011 (que passa l’exponent 2,376 a 2,3727) pot semblar ridícula, i vista des de fora, l’enrenou entre els experts pot resultar incomprensible. Però recordem que el producte de matrius gegantines i denses està a l’ordre del dia en aplicacions que van des de la física nuclear als mercats financers, i quan es treballa amb matrius de milions d’elements, el temps de còmput no és menyspreable (en el nostre exemple passaríem de 22,376 = 5,190… a 22,3727 = 5,179… vegades més temps d’execució en doblar la mida de la matriu). Sense oblidar que el nou descobriment torna a obrir la veda i la mateixa Virginia Vassilevska no veu desgavellada la possibilitat d’aconseguir un límit mínim de complexitat d’ordre O(N2).
© 2012 Conec. Tots les drets reservats.
No comments yet.