PDA

Visualizza la versione completa : Moltiplicazione di n-matrici


RmiMik
18-01-2003, 15:33
Come posso Moltiplicare n-matrici,
o meglio quale Ŕ l'algoritmo che me le moltiplica in modo ottimale?
:dh˛:

r0x
18-01-2003, 16:10
Ho trovato questo:

http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/mat_chain.html

Focalizza l'efficienza sulla posizione delle parentesi per scegliere l'associativitÓ che maggiormente riduca il numero di righe/colonne dei prodotti intermedi. Inoltre in fondo alla pagina c'Ŕ un applet che spiega l'algoritmo per gradi.

Ciao.

Dwenegar
18-01-2003, 17:14
Se le matrici sono quadrate basta cercare con google. Ci sono molti algoritmi per moltiplicare due matrici. Tutti hanno un grado di efficienza in funzione delle caratteristiche della matrice. Nel caso peggiore tutti sono O(n^3). Vi Ŕ un algoritmo (l'algoritmo di Strassen) che con una matrice generica ha complessitÓ (O^2.81). Ora non ce l'ho sotto mano ma lo trovi facilmente in giro.

Loading