Analysis of Algorithms : An Active Learning Approach

106 NUMERIC ALGORITHMS

method and calculate the preprocessed coefficients for the polynomials x^3 +

4 x^2 
 3 x + 2 and x^7 
 8 x^6 + 3x^5 + 2x^4 
 4 x^3 + 5x
 7. You should trace the

standard matrix multiplication algorithm, Winograd's matrix multiplication

algorithm, and Strassen's matrix multiplication with

You should trace the Gauss-Jordan method with the equations 3x 1 + 9x 2 + 6x 3 =

21, 5x 1 + 3x 2 + 22x 3 = 23, and 2x 1 + 8x 2 + 7x 3 = 26. You should also try to

answer any questions before reading on. A hint or the answer is in the sen-

tences following the question.

athematical calculation forms the basis for a wide range of pro-

grams. Computer graphics and vision both require a large number

of calculations involving polynomials and matrices. Because these

are typically done for each location in an image, small improvements can have

a great impact. A typical image can be created with 1024 pixels per row and

1024 pixels per column. Improving the calculation for each of these locations

by even one multiplication would reduce the creation of this image by

1,048,576 multiplications overall. So, even though the techniques in this chap-

ter don't seem to show a dramatic improvement, the real savings come from

the number of times that these are used.

Some software will repeatedly evaluate complex polynomial equations. This

can be part of a monitoring task where input from an external device is the

value “plugged into” the equation, and the result tells if there is some condi-

tion that needs attention. Another application is trigonometric functions. What

most programmers do not realize is that standard trigonometric functions like

sine and cosine have power series expansions that take the form of polynomial

equations, and it is these equations that a computer will use when calculating

trigonometric function results. These calculations need to be fast, and so, we

begin by looking at methods for more rapidly calculating polynomials.

Matrix multiplication plays a role in a number of applications. Models of

physical objects for computer graphics and computer-aided design and manu-

14

58

and^67

32

M