Winogradovo množenje matrik

Iz MaFiRaWiki

Dani sta matriki A in B velikosti n \times n. Produkt matrik A in B je matrika C=A \cdot B velikosti n \times n, s členi:

c_{ij}= \sum_{k=1}^{n} (A_{ik} \cdot B_{kj})

Najpreprostejši algoritem izračuna po vrsti vseh n2 elementov cij po definiciji standardnega množenja matrik. Njegova časovna zahtevnost je O(n3) in sicer imamo n3 seštevanj in n3 množenj. Obstajajo pa boljši algoritmi za množenje dveh matrik in eden izmed takšnih je Winogradov algoritem.

Winogradov algoritem zmanjša število množenj za približno 50%, toda asimptotično je še vedno O(n3). Shmuel Winograd-a je zanimalo ali se da matriki velikosti n \times n zmnožiti z manj kot n3 množenji in odkril je naslednji algoritem. Naj bo n sodo število (če ni, ga povečaj za 1, matriki A in B pa povečaj za prazno vrstico in stolpec). Izračunajmo:

X_{i,k,j}=(A_{i,2k-1}+B_{2k,j}) \cdot (B_{2k-1,j}+A_{i,2k})
Y_{i,k}=A_{i,2k-1} \cdot A_{i,2k}
Z_{k,j}=B_{2k,j} \cdot B_{2k-1,j},

kjer je 1 \leq i,j \leq n in 1 \leq k \leq \frac{n}{2}. Sedaj uporabimo Xi,k,j,Yi,k,Zk,j za raunanje členov cij na naslednji način:

c_{ij}= \sum_{k=1}^{\frac{n}{2}}(X_{ikj}-Y_{ik}-Z_{kj})

Preverimo:

c_{ij}= \sum_{k=1}^{\frac{n}{2}}(X_{ikj}-Y_{ik}-Z_{kj})=
= \sum_{k=1}^{\frac{n}{2}}(A_{i,2k-1}B_{2k-1,j}+A_{i,2k-1}A_{i,2k}+B_{2k,j}B_{2k-1,j}+B_{2k,j}A_{i,2k}-A_{i,2k-1}A_{i,2k}-B_{2k,j} \cdot B_{2k-1,j})=
= \sum_{k=1}^{\frac{n}{2}} (A_{i,2k-1}B_{2k-1,j}+B_{2k,j}A_{i,2k})=
= \sum_{k=1}^{\frac{n}{2}}(A_{i,2k-1}B_{2k-1,j}+A_{i,2k}B_{2k,j})=
= \ldots =
= \sum_{l=1}^{n} (A_{il}B_{lj})

Časovna zahtevnost

Za izračun Xikj,Yik,Zkj potrebujemo:

  1. \frac{1}{2} n^{3}+n^{2} množenj
  2. n3 + 3n22n seštevanj

Opomba

Implementacija tega algoritma na rekurziven način je lahko problematična, ker algoritem predvideva, da je množenje komutativno, kar pa seveda ne velja za vse matrike.

Glej tudi

Osebna orodja