 In Progress
Lesson 20 of 43
In Progress

# Stassen’s Matrix Multiplication

Let A and B be two n x n matrices. The product matrix C= AB is also an n x n matrix whose i,jth element is formed by taking the elements in the ith row of A and the jth column of Band multiplying them to get for all i and j between 1 and n. To compute C(i,j) using this formula, we need n multiplications.As the matrix C has n^2 elements,the time for the resulting matrix multiplication algorithm,which we refer to as the conventional method is theta(n^3).

The divide-and-conquer strategy suggests another way to compute the product of two n x n matrices. For simplicity we assume that n is a power of 2, that is,that there exists a non negative integer k such that n = 2^k. In case? i is not a power of two, then enough rows and columns of zero scan be added to both A and B so that the resulting dimensions area power of two (see the exercises for more on this subject). Imagine that A and B are each partitioned into four square sub matrices, each sub matrix having dimensions n/2*n/2. Then the product AB can be computed by using the above formula for the product of 2 x 2 matrices: if AB is