Strassen's Matrix Multiplication

(A Divide and Conquer approach)

 Basic Matrix Multiplication

Suppose we want to multiply two matrices of size

N x N: for example A x B = C.

C11 = a11b11 + a12b21

C12 = a11b12 + a12b22
C21 = a21b11 + a22b21
C22 = a21b12 + a22b22
 Basic Matrix Multiplication

void matrix_mult (){

for (i = 1; i <= M; i++) {
for (j = 1; j <= N; j++) { algorithm
for (k = 1; k <= M; k++) {
C[i][j]+=A[i][k]*B[k][j];
}
}
}}
N
Ci , j =  ai ,k bk , j
k =1

Time analysis N N N
Thus T ( N ) =  c = cN 3 = O( N 3 )
i =1 j =1 k =1
 Strassens’s Matrix Multiplication

• Strassen showed that 2x2 matrix multiplication

can be accomplished in 7 multiplication and 18
additions or subtractions.(2log27 =22.807)

• This can be done by Divide and Conquer

Approach.
 Divide-and-Conquer

• Divide-and conquer is a general algorithm design

paradigm:
➢ Divide: divide the input data S in two or more disjoint
subsets S1, S2, …
➢ Recur: solve the subproblems recursively
➢ Conquer: combine the solutions for S1, S2, …, into a
solution for S
• The base case for the recursion are subproblems of
constant size
• Analysis can be done using recurrence equations
 Divide and Conquer Matrix Multiply

A  B = R
A0 A1 B0 B1 A0B0+A1B2 A0B1+A1B3
 =
A2 A3 B2 B3 A2B0+A3B2 A2B1+A3B3
Divide and Conquer Matrix Multiply

A  B = R
a0  b0 = a0  b0
 Strassens’s Matrix Multiplication

P1 = (A11+ A22)(B11+B22) C11 = P1 + P4 - P5 + P7

P2 = (A21 + A22) * B11 C12 = P3 + P5
P3 = A11 * (B12 - B22) C21 = P2 + P4
P4 = A22 * (B21 - B11) C22 = P1 + P3 - P2 + P6
P5 = (A11 + A12) * B22
P6 = (A21 - A11) * (B11 + B12)
P7 = (A12 - A22) * (B21 + B22)
 Comparison

C11 = P1 + P4 - P5 + P7
= (A11+ A22)(B11+B22) + A22 * (B21 - B11) - (A11 + A12) * B22+
(A12 - A22) * (B21 + B22)
= A11 B11 + A11 B22 + A22 B11 + A22 B22 + A22 B21 – A22 B11 -
A11 B22 -A12 B22 + A12 B21 + A12 B22 – A22 B21 – A22 B22

= A11 B11 + A12 B21

 Comparison

C12 = P3 + P5

= A11 * (B12 - B22) + (A11 + A12) * B22

= A11 B12 – A11 B22 + A11 B22 + A12 B22

= A11 B12 + A12 B22

 Comparison

C21 = P2 + P4

= (A21 + A22) * B11 + A22 * (B21 - B11)

= A21 B11 + A22 B11 + A22 B21 – A22 B11

= A21 B11 + A22 B21

 Comparison

C22 = P1 + P3 - P2 + P6

= (A11+ A22)(B11+B22) + A11 * (B12 - B22) - (A21 + A22) * B11

+ (A21 - A11) * (B11 + B12)

= A22 B22 + A21 B11

 Comparison

C11 = A11 B11 + A12 B21

C12 = A11 B12 + A12 B22

C21 = A21 B11 + A22 B21
C22 = A22 B22 + A21 B11
Only 7 multiplication required
Time Analysis
 Algorithm types

• Algorithm types we will consider include:

➢ Simple recursive algorithms
➢ Brute force algorithms
➢ Randomized algorithms
➢ Divide and conquer algorithms
➢ Greedy algorithms
➢ Dynamic Programming Algorithms
Dynamic Programming
 Dynamic Programming (DP)

• A method for solving Optimization Problem.

• Use when problem breaks down into recurring small

subproblems.

• Few examples of DP:

➢ 0-1 Knapsack problem
➢ All Pair Shortest Path
➢ Matrix Chain Multiplication
 Recall Divide and Conquer

• Divide the Problem into subproblems.

• Solve the sub problems.
• Combine the solutions to solve the original one.

• Remarks:
➢ these sub problems are independent.
➢ They did not call the same subproblems.
➢ If these problems are not independent then, then divide
and Conquer approach resolving many of the same
problems many times. Thus it does more work than
necessary.
 Dynamic programming

• It is used, when the solution can be recursively described in

terms of solutions to subproblems (optimal substructure).

• Dynamic Programming solve every subproblems exactly

once and is therefore more efficient in those cases where
subproblems are not independent.

