CSC-325 Analysis of Algorithms

Section 4.1 – Matrix Multiplication

Besides evaluating polynomials as we did in the last section, the other BIG number crunching activity in programming comes in multiplying matrices (singular = matrix). A matrix is nothing more than a two dimensional array, one with rows and columns.

Consider the following two matrices (or) arrays:

A =

1	0	-1
2	3	0

This array has 2 rows and 3 columns

and

B =

1	0	-1	-1
2	0	2	1
3	3	5	-2

This array has 3 rows and 4 columns

When we multiply A x B, we will get an array C that has 2 rows and 4 columns

The entries of C are obtained by cross-multiplying the i-th row with the j-th column.

For example for the C[1][1] position, we cross multiply the 1^st row from A with the 1^st column from B, i.e.

C[1][1] = 1*1 + 0*2 + (-1)*3 = -2

In this way we should get the final answer as:

C =

-2	-3	-6	1
8	0	4	1

In general when multiplying matrices, the number of columns in the first matrix must be the same as the number of rows in the second matrix or the multiplication will not work. For example a 3 x 7 matrix multiplied by a 7 x 5 matrix will yield a 3 x 5 matrix.

If we were multiplying an a x b matrix by a b x c matrix, a reasonable way of coding this algorithm would be as follows:

for i = 1 to a do

for j = 1 to c do

R[i][j] = 0

For k = 1 to b do

R[i][j] = R[i][j] + A[i][k] * B[k][j]

End for k

End for j

End for i

Consider a 3x7 matrix multiplied by a 7x5 matrix. How many multiplications and additions does the above algorithm do?

Can we do better?

4.2.1 Winograd’s Matrix multiplication.

A vector is just a series of numbers. For example :

V = (3, 2, 0, -1)

If two vectors are of the same size, then their “dot-product” is defined to be:

V = (v1,v2,v3,v4) W = (w1,w2,w3,w4)

V.W = v1*w1 + v2*w2 + v3*w3 + v4*w4

This looks very close to what we were doing to cross-multiply a row of one matrix with the column of another matrix.

Now let’s look at the dot product another way:

V.W = (v1+w2)*(v2+w1) + (v3+w4)*(v4+w3) – v1*v2 – v3*v4 – w1*w2 – w3*w4

Can you convince yourself that the two formulas for V.W are the same?

It looks like this formula actually does more work, but it is useful. Here is the algorithm for Winograd’s matrix multiplication. We will multiply a matrix G ( a x b) by a matrix H ( b x c ) to obtain a matrix R ( a x c ):

d = b/2

//calculate rowFactors for G

for i = 1 to a do

rowFactor[i] = G[i][1] * G[i][2]

for j = 2 to d do

rowFactor[i] = rowFactor[i] + G[i][2j-1] * G[i][2j]

end for j

end for I

//calculate column factors for H

for i = 1 to c do

columnFactor[i] = H[1][i] * H[2][i]

for j = 2 to d do

columnFactor[i] = columnFactor[i] + H[2j-1][i]*H[2j][i]

end for j

end for i

//calculate R

for i = 1 to a do

for j = 1 to c do

R[i][j] = -rowFactor[i] – columnFactor[j]

For k = 1 to d do

R[i][j] = R[i][j] + (G[i][2k-1] + H[2k][j])*(G[i][2k] + H[2k-1][j])

end for k

end for j

end for i

//add in terms for odd shared dimension

if(2*(b/2) != b) then

for i = 1 to a do

for j = 1 to c do

R[i][j] = R[i][j] + G[i][b]*H[b][j]

end for j

end for i

end if

Let’s try this with an example is class!

With Winograd’s method we can reduce the number of multiplications and additions, usually.

Suppose you were multiplying an NxN matrix and another NxN matrix to give you an NxN matrix, then the number of arithmetic operations on the standard method and Winograd’s method is given below.

	Multiplications	Additions
Standard Algorithm	N^3	N^3 – N^2
Winograd’s Algorithm	(N^3 + 2N^2) / 2	(3N^3 + 4N^2 – 4N) / 2

Is Winograd’s method better?

4.3 Linear Equations and Gauss-Jordan Method

You are probably all familiar with solving simple linear equations of the form

3x + 2y = 1

2x – 2y = 9

There are many ways of doing this but the simplest way for the above two equations is to add them together getting:

5x = 10 or x = 2

Now substitute the 2 in for x, giving

3*2 + 2y = 1

6 + 2y = 1

2y = -5

y = -5/2

But what do we do about systems of equations in several unknowns? Consider the example in your text.

2x1 + 7x2 + 1x3 + 5x4 = 70

1x1 + 5x2 + 3x3 + 2x4 = 45

3x1 + 2x2 + 4x3 + 1x4 = 33

8x1 + 1x2 + 5x3 + 3x4 = 56

Now we have four equations in four unknowns!

We can however represent this set of equations in a matrix, as follows:

2	7	1	5	70
1	5	3	2	45
3	2	4	1	33
8	1	5	3	56

The Gauss-Jordan method says that if we can follow certain rules and get the matrix to eventually look like this:

1	0	0	0	X1
0	1	0	0	X2
0	0	1	0	X3
0	0	0	1	X4

Then the X1, X2, X3 and X4 values will be a solution to our original set of equations.

Do get this matrix to the form in which we want it, we can follow only a few rules:

a. multiply a row by a constant

b. multiply a row by a constant and add the elements to another row.

Look back at the original matrix:

2	7	1	5	70
1	5	3	2	45
3	2	4	1	33
8	1	5	3	56

If we multiply row 1 by 0.5 we get

1	3.5	0.5	2.5	35
1	5	3	2	45
3	2	4	1	33
8	1	5	3	56

Well, at least we have a 1 in the top left corner as desired.

Now multiply row 1 by a –1 and add it’s elements to the second row

1	3.5	0.5	2.5	35
0	1.5	2.5	-0.5	10
3	2	4	1	33
8	1	5	3	56

Now multiply the first row by a –3 and add it to the third row, then multiply the first row by a –8 and add it to the last row. We get:

1	3.5	0.5	2.5	35
0	1.5	2.5	-0.5	10
0	-8.5	2.5	-6.5	-72
0	-27	1	-17	-224

Hmm, it seems to be getting messy, but we do have the first column the way we want it.

Now multiply the second row by a 1/1.5. This gives

1	3.5	0.5	2.5	35
0	1	1.67	-0.33	6.67
0	-8.5	2.5	-6.5	-72
0	-27	1	-17	-224

Aha! We have another 1 in the right place. Now we can multiply it by various numbers and add the elements to the other rows to zero out some more stuff.

We continue this way, forcing ones and zeros where we need them and at the end we will be left with:

1	0	0	0	2
0	1	0	0	4
0	0	1	0	3
0	0	0	1	7

This means that x1=2, x2=4, x3=3 and x4=7 is a solution to our original set of equations.

Your assignment for this chapter will be a programming assignment. We will work on this assignment during the next class period. Your assignment can be found from the link on the previous page.