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 \( \displaystyle {D}{B}={B}{D} \)

risolto, basta che la matrice D abbia tutti elementi uguali sulla diagonale affinché l'uguaglianza sia vera, altrimenti sarà vero \( \displaystyle {D}{B}={{\left({B}{D}\right)}}^{{T}} \)

2) descrivere due algoritmi che calcolano i prodotti DB e BD con costo \( \displaystyle {O}{\left({{n}}^{{2}}\right)} \) 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 \( \displaystyle {O}{\left({{n}}^{{2}}\right)} \) può andare?

ma l'implementazione in pseudocodice come la faccio?

3) se \( \displaystyle {v}\in{\mathbb{R}}^{{n}} \) trovare un algoritmo che calcoli \( \displaystyle {D}{B}{v} \) con costo asintotico \( \displaystyle {2}{{n}}^{{2}} \) operazioni

questo non riesco a capire come può venire \( \displaystyle {2}{{n}}^{{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:

Codice: Seleziona tutto

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.

Codice: Seleziona tutto

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à \( \displaystyle {O}{\left({{n}}^{{2}}\right)} \) 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.