Free web design - 4.6.4 EVALUATION OF POLYNOMIALS 503 54. [A-4.%?] Theorem
4.6.4 EVALUATION OF POLYNOMIALS 503 54. [A-4.%?] Theorem W refers to an infinite field. How many elements must a finite field have in order for the proof of Theorem W to be valid? 55. [HA&??] Determine the rank of tensor (72) when P is an arbitrary n x n matrix. 56. [A&??] (V. Strassen.) Show that any polynomial chain that evaluates a set of quadratic forms c Ili,jln723k~z~k for 1 5 k 2 s must use at least Jrank(r,,k +r]ik) chain multiplications. [Hint: Show that the minimum number of chain multiplications iS the ~iniInU~ rank Of (i&k) taken over all tenSOrS (tzjk) such that tijk + tjik = TtJk + rJZk for all i, j, k.] Use this to prove that any polynomial chain that evaluates a set of bilinear forms (45) corresponding to a tensor (tijk), whether normal or abnormal, must use at least ?jrank(t,,k) chain multiplications. 57. [MZO] Show that fast Fourier transforms can be used to compute the coefficients of the product z(u)y(~) of two given polynomials of degree n, using O(n log n) operations of (exact) addition and multiplication of complex numbers. [Hint: Consider the product of Fourier transforms of the coefficients.] 58. [HA&B] (a) Show that any realization A, B, C of the polynomial multiplication tensor (53) must have the following property: Any nonzero linear combination of the three rows of A must be a vector with at least four nonzero elements; and any nonzero linear combination of the four rows of B must have at least three nonzero elements. (b) Find a realization A, B, C of (53) using only 0, +l, and -1 as elements, where t = 8. Try to use as many O s as possible. b 59. [M40] (H. J. Nussbaumer, 1980.) The text defines the cyclic convolution of two sequences (so, Q, . . . , ~~-1) and (ye, yr, . . . , y,-I) to be the sequence (~0, ~1,. . , ~~-1) where zk = x,,yk + . . + sky0 + Xk+lYn-1 + + xn-lyk+l. Let us define the negacyclic convolution similarly, but with zk = XOyk + . . . + ZkyO -(Xk+lyn-1 + . . . + xn-lyk+l), Construct efficient algorithms for cyclic and negacyclic convolution over the integers when n is a power of 2. Your algorithms should deal entirely with integers, and they should perform at most O(n log n) multiplications and at most O(n log n log log n) additions or subtractions or divisions of even numbers by 2. 60. [M.Z7] (V. I^a. Pan.) The problem of (m X n) times (n X s) matrix multiplication corresponds to an mn X 72s X sm tensor (t(,,j1)(3,k )(k,z )) where t(i,j )(j,k/)(k,$) = 1 if and only i = i and j = j and k = k. The rank of this tensor T(m, n, s) is the Smallest r such that numbers c&j/l, bjk l, ckill exist satisfying Let M(n) be the rank of T(n,n, n). The purpose of this exercise is to exploit the symmetry of such a trilinear representation, obtaining efficient realizations of matrix multiplication over the integers when m = n = s = 2~. For convenience we divide the indices { 1, . . , n} into two subsets 0 = { 1,3, . , n -l} and E = { 2,4, . . , n} of v elements each, and we set up a one-to-one correspondence between 0 and E by the rule Z = i $1 if i E 0; Z = i -1 if i E E. Thus we have i = i for all indices i.