Web hosting domain - 4.6.4 ANSWERS TO EXERCISES 651 complex multiplications are
4.6.4 ANSWERS TO EXERCISES 651 complex multiplications are all simple since they involve only two real multiplications and no real additions.) We can construct a normal scheme for the two-dimensional m x m case by applying the m scheme to vectors F(t , *) of length m . Each si step becomes m additions; each rnj becomes a Fourier transform on m elements, but with all of the (Y S in this algorithm multiplied by crj; and each tk becomes m additions. Thus the new algorithm has (a m + c a ) complex additions, t t trivial multiplications, and a total of c c complex multiplications. Using these techniques, Winograd has found normal one-dimensional schemes for the following small values of m with the following costs (a, t, c): m = 2 ( 2,2,2) m = 7 (36,1, 9) m = 3 ( 6,1,3) m=8 (2% 6, 
m = 4 ( 8,4,4) m = 9 (46,1,12) m=5 (17,1,6) m = 16 (74,8,18) By combining these schemes as described above, we obtain methods that use fewer arithmetic operations than the fast Fourier transform (FFT) discussed in exercise 14. For example, when m = 1008 = 7.9.16, the costs come to (17946,8,1944), so we can do a Fourier transform on 1008 complex numbers with 3872 real multiplications and 35892 real additions. It is possible to improve on Winograd s method for combining relatively prime moduli by using multidimensional convolutions, as shown by Nussbaumer and Quandalle in IBM J. Res. and Devel. 22 (1978), 134-144; their ingenious approach reduces the amount of computation needed for 1008-point complex Fourier transforms to 3084 real multiplications and 34668 real additions. By contrast, the FFT on 1024 complex numbers involves 14344 real multiplications and 27652 real additions. If the two-passes-at-once improvement in the answer to exercise 14 is used, however, the FFT on 1024 complex numbers needs only 10936 real multiplications and 25948 additions, and it is not difficult to implement. Therefore the subtler methods are faster only on machines that take significantly longer to multiply than to add. [References: Proc. Nat. Acad. Sci. USA 73 (1976), 1005-1006; Math. Comp. 33 (1978), 175-199; Advances in Math. 32 (1979), 83-117.1 54. max(2eldeg(pl) -1,. . ,2e,deg(p,) -1, q + 1). 55. 2n -q , where n is the degree of the minimum polynomial of P (i.e., the manic polynomial p of least degree such that p(P) is the zero matrix) and r is the number of distinct irreducible factors it has. (Reduce P by similarity transformations.) 56. Let tzjk + t @ = rijk + rjik, for all i, j, k. If A, B, c iS a realization Of (tijk) Of rank 7, then cl