chap patterns of algorithms at the nth roots of unity by multiplying the az matrix by the coefficient vector the resulting vector fz is called the discrete fourier transform for the polynomial fz az bi - ak ik = when then sothe corresponding matrix is as follows - - - - - - - - - - az - - - - - - - - - - - - - - we still have two problems we need to be able to multiply this matrix times the vector faster than just by performing standard matrix-vector multiplicationotherwise the cost is still multiplies to do the evaluation theneven if we can multiply the two cheaplywe still need to be able to reverse the process that isafter transforming the two input polynomials by evaluating themand then pairwise multiplying the evaluated pointswe 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 fz- - = we need to find - this turns out to be simple to computeand is defined as follows - / in other wordsinterpolation (the inverse transformationrequires the same computation as evaluationexcept that we substitute / for (and multiply by / at the endsoif we can do one fastwe can do the other fast if you examine the example az matrix for you should see that there are symmetries within the matrix for examplethe top half is identical to the