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.^[1] 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 $n 3$ operacions de camp per multiplicar dues $n \times n$ matrius sobre aquest camp ( $Θ(n 3)$ 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 $O(n 2.37188)$ , donat per Duan, Wu i Zhou anunciat en una preimpressió. Això millora el límit del temps $O(n 2.3728596)$ , donat per Josh Alman i Virginia Vassilevska Williams.^[2] 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 $C = AB$ per a una matriu $n \times m$ $A$ i una matriu $m \times p$ $B$ , aleshores $C$ és una matriu $n \times p$ 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 $i$ d'1 a $n$ i $j$ d'1 a $p$ , calculant l'anterior utilitzant un bucle imbricat.

Aquest algorisme pren temps $Θ(nmp)$ (en notació asimptòtica).^[3] Una simplificació comuna per a l'anàlisi d'algorismes és suposar que les entrades són totes matrius quadrades de mida $n \times n$ , en aquest cas el temps d'execució és $Θ(n 3)$ , é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; ^[4] 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={\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\\\end{pmatrix}},\,A={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\\\end{pmatrix}},\,B={\begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\\\end{pmatrix}},$

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 $2 n \times 2 n$ per a alguns $n$ . El producte de la matriu és ara

${\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\\\end{pmatrix}}={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\\\end{pmatrix}}{\begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\\\end{pmatrix}}={\begin{pmatrix}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{pmatrix}}$

Algorismes subcúbics

Millora de les estimacions de l'exponent

ω

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 $2 \times 2$ 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è $n > 100$ aproximadament ^[5] i apareix en diverses biblioteques, com ara BLAS.^[6] É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

C

En l'algorisme 3D, cada parell de submatrius de

A

i

B

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

${\begin{pmatrix}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{pmatrix}}$

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ó $Ω(n 3)$ .

Referències

↑ Skiena, Steven. «Sorting and Searching». A: The Algorithm Design Manual (en anglès). Springer, 2012, p. 45–46, 401–3. DOI 10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.
↑ Hartnett, Kevin. «Matrix Multiplication Inches Closer to Mythic Goal» (en anglès). Quanta Magazine, 23-03-2021. [Consulta: 1r abril 2021].
↑ Skiena, Steven. «Sorting and Searching». A: The Algorithm Design Manual (en anglès). Springer, 2012, p. 45–46, 401–3. DOI 10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.
↑ Skiena, Steven. «Sorting and Searching». A: The Algorithm Design Manual (en anglès). Springer, 2012, p. 45–46, 401–3. DOI 10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.
↑ Skiena, Steven. «Sorting and Searching». A: The Algorithm Design Manual (en anglès). Springer, 2012, p. 45–46, 401–3. DOI 10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.
↑ Press, William H. Numerical Recipes: The Art of Scientific Computing (en anglès). 3rd. Cambridge University Press, 2007, p. 108. ISBN 978-0-521-88068-8.

[skiena-1] Skiena, Steven. «Sorting and Searching». A: The Algorithm Design Manual (en anglès). Springer, 2012, p. 45–46, 401–3. DOI 10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.

[quanta2-2] Hartnett, Kevin. «Matrix Multiplication Inches Closer to Mythic Goal» (en anglès). Quanta Magazine, 23-03-2021. [Consulta: 1r abril 2021].

[skiena2-3] Skiena, Steven. «Sorting and Searching». A: The Algorithm Design Manual (en anglès). Springer, 2012, p. 45–46, 401–3. DOI 10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.

[skiena3-4] Skiena, Steven. «Sorting and Searching». A: The Algorithm Design Manual (en anglès). Springer, 2012, p. 45–46, 401–3. DOI 10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.

[skiena4-5] Skiena, Steven. «Sorting and Searching». A: The Algorithm Design Manual (en anglès). Springer, 2012, p. 45–46, 401–3. DOI 10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.

[6] Press, William H. Numerical Recipes: The Art of Scientific Computing (en anglès). 3rd. Cambridge University Press, 2007, p. 108. ISBN 978-0-521-88068-8.

[1]

[2]

[3]

[4]

[5]

[6]