マトリックス乗算分治アルゴリズムの擬似コード
2438 ワード
SQUARE-MATRIX-MULTIPLY-RECURSIVE(A,B)
n=A.rows
let C be a new n*n matrix
if n==1
c11=a11*b11
else partition A, B and C as in equation(1)
C11=SQUARE-MATRIX-MULTIPLY-RECURSIVE(A11,B11)
+SQUARE-MATRIX-MULTIPLY-RECURSIVE(A12,B21)
C22=SQUARE-MATRIX-MULTIPLY-RECURSIVE(A11,B12)
+SQUARE-MATRIX-MULTIPLY-RECURSIVE(A12,B22)
C21=SQUARE-MATRIX-MULTIPLY-RECURSIVE(A21,B11)
+SQUARE-MATRIX-MULTIPLY-RECURSIVE(A22,B21)
C22=SQUARE-MATRIX-MULTIPLY-RECURSIVE(A21,B22)
+SQUARE-MATRIX-MULTIPLY-RECURSIVE(A22,B22)
return C
式1:
A=[A11A21A12A22],B=[B11B21B12B22],C=[C11C21C12C22](1)
アルゴリズムの導論の第3版の中国語版から選ぶ