■行列の計算(その3)
A=[a11,a12] B=[b11,b12]
[a21,a22] [b21,b22]
C=[a11b11+a12b21,a11b12+a12b12]
[a21b11+a22b21,a21b12+a22b22]
2次の正方行列2つの積を求めるのに,普通は8回のかけ算(と4回の足し算)が必要であるが,7回ですませる方法がある.
[参]チャンバーランド「ひとけたの数に魅せられて」岩波書店
===================================
【1】シュトラッセン法
次の7つの式には,それぞれひとつずつのかけ算が含まれている.
m1=(a11+a22)(b11+b22)
m2=(a21+a22)b11
m3=a11(b12−b22)
m4=a22(b21−b11)
m5=(a11+a12)b22
m6=(a21−a11)(b11+b12)
m7=(a12−a22)(b21+b22)
c11=a11b11+a12b21=m1+m4−m5+m7
c12=a11b12+a12b12=m3+m5
c21=a21b11+a22b21=m2+m4
c22=a21b12+a22b22=m1−m2+m3+m6
8回のかけ算(と4回の足し算)→7回のかけ算(と18回の足し算引き算)によって,行列の積を計算できるというわけである.
===================================