■行列の計算(その1)

 行列に関する計算でもかけ算は足し算よりも計算がかなり大変なのでかけ算の回数を減らすことは重要である.1969年,シュトラッセンはN×Nの行列の積を計算するのにかけ算の回数をN^3からN^2.8回に減らす方法を開発した.

 これはN=2^nの場合で,log27=2.8であるという.

===================================

【1】シュトラッセン法

A=[a11,a12]  B=[b11,b12]

  [a21,a22]    [b21,b22]

C=[a11b11+a12b21,a11b12+a12b12]

  [a21b11+a22b21,a21b12+a22b22]

 2次の正方行列2つの積を求めるのに,普通は8回のかけ算(と4回の足し算)が必要であるが,7回ですませる方法がある.

 この方法は交換法則にはよらないので,N×N行列をブロックに分けて効率よくやれば,O(N^log2N)回のかけ算でできる.

[参]V. Strassen: Gaussian elimination is not optimal, Numer Math 13,1969

===================================

【2】ラダーマン法

 3次の正方行列2つの積を求めるのに,普通は27回のかけ算(と4回の足し算)が必要であるが,23回ですませる方法がある.

 だが,これはシュトラッセンの方法を改良したことにはなっていない.

[参]J. Laderman: A non-cummulative algorithm for multiplying 3x3 matrices using 23 multiplications, Bull Amer Math Soc 82, 1976

===================================