Strassen's algorithm for matrix multiplication

簡單的比較 一般的矩陣運算 以及 Strassen's algorithm

{ r s }   { a b }   { e f }
{ t u } = { c d } * { g h }

一般的矩陣運算: Θ(n^3)
r = ae + bg
s = af + bh
t = ce + dg
u = cf + dh
總共 4 個加法運算 8 個乘法運算

Strassen's algorithm: Θ(n^lg7)
P1 = a * ( f - h )
P2 = ( a + b ) * h
=> s = P1 + P2
P3 = ( c + d ) * e
P4 = d * ( g - e )
=> t = P3 + P4
P5 = ( a + d ) * ( e + h )
P6 = ( b - d ) * ( g + h )
=> r = P5 + P4 - P2 + P6
P7 = ( a - c ) * ( e + f )
=> u = P5 + P1 - P3 - P7
總共 18 個加法運算 7 個乘法運算

在一般的 CPU 中乘法所需的運算量較大，所以才會造成 Strassen's algorithm 比較快 (應該吧?)