27 Gennaio 2022
Expand search form

Cos’è la matrice di Strassen?

In questo capitolo, prima discuteremo il metodo generale di moltiplicazione delle matrici e poi discuteremo l’algoritmo di moltiplicazione delle matrici di Strassen.

Dichiarazione del problema

Consideriamo due matrici X e Y. Vogliamo calcolare la matrice risultante Z moltiplicando X e Y.

Metodo ingenuo

Per prima cosa, discuteremo il metodo ingenuo e la sua complessità. Qui, stiamo calcolando Z = X × Y. Usando il metodo ingenuo, due matrici (X e Y) possono essere moltiplicate se l’ordine di queste matrici è p × q e q × r. Di seguito è riportato l’algoritmo.

Complessità

Qui, assumiamo che le operazioni intere richiedano O(1) tempo. Ci sono tre per in questo algoritmo e uno è annidato nell’altro. Quindi, l’algoritmo richiede O(n 3 ) per essere eseguito.

Algoritmo di moltiplicazione delle matrici di Strassen

In questo contesto, utilizzando l’algoritmo di moltiplicazione della matrice di Strassen, il consumo di tempo può essere migliorato un po’.

La moltiplicazione di matrice di Strassen può essere eseguita solo su matrici quadrate dove n è una potenza di 2. L’ordine di entrambe le matrici è n × n.

Dividere X, Y e Z in quattro matrici (n/2)×(n/2) come rappresentato qui sotto –

$Z = inizioI & J K & L fineX = inizioA & B C & D finee $Y = inizioE & F G & H fine$

Usando l’algoritmo di Strassen calcola la seguente –

$$M_ <1>: colon= (A+C) tempo (E+F)$$

$$M_ <2>: colon= (B+D) tempi (G+H)$$

$$M_ <3>: colon= (A-D) volte (E+H)$$

$$M_ <4>: colon= A volte (F-H)$$

$$M_ <5>: colon= (C+D) volte (E)$$

$$M_ <6>: colon= (A+B) tempi (H)$$

$$M_ <7>: colon= D tempi (G-E)$$

$$I : colon= M_ <2>+ M_ <3>– M_ <6>– M_<7>$$

$$L : colon= M_ <1>– M_ <3>– M_ <4>– M_<5>$$

Analisi

$T(n)=inizioc & if:n= 17:x:T(frac<2>)+d:x:n^2 & otherwiseend$ dove c e d sono costanti

Usando questa relazione di ricorrenza, otteniamo $T(n) = O(n^)$

Quindi, la complessità dell’algoritmo di moltiplicazione delle matrici di Strassen è $O(n^)$.

Potresti anche essere interessato agli argomenti

Cosa intendi per matrice di Strassen?

La matrice di Strassen è un metodo Divide and Conquer che ci aiuta a moltiplicare due matrici (di dimensioni n X n).Jul 14, 2020

Continua…

Qual è lo scopo della moltiplicazione della matrice di Strassen?

L’algoritmo di Strassen è un metodo ricorsivo per la moltiplicazione di matrici dove dividiamo la matrice in 4 sottomatrici di dimensioni n/2 x n/2 in ogni passo ricorsivo. Per esempio, consideriamo due matrici 4 x 4 A e B che dobbiamo moltiplicare. Una 4 x 4 può essere divisa in quattro matrici 2 x 2. 17 agosto 2020

Continua…

Come si memorizza la moltiplicazione delle matrici di Strassen?

mettiamo gli elementi come valore dell’indice della matrice. Quindi ora per imparare la formula di Q. C’è un semplice trucco. Eseguiremo in altre parole B a a B. | Tempo – 0:21 [Inglese]

Continua…

Come si trova la matrice indicata?

Operazioni con le matrici: Find the Indicated Matrix – YouTubeStart of suggested clipEnd of suggested clipSo questo è solo semplice sottrazione di matrici. Quindi in pratica si prende una cella della matrice. AndMoreSo questo è solo semplice sottrazione di matrici. Quindi fondamentalmente prendete una cella della matrice. E la sottrai dalla cella corrispondente dell’altra matrice. | Tempo – 0:02 [Inglese]

Continua…

Come si memorizzano le formule di Strassen?

P1 = A. P2= H. P3= E. P4= D. P5= ( A + D ) * ( E + H )P1 = A. P2= H. P3= E. P4= D. P5= ( A + D ) * ( E + H ) P6= ( B – D ) * ( G + H ) … P1 = A * ( F – H) P2= H. P3= E. P4= D. P5= ( A + D ) * ( E + H ) P6= ( B – D ) * ( G + H) … P1= A * ( F – H ) P2= H * ( A + B ) P3= E * ( C + D ) P4= D. P5= ( A + D ) * ( E + H )

