Algoritmo per calcolo prodotto di matrici

[Andry459]

Salve, sto facendo un vecchio (2004) esercizio trovato su un sito, relativo ad Analisi numerica.

Date D (matrice diagonale nxn) e B (matrice generica nxn) dire:

1) se $ DB=BD $

risolto, basta che la matrice D abbia tutti elementi uguali sulla diagonale affinché l'uguaglianza sia vera, altrimenti sarà vero $ DB=(BD)^T $

2) descrivere due algoritmi che calcolano i prodotti DB e BD con costo $ O(n^2) $ e fornire una implementazione in pseudocodice

questo non riesco a farlo(o meglio c'ho provato). scrivendo le matrici mi accorgo che per moltiplicarle devo solo moltiplicare l' elemento della diagonale (quindi per a i,i che va da (i=1 a i=n)) per un solo valore della seconda matrice, secondo il mio ragionamento ,credo sbagliato, mi viene un costo pari a 1 operazione per ogni elemento fino ad n (per coprire tutte la colonne) per n che è la dimensione delle matrici(per le righe), quindi $ O(n^2) $ può andare?

ma l'implementazione in pseudocodice come la faccio?

3) se $ v in RR^n $ trovare un algoritmo che calcoli $ DBv $ con costo asintotico $ 2n^2 $ operazioni

questo non riesco a capire come può venire $ 2n^2 $ operazioni..


Se potete aiutarmi a capire ve ne sarò infinitamente grato!
Grazie mille

[vict85]

Per il primo si tratta di notare che devi semplicemente scalare le righe e le colonne. Lo pseudocodice usato sarà qualcosa del tipo:

INPUT dense nxn matrix B
      diagonal nxn matrix D as vector
OUTPUT dense nxn matrix R = DB
for i = 1 to n do
for j = 1 to n do
R(i,j) = D(i) * B(i,j);
end for
end for

Ma il tuo libro userà uno pseudocodice suo. Quindi vedilo e imparalo.
L'altro è del tutto simile.

Per il punto 3 uso lo stesso pseudocodice.

INPUT dense nxn matrix B
      diagonal nxn matrix D as vector
      n vector v
OUTPUT n vector V = DBv
for i = 1 to n do
V(i) = 0;
for j = 1 to n do
temp := D(i) * B(i,j);
V(i) += temp * v(j);
end for
end for

Immagino che intenda questo metodo. Lo puoi anche dividere in due gruppi di cicli in realtà.

[Andry459]

Grazie , era proprio questo quello che cercavo di acpire.

Per il codice posso usare quello che preferisco, anche un linguaggio vero e proprio volendo..

Grazie mille!

[hamming_burst]

ma la complessità $O(n^2)$ per la moltiplicazione di queste due matrici, è dovuta unicamente al fatto che una di esse è diagonale, giusto? se no mi pare parecchio errata sta complessità...

[Andry459]

Si si , la matrice D è diagonale.