Algorithm
-
Getting Started with AlgorithmWhat is an Algorithm?
-
Characteristics of Algorithm1 Topic
-
Analysis Framework
-
Performance Analysis3 Topics
-
Mathematical Analysis2 Topics
-
Sorting AlgorithmSorting Algorithm10 Topics
-
Searching Algorithm6 Topics
-
Fundamental of Data StructuresStacks
-
Queues
-
Graphs
-
Trees
-
Sets
-
Dictionaries
-
Divide and ConquerGeneral Method
-
Binary Search
-
Recurrence Equation for Divide and Conquer
-
Finding the Maximum and Minimum
-
Merge Sort
-
Quick Sort
-
Stassen’s Matrix Multiplication
-
Advantages and Disadvantages of Divide and Conquer
-
Decrease and ConquerInsertion Sort
-
Topological Sort
-
Greedy MethodGeneral Method
-
Coin Change Problem
-
Knapsack Problem
-
Job Sequencing with Deadlines
-
Minimum Cost Spanning Trees2 Topics
-
Single Source Shortest Paths1 Topic
-
Optimal Tree Problem1 Topic
-
Transform and Conquer Approach1 Topic
-
Dynamic ProgrammingGeneral Method with Examples
-
Multistage Graphs
-
Transitive Closure1 Topic
-
All Pairs Shortest Paths6 Topics
-
BacktrackingGeneral Method
-
N-Queens Problem
-
Sum of Subsets problem
-
Graph Coloring
-
Hamiltonian Cycles
-
Branch and Bound2 Topics
-
0/1 Knapsack problem2 Topics
-
NP-Complete and NP-Hard Problems1 Topic
Participants2253
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

If n = 2, then formulas (a) and (b) are computed using a multiplication operation for the elements of A and B. These elements are typically floating point numbers. For n > 2, the elements of C can be computed using matrix multiplication and addition operations applied to matrices of size n/2 * n/2. Since n is a power of 2, these matrix products can be recursively computed by the same algorithm we are using for the n*n case. This algorithm will continue applying itself to smaller-sized sub matrices until n becomes suitably small(n = 2) so that the product is computed directly.
To compute AB using (3.12), we need to perform eight multiplications of n/2*n/2 matrices and four additions of n/2*n/2 matrices. Since two n/2*n/2 matrices can be added in time cn^2 for some constant c,the overall computing time T(n) of the resulting divide-and-conquer algorithm is given by the recurrence

where b and c are constants.
This recurrence can be solved in the same way as earlier recurrences to obtain T(n)= 0(n^3). Hence no improvement over the conventional method has been made. Since matrix multiplications are more expensive than matrix additions (0(n^3) versus 0(n^2)),we can attempt to reformulate the equations for Cij so as to have fewer multiplications and possibly more additions. Volker Strassen has discovered a way to compute the Cij’s of (formula b) using only 7 multiplications and 18 additions or subtractions. His method involves first computing the seven n/2*n/2 matrices P, Q, R, S, T, U, and V as in (formula c).Then the Cij’s are computed using the formulas in (formula d). As can be seen P, Q, R, S, T, U, and V can be computed using 7 matrix multiplications and 10 matrix additions or subtractions. The Cij’s require an additional 8 additions or subtraction.