Continua…

Qual è la relazione di ricorrenza usata nell’algoritmo di Strassen?

Spiegazione: La relazione di ricorrenza utilizzata nell’algoritmo di Strassen è 7T(n/2) + Theta(n2) poiché ci sono solo 7 moltiplicazioni ricorsive e Theta(n2) aggiunte e sottrazioni scalari coinvolte per calcolare il prodotto.

Continua…

Si usa l’algoritmo di Strassen?

L’algoritmo di Strassen è più lento dei più veloci algoritmi conosciuti per matrici estremamente grandi, ma tali algoritmi non sono utili nella pratica, poiché sono molto più lenti per matrici di dimensioni pratiche.

Continua…

L’algoritmo di Strassen è divide et impera?

Il metodo di Strassen è simile al precedente metodo divide et impera, nel senso che anche questo metodo divide le matrici in sottomatrici di dimensioni N/2 x N/2 come mostrato nel diagramma sopra, ma nel metodo di Strassen, le quattro sottomatrici del risultato sono calcolate usando le seguenti formule.

Continua…

Come funziona una matrice in matematica?

In matematica, una matrice (matrici plurali) è una matrice rettangolare di numeri, simboli o espressioni, disposti in righe e colonne. Le matrici sono comunemente scritte tra parentesi quadre. Le linee orizzontali e verticali di voci in una matrice sono chiamate rispettivamente righe e colonne.

Continua…

Cosa significa i3 nelle matrici?

Nota: la matrice identità si identifica con una I maiuscola e un pedice che indica le dimensioni; consiste in una diagonale di uno e gli angoli sono riempiti di zeri. Esempio: Moltiplicare A per la matrice identità. Inversi: Un numero per il suo inverso (A.K.A.

Continua…

Perché la moltiplicazione di matrici di Strassen è considerata migliore della semplice moltiplicazione di matrici?

Abstract L’obiettivo principale di questo articolo è quello di confrontare la complessità del tempo di esecuzione e la complessità dello spazio tra l’algoritmo di Strassen e l’algoritmo convenzionale per la moltiplicazione delle matrici. … La conclusione generale è che l’algoritmo di Strassen è più efficiente dell’algoritmo convenzionale su matrici di grandi dimensioni.

Continua…

Qual è l’idea chiave dell’algoritmo di moltiplicazione delle matrici di Strassen?

L’idea di base dell’algoritmo di Strassen è di dividere A e B in 8 sottomatrici e poi calcolare ricorsivamente le sottomatrici di C. Questa strategia è chiamata Divide et Impera. Usiamo poi questi risultati per calcolare le sottomatrici di C.

Continua…

Qual è la relazione di ricorrenza per la moltiplicazione delle matrici di Strassen?

9. Qual è la relazione di ricorrenza usata nell’algoritmo di Strassen? Spiegazione: La relazione di ricorrenza utilizzata nell’algoritmo di Strassen è 7T(n/2) + Theta(n2) poiché ci sono solo 7 moltiplicazioni ricorsive e Theta(n2) aggiunte e sottrazioni scalari coinvolte per calcolare il prodotto.

Continua…

Perché si usa il teorema del maestro?

1. Il teorema di Master è usato per? Spiegazione: Il teorema di Master è un metodo diretto per risolvere le ricorrenze. Possiamo risolvere qualsiasi ricorrenza che rientra in uno dei tre casi del teorema di Master.

Continua…

Come si descrive una matrice?

Una matrice è una disposizione rettangolare di numeri in righe e colonne. Per esempio, la matrice A ha due righe e tre colonne.

Continua…

Articolo precedente

Quale parte del giglio è velenosa per i cani?

Articolo successivo

Come si rifinisce sikaflex?

You might be interested in …

Come funziona il miniprep Qiagen?

Dopo la lisi dei batteri in condizioni alcaline, il lisato viene applicato in condizioni saline definite al QIAGEN-tip. Il DNA plasmidico viene selettivamente legato e purificato da RNA, proteine e altri contaminanti cellulari. La resa […]

Come si fa a decorare una classe?

Come un film o una produzione teatrale di successo, l’apprendimento si basa sull’ambientazione adeguata per renderlo stimolante e d’impatto. Questo è particolarmente importante per i bambini, i cui tempi di attenzione possono essere brevi. Ecco […]