490 ARITHMETIC 4.6.4 For brevity, we may write (Abyss web server)
490 ARITHMETIC 4.6.4 For brevity, we may write (52) as z(u)y(u) = Z(U), letting Z(U) denote the polynomial ~0 + zlu + x2u2, etc. Note that we have come full circle from the way we began this section, since Eq. (1) refers to u(z), not x(u); the notation has changed because the coefficients of the polynomials are now the variables of interest to us. If each of the six matrices in (53) is regarded as a vector of length 12 indexed by (i, j), it is clear that the vectors are linearly independent, since they are nonzero in different positions; hence the rank of (53) is at least 6 by Lemma T. Conversely, it is possible to obtain the coefficients ~0, 21, . . . , zs by making only six chain multiplications, for example by computing X(O)Y(O), XP)Y(l), -. .P x(5)!/(5); (54) this gives the values of z(O), z(l), . . . , z(5), and the formulas developed above for interpolation will yield the coefficients of z(u). The evaluation of x(j) and y(j) can be carried out entirely in terms of additions and/or parameter multiplications, and the interpolation formula merely takes linear combinations of these values. Thus, all of the chain multiplications are shown in (54) and the rank of (53) is 6. (We used essentially this same technique when multiplying high-precision numbers in Algorithm 4.3.3C.) The realization A, B, C of (53) sketched in the above paragraph turns out to be Thus, the scheme does indeed require the minimum number of chain multiplica- tions, but it is completely impractical because it involves so many additions and parameter multiplications. We shall now study a practical approach to the generation of more efficient schemes, suggested by S. Winograd. In the first place, to evaluate the coefficients of x(~)y(u) when deg(z) = m and deg(y) = n, one can use the identity 44~04 = (xb.4~(4 mod p(4) + z~Y~P(~, (56) when p(u) is any manic polynomial of degree m+n. The polynomial p(u) should be chosen so that the coefficients of x(u)y(~)modp(u) are easy to evaluate. In the second place, to evaluate the coefficients of x(u)y(u)modp(u), when the polynomial p(u) can be factored into q(u)r(u) where gcd(q(u), T(U)> = 1, one can use the identity x(~>Y(u) mod q(u)r(u) = (4u)r(u)(x(u)~(u) mod q(u)) + W&~(XWY(~ mod +4)) mod &4@4 (57)