• More efficient than “brute-force methods”, which solve the

same subproblems over and over again.
Dynamic Programming v/s divide-and-conquer

• Divide-and-conquer algorithms split a problem into

separate subproblems, solve the subproblems, and combine
the results for a solution to the original problem
➢ Example: Quicksort
➢ Example: Mergesort

• Divide-and-conquer algorithms can be thought of as top-

down algorithms.
• In contrast, a dynamic programming algorithm proceeds by
solving small problems, then combining them to find the
solution to larger problems.
• Dynamic programming can be thought of as bottom-up.
Dynamic Programming v/s divide and conquer

• Like divide-and-conquer, solve problem by combining the

solutions to sub-problems.

• Differences between divide-and-conquer and DP:

➢ Independent sub-problems, solve sub-problems
independently and recursively, (so same
sub(sub)problems solved repeatedly)

➢ Sub-problems are dependent, i.e., sub-problems share

sub-sub-problems, every sub(sub)problem solved just
once, solutions to sub(sub)problems are stored in a
table and used for solving higher level sub-problems.
 Dynamic Programming

• Dynamic Programming (DP) is a method of solving

Optimization Problems.

• In such problems there can be many possible solutions.

• Each solution has a value, and we wish to find a solution

with the optimal (minimum or maximum).

• Basic Idea: Compute the solution for subproblems once,

and store the solutions in a table so that they can be reused
(repeatedly) later.
Properties of a problem that can be solved with
dynamic programming

Simple Subproblems
➢ We should be able to break the original problem to smaller
subproblems that have the same structure.

Optimal Substructure
➢ The solution to the problem contains within it optimal
solutions to subproblems.

Whenever a problem exhibits optimal substructure, then

dynamic programming can be applied.
Properties of a problem that can be solved with
dynamic programming

➢ Dynamic programming uses optimal substructure in a

bottom up fashion.
Dynamic programming
0-1 Knapsack problem
 0-1 Knapsack problem

• Given a knapsack with maximum capacity W, and a set S

consisting of n items

• Each item i has some weight wi and benefit value bi (all wi

, bi and W are integer values)

• Problem: How to pack the knapsack to achieve maximum

total value of packed items?
 Knapsack problem
There are two versions of the problem:
(1) “0-1 knapsack problem” and
(2) “Fractional knapsack problem”

(1) Items are indivisible; you either take an item

or not. Solved with dynamic programming
(2) Items are divisible: you can take any fraction

of an item. Solved with a greedy algorithm.

 0-1 Knapsack problem:
an example
Weight Benefit value
wi bi
Items
2 3

4
This is a knapsack 3

4 5
Max weight: W = 20
5 8

W = 20

9 10
 0-1 Knapsack problem

• Problem, in other words, is to find

max  bi subject to  wi  W
iT iT

The problem is called a “0-1” problem, because each item

must be entirely accepted or rejected.
 0-1 Knapsack problem: brute-force
approach
Let’s first solve this problem with a straightforward algorithm

• Since there are n items, there are 2n possible combinations

of items.

• We go through all combinations and find the one with the

most total value and with total weight less or equal to W

• Running time will be O(2n)

 0-1 Knapsack problem: brute-force
approach

• Can we do better?

• Yes, with an algorithm based on dynamic

programming.

• We need to carefully identify the subproblems

 Recursive Formula
 B[k − 1, w] if wk  w
B[k , w] = 
max{B[k − 1, w], B[k − 1, w − wk ] + bk } else

• The best subset of Sk that has the total weight w, either

contains item k or not.

• First case: wk>w. Item k can’t be part of the solution,

since if it was, the total weight would be > w, which is
unacceptable.

• Second case: wk <=w. Then the item k can be in the

solution, and we choose the case with greater value.
 0-1 Knapsack Algorithm
for w = 0 to W
B[0,w] = 0
for i = 0 to n
B[i,0] = 0
for w = 0 to W
if wi <= w // item i can be part of the solution
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Running time
for w = 0 to W O(W)
B[0,w] = 0
for i = 0 to n Repeat n times
B[i,0] = 0
for w = 0 to W O(W)
< the rest of the code >
What is the running time of this algorithm?

O(n*W)
Remember that the brute-force algorithm
takes O(2n)
 Example

Let’s run our algorithm on the

following data:

n = 4 (# of elements)
W = 5 (max weight)
Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)
 Example (2)
i 0 1 2 3 4
W
0 0

1 0

2 0

3 0

4 0

5 0

for w = 0 to W
B[0,w] = 0
 Example (3)
i 0 1 2 3 4
W
0 0 0 0 0 0

1 0

2 0

3 0

4 0

5 0

for i = 0 to n
B[i,0] = 0
 Example (4) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0
