648 ANSWERS TO EXERCISES 4.6.4 /3so = 0. The result set now has at most m + 1 + cl 3. This single canonical form involves m2 + 2m parameters. As the cr s run through all integers and as we run through all chains, the /3 s run through at most 2m2f2m sets of values mod 2, hence the result set does also. In order to obtain all 2n polynomials of degree n with O-l coefficients, we need m2 + 2m > n. (c) Set m + 161 and compute z2, x3, . . . , xm. Let U(X) = ZL~+~(X)X(~+ )~ + . . . + ul(x)xm f u,J(x), where each ~~(5) is a polynomial of degree 5 m with integer coefficients (hence it can be evaluated without any more multiplications). Now evaluate U(X) by rule (2) as a polynomial in xm with known coefficients. (The number of additions used is approximately the sum of the absolute values of the coefficients, so this algorithm is efficient on O-l polynomials. Paterson and Stockmeyer also gave another algorithm that uses about 6 multiplications.) Reference: SIAM J. Computing 2 (1973), 60-66; see also J. E. Savage, SIAh4 J. Computing 3 (1974), 150-158. For analogous results about additions, see Borodin and Cook, SIAM J. Computing 5 (1976), 146-157; Rivest and Van de Wiele, Inf. Proc. Letters 8 (1979), 178-180.1 43. When ai = aj $ ak is a step in some optimal addition chain for n $1, compute xi = z3xk and pi = p& fpj, where pi = x2-l+. . .+x+1; omit the final calculation of xnf . We save one multiplication whenever ak = 1, in particular when i = 1. (Cf. exercise 4.6.3-31 with c = a.) 44. It suffices to show that (TZjk) s rank is at most that of (&k), since we can obtain (tijk) back from (Tijk) by transforming it in the same way with F-l, G-l, H- . If t ajk = c 1 <1<7 azl bjl ckl then it follows immediately that [H. F. de Groote has proved that all normal schemes that yield 2 X 2 matrix products with seven chain multiplications are equivalent, in the sense that they can be obtained from each other by nonsingular matrix multiplication as in this exercise. In this sense Strassen s algorithm is unique.] 45. By exercise 44 we can add any multiple of a row, column, or plane to another one without changing the rank; we can also multiply a row, column, or plane by a nonzero constant, or transpose the tensor. A sequence of such operations can always be found to reduce agive 2 X 2 x 2 tensor to one of the forms ( )( )00 00 9 ( )( )00 7 (lo)(oo),01 (~~)(~~), 00 00 (A y)( z t). The last tensor has rank 3 or 2 according as the polynomial u2 - TU -9 has one or two irreducible factors in the field of interest, by Theorem W (cf. (72)). 46. A general m X n X s tensor has mns degrees of freedom. By exercise 28 it is impossible to express all m X n X s tensors in terms of the (m + n + S)T elements of a realization A, B, C unless (m + n + S)T 2 mns. On the other hand, assume that m 2 n 2 s. The rank of an m X n matrix is at most n, so we can realize any tensor in ns chain multiplications by realizing each matrix plane separately. [Exercise 45 shows that this lower bound on the maximum tensor rank is not best possible, nor is the upper bound. Thomas D. Howell (Ph. D. thesis, Cornell Univ., 1976) has shown that there are tensors of rank 2 [mns/(m + n + s - 2)1 over the complex numbers.]
This entry was posted
on Saturday, December 15th, 2007 at 10:25 am and is filed under MySQL.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.