Web hosting domain - 496 ARITHMETIC 4.6.4 One of the most important
496 ARITHMETIC 4.6.4 One of the most important corollaries of Theorem W is that the rank of a tensor can depend on the field from which we draw the elements of the realization A, B, C. For example, consider the tensor corresponding to cyclic convolution of degree 5; this is equivalent to multiplication of polynomials mod P(U) = u5 -1. Over the field of rational numbers, the complete factorization of p(u) is (u -1) X (u + u3 + u2 + u + 1) by exercise 4.6.2-32, so the tensor rank is 10 -2 = 8. On the other hand, the complete factorization over the real numbers, in terms of the number 4 = &(l + fi), is (U -1)(u2 + #u + 1)(u2 -4-l~ + 1); thus, the rank is only 7, if we allow arbitrary real numbers to appear in A, El, C. Over the complex numbers the rank is 5. This phenomenon does not occur in two-dimensional tensors (i.e., matrices), where the rank can be determined by evaluating determinants of submatrices and testing for 0. The rank of a matrix does not change when the field containing its elements is embedded in a larger field, but the rank of a tensor can decrease when the field gets larger. In the paper that introduced Theorem W [Math. Systems Theory 10 (1977), 169-1801, Winograd went on to show that all realizations of (69) in 2n -q chain multiplications correspond to the use of (57), when q is greater than 1. Furthermore he has shown that the only way to evaluate the coefficients of z(u)y(zl) in deg(z) + deg(y) + 1 chain multiplications is to use interpolation or to use (56) with a polynomial that splits into distinct linear factors in the field. Finally he has proved that the only way to evaluate Z(U)Y(U) mod p(u) in 2n -1 chain multiplications when q = 1 is essentially to use (58). These results hold for all polynomial chains, not only normal ones. He has extended the results to multivariate polynomials in Sm J. Computing 9 (1980), 225-229. The tensor rank of an arbitrary m X n X 2 tensor in a suitably large field has been determined by Joseph Ja Ja , SIAM J. Computing 8 (1979), 443-462. For further reading. In this section we have barely scratched the surface of a very large subject in which many beautiful theories are emerging; a considerably more comprehensive treatment appears in the book Computational Complexity of Mgebraic and Numeric Problems by A. Borodin and I. Munro (New York: American Elsevier, 1975). EXERCISES 1. [IS] What is a good way to evaluate an odd polynomial Znfl 2n-1 + . . . + lL1x? u(x) = U2n+12 + 112n-12 b 2. [A4,%?] Instead of computing U(Z + ~0) by steps Hl and H2 as in the text, discuss the application of Horner s rule (2) when polynomial multiplication and addition are used instead of arithmetic in the domain of coefficients. 3. [.%?I Give a method analogous to Horner s rule, for evaluating a polynomial in two variables c,+jS, uijx yj. (This polynomial has (n + l)(n f 2)/2 coefficients, and total degree n.) Count the number of additions and multiplications you use.