■加減法(その10)

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回の足し算引き算)によって,行列の積を計算できるというわけである.

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