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,

image

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

image

Comments

Popular posts from this blog

Data Structure Visualization:Introduction and Value of Data Structure Rendering

Binary Space Partitioning Trees:BSP Tree as a Hierarchy of Regions.

Drawing Trees:HV-Layout