Algorisme de multiplicació de matrius

Com que la multiplicació de matrius és una operació tan central en molts algorismes numèrics, s'ha invertit molt de treball per fer eficients els algorismes de multiplicació de matrius. Les aplicacions de la multiplicació de matrius en problemes computacionals es troben en molts camps, com ara la informàtica científica i el reconeixement de patrons, i en problemes aparentment no relacionats, com ara comptar els camins a través d'un gràfic. S'han dissenyat molts algorismes diferents per multiplicar matrius en diferents tipus de maquinari, inclosos sistemes paral·lels i distribuïts, on el treball computacional s'estén en diversos processadors (potser a través d'una xarxa).

L'aplicació directa de la definició matemàtica de la multiplicació de matrius dona un algorisme que triga un temps de l'ordre de Plantilla:Math operacions de camp per multiplicar dues Plantilla:Math matrius sobre aquest camp (Plantilla:Math en notació O gran). Des de l'algorisme de Strassen a la dècada de 1960 es coneixen millors límits asimptòtics sobre el temps necessari per multiplicar matrius, però el temps òptim (és a dir, la complexitat computacional de la multiplicació de matrius) segueix sent desconegut. L'octubre del 2022, el millor límit anunciat de la complexitat asimptòtica d'un algorisme de multiplicació de matrius és el temps Plantilla:Math, donat per Duan, Wu i Zhou anunciat en una preimpressió. Això millora el límit del temps Plantilla:Math, donat per Josh Alman i Virginia Vassilevska Williams. Tanmateix, aquest algorisme és un algorisme galàctic a causa de les grans constants i no es pot realitzar pràcticament.

Algorisme iteratiu

La definició de la multiplicació de matrius és que si Plantilla:Math per a una matriu Plantilla:Math Plantilla:Mvar i una matriu Plantilla:Math Plantilla:Mvar, aleshores Plantilla:Mvar és una matriu Plantilla:Math amb entrades

Il·lustració de l'ordre principal de fila i columna

$c_{ij}=\sum _{k=1}^m{a}_{ik}{b}_{kj}.$

A partir d'això, es pot construir un algorisme senzill que fa un bucle sobre els índexs Plantilla:Mvar d'1 a Plantilla:Mvar i Plantilla:Mvar d'1 a Plantilla:Mvar, calculant l'anterior utilitzant un bucle imbricat.

Aquest algorisme pren temps Plantilla:Math (en notació asimptòtica). Una simplificació comuna per a l'anàlisi d'algorismes és suposar que les entrades són totes matrius quadrades de mida Plantilla:Math, en aquest cas el temps d'execució és Plantilla:Math, és a dir, cúbic en la mida de la dimensió.

Els tres bucles de la multiplicació iterativa de matrius es poden intercanviar arbitràriament entre ells sense que hi hagi cap efecte sobre la correcció o el temps d'execució asimptòtic. Tanmateix, l'ordre pot tenir un impacte considerable en el rendiment pràctic a causa dels patrons d'accés a la memòria i l'ús de la memòria cau de l'algorisme; quin ordre és millor també depèn de si les matrius s'emmagatzemen en l'ordre principal de la fila, l'ordre principal de la columna o una barreja d'ambdós.

Algorisme de divideix i venceràs

Una alternativa a l'algoritme iteratiu és l'algoritme de divideix i conquereix per a la multiplicació de matrius. Això es basa en la partició de blocs

$C=\left(\begin{array}{cc}{C}_{11}& C_{12}\\ C_{21}& C_{22}\end{array}\right),A=\left(\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right),B=\left(\begin{array}{cc}{B}_{11}& B_{12}\\ B_{21}& B_{22}\end{array}\right),$

que funciona per a totes les matrius quadrades les dimensions de les quals són potències de dos, és a dir, les formes són Plantilla:Math per a alguns Plantilla:Mvar. El producte de la matriu és ara

$\left(\begin{array}{cc}{C}_{11}& C_{12}\\ C_{21}& C_{22}\end{array}\right)=\left(\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right)\left(\begin{array}{cc}{B}_{11}& B_{12}\\ B_{21}& B_{22}\end{array}\right)=\left(\begin{array}{cc}{A}_{11}{B}_{11}+A_{12}{B}_{21}& A_{11}{B}_{12}+A_{12}{B}_{22}\\ A_{21}{B}_{11}+A_{22}{B}_{21}& A_{21}{B}_{12}+A_{22}{B}_{22}\end{array}\right)$

Algorismes subcúbics

Millora de les estimacions de l'exponent Plantilla:Math al llarg del temps per a la complexitat computacional de la multiplicació de matrius $O(n^{\omega })$.

Existeixen algorismes que proporcionen millors temps de funcionament que els senzills. El primer que es va descobrir va ser l'algorisme de Strassen, ideat per Volker Strassen el 1969 i sovint anomenat "multiplicació ràpida de matrius". Es basa en una manera de multiplicar dues matrius Plantilla:Math que només requereix 7 multiplicacions (en lloc de les 8 habituals), a costa de diverses operacions addicionals de suma i resta. Aplicar-ho de manera recursiva dona un algorisme amb un cost multiplicatiu de $O(n^{{\log }_{2}7})\approx O(n^{2.807})$. L'algorisme de Strassen és més complex, i l'estabilitat numèrica es redueix en comparació amb l'algorisme naïf, però és més ràpid en els casos en què Plantilla:Math aproximadament i apareix en diverses biblioteques, com ara BLAS. És molt útil per a matrius grans sobre dominis exactes com ara camps finits, on l'estabilitat numèrica no és un problema.

Algorismes paral·lels i distribuïts

Multiplicació de matrius de blocs. En l'algorisme 2D, cada processador és responsable d'una submatriu de Plantilla:Mvar En l'algorisme 3D, cada parell de submatrius de Plantilla:Mvar i Plantilla:Mvar que es multiplica s'assigna a un processador.

Paral·lelisme de memòria compartida

L'algoritme de divideix i conquereix esbossat anteriorment es pot paral·lelitzar de dues maneres per als multiprocessadors de memòria compartida. Es basen en el fet que les vuit multiplicacions de matrius recursives en

$\left(\begin{array}{cc}{A}_{11}{B}_{11}+A_{12}{B}_{21}& A_{11}{B}_{12}+A_{12}{B}_{22}\\ A_{21}{B}_{11}+A_{22}{B}_{21}& A_{21}{B}_{12}+A_{22}{B}_{22}\end{array}\right)$

es poden realitzar independentment entre si, igual que les quatre sumacions (tot i que l'algoritme necessita "unir" les multiplicacions abans de fer les sumacions). Aprofitant tot el paral·lelisme del problema, s'obté un algorisme que es pot expressar en pseudocodi d'estil fork-join.

Algoritmes distribuïts i evitant la comunicació

A les arquitectures modernes amb memòria jeràrquica, el cost de carregar i emmagatzemar els elements de la matriu d'entrada tendeix a dominar el cost de l'aritmètica. En una única màquina, aquesta és la quantitat de dades transferides entre la memòria RAM i la memòria cau, mentre que en una màquina multinode de memòria distribuïda és la quantitat transferida entre nodes; en qualsevol cas s'anomena ample de banda de comunicació. L'algorisme naïf que utilitza tres bucles imbricats utilitza ample de banda de comunicació Plantilla:Math.