i=1
2 0 bi=3 3: (4,5)
3 0
wi=2 4: (5,6)
4 0
w=1
5 0
w-wi =-1
if wi <= w // item i can be part of the solution
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (5) Items:
i 0 1 2 3 4 1: (2,3)
W
0 0 0 0 0 0 2: (3,4)
i=1
1 0 0 3: (4,5)
2 0 3 bi=3 4: (5,6)
3 0
wi=2
4 0
w=2
5 0
w-wi=0
if wi <= w // item i can be part of the solution
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (6) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0
i=1
2 0 3 bi=3 3: (4,5)
3 0 3
wi=2 4: (5,6)
4 0
w=3
5 0
w-wi=1
if wi <= w // item i can be part of the solution
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (7) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0
i=1
2 0 3 bi=3 3: (4,5)
3 0 3
wi=2 4: (5,6)
4 0 3
w=4
5 0
w-wi=2
if wi <= w // item i can be part of the solution
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (8) Items:
i 0 1 2 3 4 1: (2,3)
W
0 0 0 0 0 0 2: (3,4)
i=1
1 0 0 3: (4,5)
2 0 3 bi=3 4: (5,6)
3 0 3
wi=2
4 0 3
w=5
5 0 3
w-wi=2
if wi <= w // item i can be part of the solution
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (9) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0 0 i=2
2 0 3
3: (4,5)
bi=4
3 0 3 4: (5,6)
4 0 3 wi=3
5 0 3
w=1
if wi <= w // item i can be part of the solution
w-wi=-2
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (10) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0 0 i=2
2 0 3 3
3: (4,5)
bi=4
3 0 3 4: (5,6)
4 0 3 wi=3
5 0 3
w=2
if wi <= w // item i can be part of the solution
w-wi=-1
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (11) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0 0 i=2
2 0 3 3
3: (4,5)
bi=4
3 0 3 4 4: (5,6)
4 0 3 wi=3
5 0 3
w=3
if wi <= w // item i can be part of the solution
w-wi=0
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (12) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0 0 i=2
2 0 3 3
3: (4,5)
bi=4
3 0 3 4 4: (5,6)
4 0 3 4 wi=3
5 0 3
w=4
if wi <= w // item i can be part of the solution
w-wi=1
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (13) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0 0 i=2
2 0 3 3
3: (4,5)
bi=4
3 0 3 4 4: (5,6)
4 0 3 4 wi=3
5 0 3 7
w=5
if wi <= w // item i can be part of the solution
w-wi=2
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (14) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0 0 0 i=3
2 0 3 3 3
3: (4,5)
bi=5
3 0 3 4 4 4: (5,6)
4 0 3 4 wi=4
5 0 3 7
w=1..3
if wi <= w // item i can be part of the solution
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (15) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0 0 0 i=3
2 0 3 3 3
3: (4,5)
bi=5
3 0 3 4 4 4: (5,6)
4 0 3 4 5 wi=4
5 0 3 7
w=4
if wi <= w // item i can be part of the solution
w- wi=0
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (15) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0 0 0 i=3
2 0 3 3 3
3: (4,5)
bi=5
3 0 3 4 4 4: (5,6)
4 0 3 4 5 wi=4
5 0 3 7 7
w=5
if wi <= w // item i can be part of the solution
w- wi=1
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (16) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0 0 0 0 i=3
2 0 3 3 3 3
3: (4,5)
bi=5
3 0 3 4 4 4 4: (5,6)
4 0 3 4 5 5 wi=4
5 0 3 7 7
w=1..4
if wi <= w // item i can be part of the solution
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Example (17) Items:
i
W
0 1 2 3 4 1: (2,3)
0 0 0 0 0 0
2: (3,4)
1 0 0 0 0 0 i=3
2 0 3 3 3 3
3: (4,5)
bi=5
3 0 3 4 4 4 4: (5,6)
4 0 3 4 5 5 wi=4
5 0 3 7 7 7
w=5
if wi <= w // item i can be part of the solution
if bi + B[i-1,w-wi] > B[i-1,w]
B[i,w] = bi + B[i-1,w- wi]
else
B[i,w] = B[i-1,w]
else B[i,w] = B[i-1,w] // wi > w
 Comments

• This algorithm only finds the max possible value

that can be carried in the knapsack.

• To know the items that make this maximum value,

an addition to this algorithm is necessary.
Conclusion
• Dynamic programming is a useful technique
of solving certain kind of problems.
• When the solution can be recursively
described in terms of partial solutions, we
can store these partial solutions and re-use
them as necessary.
• Running time (Dynamic Programming
algorithm vs. naïve algorithm):
➢0-1 Knapsack problem: O(W*n) vs. O(2n)
More Dynamic Programming

Floyd-Warshall Algorithm
 Floyd-Warshall Algorithm
