Strassen’s matrix multiplication using Divide & Conquer technique.
Strassen’s matrix multiplication
using Divide & Conquer technique:
Description :
Strassen’s algorithm is used for matrix multiplication. It is asymptotically faster than the
standard matrix multiplication algorithm
ALGORITHM using Divide & Conquer method:
Let A & B be two square matrices.
C= A * B
We have,
Where:
M1 = (A00 + A11) * (B00 + B11)
M2 = (A10 + A11) * B00
M3 = A00 * (B01 – B11)
M4 = A11 * (B10 – B00)
M5 = (A00 + A01) * B11
M6 = (A10 – A00) * (B00 + B01)
M7 = (A01 – A11) * (B10 + B11)
Analysis:
• Input size: n – order of square matrix.
• Basic operation:
o Multiplication (7)
o Addition (18)
o Subtraction (4)
• No best, worst, average case
• Let M(n) be the number of multiplication’s made by the algorithm, Therefore we have:
M (n) = 7 M(n/2) for n > 1
M (1) = 1
Comments
Post a Comment