Best web site - 494 ARITHMETIC 4.6.4 illustrated important techniques that are
494 ARITHMETIC 4.6.4 illustrated important techniques that are useful in a variety of other situations. For example, Winograd has used this approach to compute Fourier transforms using significantly fewer multiplications than the fast Fourier transform algo- rithm needs (see exercise 53). Let us conclude this section by determining the exact rank of the n X n X n tensor that corresponds to the multiplication of two polynomials modulo a third, = (ZO + ZIU + . . . + ~~-lu~-~)(yo + ylu + . . . + yn.-iu+ )modp(u). (69) Here p(u) stands for any given manic polynomial of degree n; in particular, p(u) might be 2~~ -1, so one of the results of our investigation will be to deduce the rank of the tensor corresponding to cyclic convolution of degree n. It will be convenient to write p(u) in the form p(u) = un -pn-lun–l -. . . - p1u -pi-J, (70) so that un E po + plu + . . . + pn.–l~n-l (modulo p(u)). The tensor element tijk is the coefficient of uk in ui+j mod p(u); and this is the element in row i, column Ic of the matrix Pj, where 0 1 0 . . . 0 0 0 1 . . . 0 p= i ; i (71) 0 0 0 . . . i i PO Pl P2 1. * Pn-1 I is called the companion matrix of p(u). (The indices i, j, k in our discussion will run from 0 to n -1 instead of from 1 to n.) It is convenient to transpose the tensor, for if Tijk = t&j the individual layers of (Tijk) for /C = 0, 1, 2, . . . , n - 1 are simply given by the matrices I P P2 . . . pn–l. (72) The first rows of the matrices in (72) are respectively the unit vectors (l,O, 0,. . . ,O), (O,l,O,. . . ,O), (O,O, 1,. . . ,O), . . . , (O,O,O,. .., l), hence a linear combination such as C o< k