Java Reference
In-Depth Information
otherwise the cost is still n
2
multiplies to do the evaluation. Even if we can mul-
tiply the matrix and vector cheaply, we still need to be able to reverse the process.
That is, after transforming the two input polynomials by evaluating them, and then
pair-wise multiplying the evaluated points, we must interpolate those points to get
the resulting polynomial back that corresponds to multiplying the original input
polynomials.
The interpolation step is nearly identical to the evaluation step.
F
1
z
= A
1
z
b
0
= a
0
:
We need to find A
1
z
. This turns out to be simple to compute, and is defined as
follows.
=
1
A
1
n
A
1=z
:
In other words, interpolation (the inverse transformation) requires the same com-
putation as evaluation, except that we substitute 1=z for z (and multiply by 1=n at
the end). So, if we can do one fast, we can do the other fast.
If you examine the example A
z
matrix for n = 8, you should see that there
are symmetries within the matrix. For example, the top half is identical to the
bottom half with suitable sign changes on some rows and columns. Likewise for the
left and right halves. An efficient divide and conquer algorithm exists to perform
both the evaluation and the interpolation in (n log n) time. This is called the
Discrete Fourier Transform (DFT). It is a recursive function that decomposes
the matrix multiplications, taking advantage of the symmetries made available by
doing evaluation at the nth roots of unity. The algorithm is as follows.
z
FourierTransform(double
*
Polynomial,intn){
//ComputetheFouriertransformofPolynomial
//withdegreen.Polynomialisalistof
//coefficientsindexedfrom0ton-1.nis
//assumedtobeapowerof2.
doubleEven[n/2],Odd[n/2],List1[n/2],List2[n/2];
if(n==1)returnPolynomial[0];
for(j=0;j<=n/2-1;j++){
Even[j]=Polynomial[2j];
Odd[j]=Polynomial[2j+1];
}
List1=FourierTransform(Even,n/2);
List2=FourierTransform(Odd,n/2);
for(j=0;j<=n-1,J++){
Imaginaryz=pow(E,2
*
i
*
PI
*
j/n);
k=j%(n/2);
Polynomial[j]=List1[k]+z
*
List2[k];
}
returnPolynomial;
}
