Nasobeni matic

NÁSOBENÍ MATIC

Je-li A. matice řádu M krát N, B. matice řádu N krát R a C. matice řádu M krát R, pak nasobení matic C.= A.*B. je definováno:

do I = 1 to M
  do K = 1 to R
    C.I.K = 0
    do J = 1 to N
      C.I.K = C.I.K + A.I.J * B.J.K
    end
  end
end

Pro výpočet součinu matice je zapotřebí M*N*R násobení. Efektivnější algoritmus, který potřebuje jen FORMAT(N/2,,0)*M*R+(N%2)*(M+R) násobení (tj. asi o polovinu méně), objevil Shmuel Winograd.

ALGORITMUS

Liche = N // 2
do K = 1 to R
  Y.K = 0
  do J = 1 to N % 2
    JpJ = J + J; JpJm1 = JpJ - 1
    Y.K = Y.K + B.JpJm1.K * B.JpJ.K
  end
end
do I = 1 to M
  X = 0
  do J = 1 to N % 2
    JpJ = J + J; JpJm1 = JpJ - 1
    X = X + A.I.JpJ * A.I.JpJm1
  end
  do K = 1 to R
    C.I.K = 0
    if Liche then Z = A.I.N * B.N.K
             else Z = 0
    do J = 1 to N % 2
      JpJ = J + J; JpJm1 = JpJ - 1
      C.I.K = C.I.K + (A.I.JpJ + B.JpJm1.K) *,
                      (A.I.JpJm1 + B.JpJ.K)
    end J
    C.I.K = C.I.K - X - Y.K + Z
  end K
end I

POROVNÁNÍ
Použil jsem následující program pro hodnoty Nd=10,100,200

parse arg Nd; numeric digits Nd
M = 20; N = 20; R = 20
A. = 1 / 3; B. = 1 / 3
/* následují výše uvedené fragmenty kódu */
...

Výsledky testu

Doba běhu v sekundách pro M = 20, N = 20, R = 20
Algoritmus Nd = 10 Nd = 100 Nd = 200

definice 0.93 23.13 90.13

Winograd 0.33 13.78 49.76

Literatura
Knuth D. E., Seminumerical Algorithms, vol. 2 of The Art of Computer Programming

Addison-Wesley, 1973