Analysis of Algorithms : An Active Learning Approach

116 NUMERIC ALGORITHMS

Strassen’s algorithm is rarely used in actual practice because of the book-

keeping necessary to use it recursively. Its importance is that it was the first

algorithm for multiplying matrices that was faster than the O(N^3 ) algorithms.

Improving the efficiency of matrix multiplication and perhaps identifying a

lower bound continues to be an active area of research.

4.2.3

1. How many multiplications and additions are done by Winograd’s algorithm
   for an odd value of the shared dimension?


2. Show that Strassen’s algorithm works by using it to multiply the two matri-
   ces

Compare the result with that of the standard algorithm. Show all work.

4.3 Linear Equations

A system of linear equations is a set of N equations with N unknown quanti-

ties. Typically these equations are written as

These equations can come from a number of sources, but typically the con-

stants (represented by the a coefficients) are some settings on equipment that

give the indicated results (represented by the b values in the equations). We are

interested in knowing what values of the unknowns (represented by the x val-

ues) will produce these results. Consider the following example:

■4.2.3 EXERCISES

19

73

and^52

411

a 11 x 1 ++++a 12 x 2 a 13 x 3 ... a 1 NxN= b 1

a 21 x 1 ++++a 22 x 2 a 23 x 3 ... a 2 NxN= b 2




aN 1 x 1 ++++aN 2 x 2 aN 3 x 3 ... aNNxN = bN

2 x 1 +++ 7 x 2 1 x 3 5 x 4 = 70

1 x 1 +++ 5 x 2 3 x 3 2 x 4 = 45

3 x 1 +++ 2 x 2 4 x 3 1 x 4 = 33

8 x 1 +++ 1 x 2 5 x 3 3 x 4 = 56