Dedicated web hosting - 4.6.4 EVALUATION OF POLYNOMIALS 493 treating the subscripts
4.6.4 EVALUATION OF POLYNOMIALS 493 treating the subscripts modulo n, since tijk = 1 if and only if i + j = k (modulo n). Thus if (ail), (bjl), (ckl ) is a realization of the cyclic convolution, so is (C&l), (b-j,l), (ail); in particular, we can realize (61) by transforming (64) into Now all of the complicated scalars appear in the A matrix. This is important in practice, since we often want to compute the convolution for many values of yo, yl, y2, ys but for a fixed choice of Q,, ~1, ~2, 5s. In such a situation, the arithmetic on x s can be done once and for all, and we need not count it. Thus (66) leads to the following scheme for evaluating the cyclic convolution WJO, 201, w2, w3 when x0, x1, x2, x3 are known in advance: 31 = Yo +y2, s2 = Yl + y3, $3 = 31 + s2, s4 = Sl -s2, s5 = Yo -Y2, 36 = Y3 -Yl, 37 = +j -~96; ~0+~1+~2+~3 =3-zl+zZ-Q ~O+~l–zZ–zS ml = 4. ~3, m2 = 4~ ~4, m3 = 2 . ~5, m4 = —~o+~l+~r-% . sg, m5 = y . ST; tl=ml+m2, t2=m3+m5, t3=ml–2, t4=m4-m5; wo = t1 + t2, Wl = t3+t4, w2 = t1 -t2, w3 = t3 -t4. (67) There are 5 multiplications and 15 additions, while the definition of cyclic con- volution involves 16 multiplications and 12 additions. We will prove later that 5 multiplications are necessary. Going back to our original multiplication problem (52), using (60), we have derived the realization This scheme uses one more than the minimum number of chain multiplications, but it requires far fewer parameter multiplications than (55). Of course, it must be admitted that the scheme is still rather complicated: If our goal is simply to compute the coefficients ~0, zl, . . . , 25 of the product of two given polyno- mials (x0 + xru + xzu2)(y~ + yru + yzu2 + ysu3), as a one-shot problem, our best bet is still to use the obvious method that does 12 multiplications and 6 additions-unless (say) the x s and y s are matrices. Note that if the x s are fixed as the y s vary, the new scheme does the evaluation with 7 multiplications and 17 additions. Even though (68) isn t especially useful as it stands, our derivation has