Java Reference
In-Depth Information
observations to speed things up further? And even if we do find a way to evaluate
many points quickly, we will also need to interpolate the five values to get the
coefficients of AB back.
So we see that we could multiply two polynomials in less than (n
2
) operations
if a fast way could be found to do evaluation/interpolation of 2n1 points. Before
considering further how this might be done, first observe again the relationship
between evaluating a polynomial at values c and c. In general, we can write
P
a
(x) = E
a
(x) + O
a
(x) where E
a
is the even powers and O
a
is the odd powers.
So,
n=21
n=21
X
X
a
2i
x
2i
+
a
2i+1
x
2i+1
P
a
(x) =
i=0
i=0
The significance is that when evaluating the pair of values c and c, we get
E
a
(c) + O
a
(c)
= E
a
(c) O
a
(c)
O
a
(c)
= O
a
(c)
Thus, we only need to compute the Es and Os once instead of twice to get both
evaluations.
The key to fast polynomial multiplication is finding the right points to use for
evaluation/interpolation to make the process efficient. In particular, we want to take
advantage of symmetries, such as the one we see for evaluating x and x. But we
need to find even more symmetries between points if we want to do more than cut
the work in half. We have to find symmetries not just between pairs of values, but
also further symmetries between pairs of pairs, and then pairs of pairs of pairs, and
so on.
Recall that a complex number z has a real component and an imaginary compo-
nent. We can consider the position of z on a number line if we use the y dimension
for the imaginary component. Now, we will define a primitive nth root of unity if
1. z
n
= 1 and
2. z
k
6= 1 for 0 < k < n.
z
0
;z
1
;:::;z
n1
are called the nth roots of unity. For example, when n = 4, then
z = i or z = i. In general, we have the identities e
i
= 1, and z
j
= e
2ij=n
=
1
2j=n
. The significance is that we can find as many points on a unit circle as we
would need (see Figure 16.6). But these points are special in that they will allow
us to do just the right computation necessary to get the needed symmetries to speed
up the overall process of evaluating many points at once.
The next step is to define how the computation is done. Define an nn matrix
A
z
with row i and column j as
A
z
= (z
ij
):