• A weighted, directed graph is a collection vertices
connected by weighted edges (where the weight is some
real number).
➢One of the most common examples of a graph in the
real world is a road map.
• Each location is a vertex and each road connecting
locations is an edge.
• We can think of the distance traveled on a road from one
location to another as the weight of that edge.

City 1 city 2 City 3 1.5

City 1 City 2
City 1 0 1.7 3.5 1.7

3.5
City 2 1.5 0 ∞ 4 2.5

City 3 4 2.5 0 City 3

Storing a Weighted, Directed Graph
• Adjacency Matrix:
➢ Let D be an edge-weighted graph in adjacency-matrix
form
• D(i,j) is the weight of edge (i, j), or  if there is no such
edge.
• Update matrix D, with the shortest path through
immediate vertices.

0 1 2 3
1
6 3
0 0 6 5 ∞ 0
4 3
D=
1 ∞ 0 4 3 5
2
2

2 ∞ ∞ 0 2
3 ∞ ∞ ∞ 0
 Floyd-Warshall Algorithm

• Given a weighted graph, we want to know the

shortest path from one vertex in the graph to
another.
➢ The Floyd-Warshall algorithm determines the shortest
path between all pairs of vertices in a graph.

➢ What is the difference between Floyd-Warshall and

Dijkstra’s??
 Floyd-Warshall Algorithm
•If V is the number of vertices, Dijkstra’s runs in
(V2)
➢ We could just call Dijkstra |V| times, passing a different
source vertex each time.
➢ (V  V2) = (V3)
➢ (Which is the same runtime as the Floyd-Warshall
Algorithm)

• BUT, Dijkstra’s doesn’t work with negative-weight

edges.
 Floyd Warshall Algorithm
• Let’s see how Floyd-Warshall algorithm works…
➢ Let the vertices in a graph be numbered from 1 … n.
➢ Consider the subset {1,2,…, k} of these n vertices.

➢ Imagine finding the shortest path from vertex i to vertex j that uses
vertices in the set {1,2,…,k} only.

➢ There are two situations:

1) k is an intermediate vertex on the shortest path.
2) k is not an intermediate vertex on the shortest path.

i j
 Dynamic Programming

Floyd-Warshall is a dynamic programming

algorithm:
Compute and store solutions to sub-
problems. Combine those solutions to
solve larger sub-problems.
Here, the sub-problems involve finding the shortest
paths through a subset of the vertices.
 A recursive solution to the all-pairs
shortest paths problem:

• Let dij(k) be the weight of a shortest path from vertex i to

vertex j with all intermediate vertices in the set {1,2,…,k}.
A recursive definition is given by

•

• dij(k)= wij
min(dij(k-1),dik(k-1)+dkj(k-1))
if k=0,
if k  1.

• The matrix D(n)=(dij(n)) gives the final answer-dij(n)=  (i, j )


for all i,j V-because all intermediate vertices are in the
set {1,2,…,n}.
 Computing the shortest-path weights
bottom up:

• FLOYD-WARSHALL(W)
• V  rows[W]
• 
D(0) W
• 
for k 1 to V
• do for i  1 to V
• do for j  1 to V
• 
dij(k) min(dij(k-1),dik(k-1)+dkj(k-1))

• return D(n)

73
Example:

2
4
3

1 3
8

1
-4 -5
7 2

5 4
6
  0 3 8  − 4
 
 0  1 7 
D(0)=
 4 0   
 
 2  −5 0  
   6 0 
 

 0 3 8  − 4
 
 0  1 7 
 4 0   
D(1)=  
 2 5 − 5 0 − 2
   6 0 
 
 0 3 8 4 − 4
 
 0  1 7 
D(2)=
 4 0 5 11 
 
 2 5 −5 0 − 2
   6 0 


0 3 8 4 − 4
 
 0  1 7 
 4 0 5 11 
D(3)=  
 2 −1 − 5 0 − 2
   6 0 

  0 3 −1 4 − 4
 
 3 0 − 4 1 −1 
D(4)=
7 4 0 5 3 
 
 2 −1 − 5 0 − 2
8 5 1 6 0 
 

 0 1 − 3 2 − 4
 
 3 0 − 4 1 −1 
7 4 0 5 3 
D(5)=  
 2 −1 − 5 0 − 2
8 5 1 6 0 

Time Complexity: Floyd Warshall Algorithm

• FLOYD-WARSHALL(W)
• V  rows[W]
• 
D(0) W
• 
for k 1 to V O(V)

• do for i  1 to V O(V)

• do for j  1 to V O(V)

• 
dij(k) min(dij(k-1),dik(k-1)+dkj(k-1))
• return D(n)

Total time taken is O(V3) where V is total number of Vertices in the graph
78