4.1 CALCULATING POLYNOMIALS 107
facturing can be moved and manipulated through matrix operations. Image
analysis will use matrices in convolution operations to improve the quality of
an image and to identify the bounds of objects in a picture. Fourier analysis
will describe complex wave patterns in terms of simpler sine waves through
matrix manipulation.
The common issue in all of these cases is that the matrix operations are
done frequently, and so faster matrix multiplication results in faster programs.
Object transformations use 4 4 matrices, convolutions can use square matri-
ces from 3 3 up to 11 11 or bigger, but they are used a very large number
of times. Convolutions, for example, will take a matrix and multiply it by blocks
of pixels in an image for every possible location. This means that for a 5 5
template used with a small image of 512 512 pixels (about one-quarter of a
typical computer screen), a convolution will multiply this matrix by 258,064
different locations (508 508). If the standard matrix multiplication algorithm
is used, this will result in 32,258,000 multiplications. A more efficient matrix
multiplication algorithm can save significant time in this application.
In this chapter we will investigate ways to make polynomial evaluation and
matrix multiplication more efficient. Because we are interested in how many
calculations are done, we will be counting additions and multiplications. When
we considered searching and sorting, we found equations that were based on
the size of the list. In analyzing numeric algorithms, we will base our equations
on the power of the highest order term in a polynomial equation, or the
dimensions of the matrices we are multiplying.
4.1 Calculating Polynomials
For our discussion of polynomial evaluation, we will use a generic polynomial
of the form
p(x) = anxn + an 1 xn^1 + an 2 xn^2 + ... + a 2 x^2 + a 1 x + a 0 (4.1)
We will assume that the coefficient values of an through a 0 are all known, con-
stant, and will be stored in an array. This means that our evaluation of a poly-
nomial has only the value of x as its input and will return the resulting
polynomial value as its output.
