Back to Course


0% Complete
0/82 Steps
  1. Getting Started with Algorithm
    What is an Algorithm?
  2. Characteristics of Algorithm
    1 Topic
  3. Analysis Framework
  4. Performance Analysis
    3 Topics
  5. Mathematical Analysis
    2 Topics
  6. Sorting Algorithm
    Sorting Algorithm
    10 Topics
  7. Searching Algorithm
    6 Topics
  8. Fundamental of Data Structures
  9. Queues
  10. Graphs
  11. Trees
  12. Sets
  13. Dictionaries
  14. Divide and Conquer
    General Method
  15. Binary Search
  16. Recurrence Equation for Divide and Conquer
  17. Finding the Maximum and Minimum
  18. Merge Sort
  19. Quick Sort
  20. Stassen’s Matrix Multiplication
  21. Advantages and Disadvantages of Divide and Conquer
  22. Decrease and Conquer
    Insertion Sort
  23. Topological Sort
  24. Greedy Method
    General Method
  25. Coin Change Problem
  26. Knapsack Problem
  27. Job Sequencing with Deadlines
  28. Minimum Cost Spanning Trees
    2 Topics
  29. Single Source Shortest Paths
    1 Topic
  30. Optimal Tree Problem
    1 Topic
  31. Transform and Conquer Approach
    1 Topic
  32. Dynamic Programming
    General Method with Examples
  33. Multistage Graphs
  34. Transitive Closure
    1 Topic
  35. All Pairs Shortest Paths
    6 Topics
  36. Backtracking
    General Method
  37. N-Queens Problem
  38. Sum of Subsets problem
  39. Graph Coloring
  40. Hamiltonian Cycles
  41. Branch and Bound
    2 Topics
  42. 0/1 Knapsack problem
    2 Topics
  43. NP-Complete and NP-Hard Problems
    1 Topic
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).

KodNest Capture41

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

KodNest Capture42
Formulas (a) & (b)

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

KodNest Capture43

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.

KodNest Capture44
Formula (c), (d) & (e)

New Report