マトリックス乗算分治アルゴリズムの擬似コード

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版の中国語版から選ぶ