Complessità prodotto matrice vettore
Siano $A\inM_n(RR)$ e $x\inRR^n$.
In generale il calcolo di $Ax$ richiede $n^2$ prodotti in quanto il prodotto matrice per vettore equivale al calcolo di $n$ prodotti scalari, ciascuno dei quali consiste in $n$ prodotti tra scalari.
Se ora supponiamo che $A$ sia una matrice sparsa la complessità del calcolo di $Ax$ si riduce a $O(n)$: non mi è però molto chiaro il motivo.
Ho supposto che sia perchè, detto $m_i$ il numero di entrate non nulle della i-esima riga di $A$ e definito $m=max_{1<=i<=n}m_i$, il numero di operazioni da fare per calcolare $Ax$ è $\sum_{i=1}^nm_i<=\sum_{i=1}^nm=mn=O(n)$. Per caso è questo il motivo? Non mi convince per il fatto che se ad esempio $A$ ha il 10% di entrate non nulle, al crescere di $n$ cresce sia il numero di prodotti scalari da fare che il numero di moltiplicazioni da fare per calcolare ogni prodotto scalare...dunque a me verrebbe da dire che la complessità dovrebbe essere qualcosa come $O(n^2)$.
Qualcuno mi chiarisce le idee?
In generale il calcolo di $Ax$ richiede $n^2$ prodotti in quanto il prodotto matrice per vettore equivale al calcolo di $n$ prodotti scalari, ciascuno dei quali consiste in $n$ prodotti tra scalari.
Se ora supponiamo che $A$ sia una matrice sparsa la complessità del calcolo di $Ax$ si riduce a $O(n)$: non mi è però molto chiaro il motivo.
Ho supposto che sia perchè, detto $m_i$ il numero di entrate non nulle della i-esima riga di $A$ e definito $m=max_{1<=i<=n}m_i$, il numero di operazioni da fare per calcolare $Ax$ è $\sum_{i=1}^nm_i<=\sum_{i=1}^nm=mn=O(n)$. Per caso è questo il motivo? Non mi convince per il fatto che se ad esempio $A$ ha il 10% di entrate non nulle, al crescere di $n$ cresce sia il numero di prodotti scalari da fare che il numero di moltiplicazioni da fare per calcolare ogni prodotto scalare...dunque a me verrebbe da dire che la complessità dovrebbe essere qualcosa come $O(n^2)$.
Qualcuno mi chiarisce le idee?
Risposte
La definizione di matrice sparsa è molto traballante: quand'è che una matrice ha tanti zero?
È vero che in alcuni casi la complessità è \(O(n)\), ma non sempre, per i motivi che giustamente dici tu.
Nel calcolo scientifico si trovano spesso matrici con bande fisse [tridiagonali, pentadiagonali e così via]. In quel caso è sicuramente vero che l'operazione ha complessità lineare, perché ogni riga ha sempre lo stesso numero di elementi [tranne negli angoli, ma poca roba].
È vero che in alcuni casi la complessità è \(O(n)\), ma non sempre, per i motivi che giustamente dici tu.
Nel calcolo scientifico si trovano spesso matrici con bande fisse [tridiagonali, pentadiagonali e così via]. In quel caso è sicuramente vero che l'operazione ha complessità lineare, perché ogni riga ha sempre lo stesso numero di elementi [tranne negli angoli, ma poca roba].
Questa mi interessa, ma vorrei chiarire un punto che mi è un po' oscuro, ovvero a me sembra che sia implicito il fatto che le stime di cui parlate dipendano dall'algoritmo usato... per intenderci mi sembra che il fatto se una matrice sia sparsa o meno non può modificare l'ordine dell'algoritmo naif. Voglio dire se ho un algoritmo che fa $n^2$ operazioni, rimarranno $n^2$ anche se talvolta questo sono triviali come $0$ per $0$... è corretto?
Immagino ci siano invece algoritmi di moltiplicazione diversi da quello naif che:
1) si applicano quando la forma di una matrice è di una particolare forma (tridiagonale per esempio). Ma questo si deve fare costruendo l'algoritmo di modo che NON si facciano operazioni inutili usando le informazioni sulla forma esatta della matrice in modo che ne possano fare meno di $n^2$;
2) abbiano un numero di passi variabile a seconda della matrice in input e si blocchino dopo un numero di passi che è un $O(n)$ per qualsiasi matrice sparsa (in qualche senso). Un procedimento iterativo potrebbe portare a questo risultato.
non sono a conoscenza di algoritmi del secondo tipo, ma immagino esistano...
Immagino ci siano invece algoritmi di moltiplicazione diversi da quello naif che:
1) si applicano quando la forma di una matrice è di una particolare forma (tridiagonale per esempio). Ma questo si deve fare costruendo l'algoritmo di modo che NON si facciano operazioni inutili usando le informazioni sulla forma esatta della matrice in modo che ne possano fare meno di $n^2$;
2) abbiano un numero di passi variabile a seconda della matrice in input e si blocchino dopo un numero di passi che è un $O(n)$ per qualsiasi matrice sparsa (in qualche senso). Un procedimento iterativo potrebbe portare a questo risultato.
non sono a conoscenza di algoritmi del secondo tipo, ma immagino esistano...
Vero, un algoritmo generico non distingue zero da non zero [un compilatore intelligente potrebbe, ma questo è un altro paio di maniche].
Si può giocare sul modo in cui memorizzi la matrice: se usi il CRS http://netlib.org/linalg/html_templates/node91.html puoi sviluppare facilmente un algoritmo che fa solo le operazioni che non coinvolgono zeri.
Si può giocare sul modo in cui memorizzi la matrice: se usi il CRS http://netlib.org/linalg/html_templates/node91.html puoi sviluppare facilmente un algoritmo che fa solo le operazioni che non coinvolgono zeri.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo