Forum » Programiranje » Strassenovo množenje matrik
Strassenovo množenje matrik
eXoo ::
Pri predmetu Algoritmi imam 1 vajo ki mi je nerazumljiva (še manj zanimiva) in sicer: Množenje dveh matrik A in B reda 4×4 izvedemo s strassenovim množenjem. Izračunajte podmatriki P in S reda 2×2, če sta :
1 2 3 7
0 4 2 -1
A = 4 5 6 0
-2 3 3 4
7 1 2 1
3 4 0 -4
B = 3 1 2 5
2 -5 4 7
No če ima kdo kaj volje za kakšno hitro razlago oziroma nasvet se priporočam. Tnx.
1 2 3 7
0 4 2 -1
A = 4 5 6 0
-2 3 3 4
7 1 2 1
3 4 0 -4
B = 3 1 2 5
2 -5 4 7
No če ima kdo kaj volje za kakšno hitro razlago oziroma nasvet se priporočam. Tnx.
- spremenil: eXoo ()
sherman ::
Koristno bi bilo, ce bi povedal kaj ste oznacili s P in S, ker ne uporabljajo vsi istih oznak.
Thomas ::
Tole je out. Tole množenje matrik po Štrasenu je brezveze, odkar računalniki množijo skoraj tako hitro kot seštevajo. Vseh operacij je več kakor na klasičen način, zato samo zamujaš tkole.
Sam kaj bi ti razlagal podrobnosti, če te pa ne zanima.
Sam kaj bi ti razlagal podrobnosti, če te pa ne zanima.
Man muss immer generalisieren - Carl Jacobi
sherman ::
In v cem je sedaj problem?
A razstavis na 4 2x2 podmatrike, to so potem A11,A12,A21,A22.
A=\left(\begin{array}{cc}A_{11}&A_{12}\\A_{21}&A_{22}\end{array}\right) (napaka se odpravlja)
Enako za B. Vstavis te podmatrike v predpisa za P in S. Matrike sestevas tako da sestejes ustrezne komponente, element produkta v i-ti vrstici in j-tem stolpcu pa je navaden skalarni produkt i-te vrstice leve matrike z j-tim stolpcem desne.
A razstavis na 4 2x2 podmatrike, to so potem A11,A12,A21,A22.
A=\left(\begin{array}{cc}A_{11}&A_{12}\\A_{21}&A_{22}\end{array}\right) (napaka se odpravlja)
Enako za B. Vstavis te podmatrike v predpisa za P in S. Matrike sestevas tako da sestejes ustrezne komponente, element produkta v i-ti vrstici in j-tem stolpcu pa je navaden skalarni produkt i-te vrstice leve matrike z j-tim stolpcem desne.
eXoo ::
potem je tak ? :
A=
(A11 A12)
(A21 A22)
B=
(B11 B12)
(B21 B22)
P = (1 + 4) * (7 + 4) = 55
S = 4*(3 - 7) = -16
Mislim da sem vžgal v temo...
A=
(A11 A12)
(A21 A22)
B=
(B11 B12)
(B21 B22)
P = (1 + 4) * (7 + 4) = 55
S = 4*(3 - 7) = -16
Mislim da sem vžgal v temo...
Zgodovina sprememb…
- spremenil: eXoo ()
sherman ::
A_{11}=\left(\begin{array}{cc}1&2\\0&4\end{array}\right) (napaka se odpravlja)
A_{12}=\left(\begin{array}{cc}3&7\\2&-1\end{array}\right) (napaka se odpravlja)
A_{21}=\left(\begin{array}{cc}4&5\\-2&3\end{array}\right) (napaka se odpravlja)
in tako naprej.
Katera sola je to?
Mnozenj + sestevanj skalarjev je pri Strassenovem mnozenju manj kot pri navadnem kubicnem. Seveda za dovolj velike matrike.
A_{12}=\left(\begin{array}{cc}3&7\\2&-1\end{array}\right) (napaka se odpravlja)
A_{21}=\left(\begin{array}{cc}4&5\\-2&3\end{array}\right) (napaka se odpravlja)
in tako naprej.
Katera sola je to?
Tole je out. Tole množenje matrik po Štrasenu je brezveze, odkar računalniki množijo skoraj tako hitro kot seštevajo. Vseh operacij je več kakor na klasičen način, zato samo zamujaš tkole.
Mnozenj + sestevanj skalarjev je pri Strassenovem mnozenju manj kot pri navadnem kubicnem. Seveda za dovolj velike matrike.
Zgodovina sprememb…
- spremenilo: sherman ()
eXoo ::
se pravi:
P =
(7 2) *(9 6)
(3 8) * (7 11)
je pa feri 1 letnik neka domača naloga, iz lansekga leta se mi zdi.
P =
(7 2) *(9 6)
(3 8) * (7 11)
je pa feri 1 letnik neka domača naloga, iz lansekga leta se mi zdi.
Zgodovina sprememb…
- spremenil: eXoo ()
sherman ::
P=\left(A_{11}+A_{22}\right)\left(B_{11}+B_{22}\right)=\left(\left(\begin{array}{cc}1&2\\0&4\end{array}\right)+\left(\begin{array}{cc}6&0\\3&4\end{array}\right)\right)\left(\left(\begin{array}{cc}7&1\\3&4\end{array}\right)+\left(\begin{array}{cc}2&5\\4&7\end{array}\right)\right)=
\left(\begin{array}{cc}7&2\\3&8\end{array}\right)\left(\begin{array}{cc}9&6\\7&11\end{array}\right) (napaka se odpravlja)
Ce imas matriki A=\left(\begin{array}{cc}a&b\\c&d\end{array}\right) (napaka se odpravlja) in B=\left(\begin{array}{cc}e&f\\g&h\end{array}\right) (napaka se odpravlja) je produkt AB=\left(\begin{array}{cc}ae+bg&af+bh\\ce+dg&cf+dh\end{array}\right) (napaka se odpravlja)
Ce imas matriki A=\left(\begin{array}{cc}a&b\\c&d\end{array}\right) (napaka se odpravlja) in B=\left(\begin{array}{cc}e&f\\g&h\end{array}\right) (napaka se odpravlja) je produkt AB=\left(\begin{array}{cc}ae+bg&af+bh\\ce+dg&cf+dh\end{array}\right) (napaka se odpravlja)
modicr ::
Tole je out. Tole množenje matrik po Štrasenu je brezveze, odkar računalniki množijo skoraj tako hitro kot seštevajo. Vseh operacij je več kakor na klasičen način, zato samo zamujaš tkole.
Mnozenj + sestevanj skalarjev je pri Strassenovem mnozenju manj kot pri navadnem kubicnem. Seveda za dovolj velike matrike.
BTW, Strassen algoritem res ni prav strašen :)
Standard ... ... A*n^3 + O(n^2) Strassen ... ... B*n^2.807 + O(n^2) Coppersmith-Winograd ... C*n^2.376 + O(n^2)
Problem je v tem, da je konstanta C zelo velika v primerjavi z A in B, zato je CW algoritem zanimiv samo teoretično, saj menda noben ne množi tako velikih matrik, da bi se splačalo uporabiti CW ;)
Lp, R.
(c) nisem patentiran
Zgodovina sprememb…
- spremenil: modicr ()
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | LatexOddelek: Pomoč in nasveti | 2129 (911) | Invictus |
| » | Pomoc pri Kompleknih stevilihOddelek: Šola | 2847 (2345) | technolog |
| » | matematika dokaz boljšega približkaOddelek: Šola | 1879 (1674) | gojcic |
| » | Matematika/Logika - teoretični pristopOddelek: Šola | 3506 (3229) | Tim Burton |
| » | vektorji nalogaOddelek: Šola | 2174 (2002) | PaX_MaN |