Tomcat, J2Ee, Hibernate Programming, Shared Web Hosting, Comcast Web Hosting Java Blog

4.6.4 EVALUATION OF POLYNOMIALS 499 23. [HM30] (J. Eve.) Let f(z) = a,zn + an-lzn- + … + a0 be a polynomial of degree n with real coefficients, having at least n -1 roots with a nonnegative real part. Let g(z) = a,zn + un-2Zn–2 + . . + hm0dzZ nmod2 7 h(z) = a,-lz–l + &-3zn-3 + f ~(,-l)~~d2Z(n-1)mod2. Assume that h(z) is not identically zero. a) Show that g(z) has at least n -2 imaginary roots (i.e., roots whose real part is zero), and h(z) has at least n -3 imaginary roots. [Hint: Consider the number of times the path f(z) circles the origin as z goes around the path shown in Fig. 15, for a sufficiently large radius R.] b) Prove that the squares of the roots of g(z) = 0 and h(z) = 0 are all real. - R Fig. 15. Proof of Eve s theorem. b 24. [h .Z4] Find values of c and &k, Pk satisfying the conditions of Theorem E, for the polynomial U(Z) = (Z + 7)(x* + 6~ + 10)(~ $4~ j-5)(2 + 1). Choose these values so that PZ = 0. Give two different solutions to this problem! 25. [M.Z0] When the construction in the proof of Theorem M is applied to the (ineffi- cient) polynomial chain Xl = 0.1 +x0, x2 = —x0 -x0, x3 = Xl + Xl, x4 = a2 x X3, x5 = x0 –x0, X6 = cl6 -x5, x7 = ff7 +x63, X8 = x7 x X7, x9 = Xl x x4, x10 = Q8 -x9, 111 = x3 -x10, how can PI, fiz, . . . , /3s be expressed in terms of CQ, , cvs? b 26. [M.21] (a) Give the polynomial chain corresponding to Horner s rule for evaluating polynomials of degree n = 3. (b) Using the construction that appears in the text s proof of Theorem A, express ~1, ~2, 1c3, and the result polynomial U(X) in terms of ,&, Pz, ps, p4, and 5. (c) Show that the result set obtained in (b), as PI, &, /33, and p4 independently assume all real values, omits certain vectors in the result set of (a). 27. [Mz?] Let R be a set that inciudes all (n+l)-tuples (q,, . . , ~,qo) of real numbers such that qn # 0; prove that R dpes not have at most n degrees of freedom. 28. [HMz?~] Show that if fo(crl,. . , as), . . . , fs(o~, . . , cu,) are multivariate polyno- mials with integer coefficients, then there is a nonzero polynomial g(zo, . . , z~) with integer coefficients such that g(f ( . , fs(crl,. = all real al, 0 CXI, , as), . . , as)) 0 for . ..) as. (Hence any polynomial chain with s parameters has at most s degrees of freedom.) [Hint: Use the theorems about algebraic dependence that are found, for example, in B. L. van der Waerden s Modern Algebra, tr. by Fred Blum (New York: Ungar, 1949), Section 64.1
Note: If you are looking for cheap and reliable webhost to host and run your mysql application check mysql web server services.

498 ARITHMETIC 4.6.4 b 15. [HA4.28] The nth divided difference f(zs, ~1,. . , z~) of a function f(r) at n + 1 distinct points ~0, x1, . , 5% is defined by the formula f(50,21,…,2n)=(f( ~0,~1,…,Z~-1)-f(Z1,…,271–1,21L))/(Z0 -Zn), for n > 0. Thus f(zo, 21,. . ,G) = COCkCn f(%)/ no,,I,,j+&k -23) is a - symmetric function of its n + 1 arguments. (a) Prove that f(zo, . , G) = f (e)/n! , for some 0 between min(zo, , CC,) and max(zo, , G), if the nth derivative f( )(z) exists and is continuous. [Hint: Prove the identity &it1 lit,. . .~nit,l (xo(l-tl) + xl(tl–t2) + . . . f(xo,51,…,xn)= +~n-l(tn-l-tn) + zn(tn-0)). This formula also defines f(zo, ~1,. , z,) in a useful manner when the x3 are not distinct.] (b) If yj = f(xj), show that oj = f(xo, . . . , xj) in Newton s interpolation polynomial (42). 16. [AL%?] How can we readily compute the coefficients of ul ](x) = u,xn +. + ~0, if we are given the values of x0, xl, . . . , ~~-1, CQ, al, . . . , on in Newton s interpolation polynomial (42)? 17. [M45] Is there a way to evaluate the polynomial c 22×3+.. . + xn-lxn = x152 llz<3ln with fewer than n -1 multiplications and 2n -4 additions? (There are (y) terms.) 18. [A&V] If the fourth-degree scheme (9) were changed to Y = (x + ao)x + Ql, 4x) = ((Y -x + m)y + cy3)Ly4, what formulas for computing the q s in terms of the @ s would take the place of (lo)? b 19. [M24] Explain how to determine the adapted coefficients oo, ol, , cy5 in (11) from the coefficients ~5, , ZL~, uo of u(z), and find the o s for the particular polynomial u(z) = x5 + 5x4 -10x3 -50x2 + 13x + 60. b 20. [ZY] Write a MIX program that evaluates a fifth-degree polynomial according to scheme (11); try to make the program as efficient as possible, by making slight modifications to (11). Use MIX s floating point arithmetic operators FADD and FMUL, which are described in Section 4.2.1. 21. [Zoo] Find two additional ways to evaluate the polynomial x6 + 13~~ + 49x4 + 33x3 -61x2 -37x $ 3 by scheme (12) using the two roots of (15) that were not considered in the text. 22. [IL?] What is the scheme for evaluating x6 -3x5 +x4 -2x3 + z2 -32 -1, using Pan s method (16)?
Visit our web design programs services for an affordable and reliable webhost to suit all your needs.

4.6.4 EVALUATION OF POLYNOMIALS 497 4. [M,20] The text shows that scheme (3) is superior to Homer s rule when we are evaluating a polynomial with real coefficients at a complex point z. Compare (3) to Horner s rule when both the coefficients and the variable z are complex numbers; how many (real) multiplications and addition-subtractions are required by each method? 5. [MIS] Count the number of multiplications and additions required by the second- order rule (4). 6. [,?Z] (L. de Jong and J. van Leeuwen.) Show how to improve on steps Sl, . . . , S4 of the Shaw-Traub algorithm by computing only about in powers of 20. 7. [A424] How can PO, . . , Pn be calculated so that (6) has the value U(ZO + kh) for all integers k? 8. [MBI] The factorial power xk is defined to be k!(i) = ~(a: - 1). . . (z -k + 1). Explain how to evaluate unxE + . . . + ulxi + ZLO with at most n multiplications and 2n -1 additions, starting with z and the n + 3 constants un, . . . , UO, 1, n -1. 9. [A424] (H. J. Ryser.) Show that if X = (xij) is an n X n matrix, then summed over all 2n choices of ~1, . . . , en equal to 0 or 1 independently. Count the number of addition and multiplication operations required to evaluate per(X) by this formula. 10. [A&I] The permanent of an n X n matrix X = (xi3) may be calculated as follows: Start with the n quantities x11, 212, . , ~1~. For 1 5 k < n, assume that the (;) quantities ADS have been computed, for all k-element subsets S of {1,2, . . . , n}, where z&s = ~Xlj,... xkjk summed over all k! permutations j, . . . jk of the elements of S; then form all of the sums We have per(X) = &{I,...,,). How many additions and multiplications does this method require? How much temporary storage is needed? 11. [A4461 Is there any way to evaluate the permanent of a general n X n matrix using fewer than 2n arithmetic operations? 12. [A4501 What is the minimum number of multiplications required to form the product of two n X n matrices? What is the smallest exponent p such that O(np+ ) multiplications are sufficient for all E > O? 13. [M,%?] Find the inverse of the general discrete Fourier transform (3 7), by express- ing F(tl,. . . , tn) in terms of the values of f(sl, . . . , sn). [Hint: See Eq. 1.2.9-13.1 b 14. [HMZB] ( Fast Fourier transforms. ) Show that the scheme (40) can be used to evaluate the one-dimensional discrete Fourier transform f(s) = c F(t)@, w = ew2n, 0 5 s < 2 , using arithmetic on complex numbers. Estimate the number of arithmetic operations performed.
Please visit our professional web hosting services to find out about cheap and reliable webhost service that will surely answer all your demands.

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.
If you are searching for cheap webhost for your web application, please visit MySQL5 Web Hosting services.

4.6.4 EVALUATION OF POLYNOMIALS 495 Theorem W (S. Winograd, 1975). Let p(u) be a mom? polynomial of degree n whose complete factorization over a given infinite field is p(u) = p1(u)Q.. .p&p. (73) Then the rank of the tensor (72) corresponding to the bilinear forms (69) is 2n-q over this field. Proof. The bilinear forms can be evaluated with only 2n-q chain multiplications by using rules (56), (573, (58) m an appropriate fashion, so we must prove only that the rank r is 2 2n -q. The above discussion establishes the fact that rank(Tcij,k) = n; hence by Lemma T, any n X r realization A, B, C of (T,jk) has rank(C) = n. Our strategy will be to use Lemma T again, by finding a vector (~0,211,. . . , ~~-1) that has the following two properties: a) The vector (~0, ~1,. . . , u,-~)C has at most q + T - n nonzero coefficients. b) The matrix v(P) = C o < k < n vk Pk is nonsingular. - This and Lemma T will prove that q + T - n 2 n, since the identity shows how to realize the n X n X 1 tensor w(P) of rank n with q + r -n chain multiplications. We may assume for convenience that the first n columns of C are linearly independent. Let D be the n X n. matrix such that the first n columns of DC are equal to the identity matrix. Our goal will be achieved if there is a linear combination (~0, ~1, . . . , ~1,~~) of at most q rows of D, such that v(P) is nonsingular; such a vector will satisfy conditions (a) and (b). Since the rows of D are linearly independent, no irreducible factor PA(U) divides the polynomials corresponding to every row. Given a vector w = (wet Wl , . . . , w,--I), let covered(w) be the set of all X such that w(u) is not a multiple of PA(U). From two vectors v and w we can find a linear combination v + cyw such that covered(v + cyw) = covered(v) U covered(w), (74) for some a! in the field. The reason is that if X is covered by v or w but not both, then X is covered by v + aw for all nonzero cy; if X is covered by both v and w but X is not covered by v + QW, then X is covered by v + /3w for all p # cy. By trying q + 1 different values of (u, at least one must yield (74). In this way we can systematically construct a linear combination of at most q rows of D, covering all X for 1 5 X < q. I
From our experience, we can recommend PHP5 Web Hosting services, if you need affordable webhost to host and run your web application.

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< kIn case you need affordable webhost to host your website, our recommendation is ecommerce web host services.

4.6.4 EVALUATION OF POLYNOMIALS 493 treating the subscripts modulo n, since tijk = 1 if and only if i + j = k (modulo n). Thus if (ail), (bjl), (ckl ) is a realization of the cyclic convolution, so is (C&l), (b-j,l), (ail); in particular, we can realize (61) by transforming (64) into Now all of the complicated scalars appear in the A matrix. This is important in practice, since we often want to compute the convolution for many values of yo, yl, y2, ys but for a fixed choice of Q,, ~1, ~2, 5s. In such a situation, the arithmetic on x s can be done once and for all, and we need not count it. Thus (66) leads to the following scheme for evaluating the cyclic convolution WJO, 201, w2, w3 when x0, x1, x2, x3 are known in advance: 31 = Yo +y2, s2 = Yl + y3, $3 = 31 + s2, s4 = Sl -s2, s5 = Yo -Y2, 36 = Y3 -Yl, 37 = +j -~96; ~0+~1+~2+~3 =3-zl+zZ-Q ~O+~l–zZ–zS ml = 4. ~3, m2 = 4~ ~4, m3 = 2 . ~5, m4 = —~o+~l+~r-% . sg, m5 = y . ST; tl=ml+m2, t2=m3+m5, t3=ml–2, t4=m4-m5; wo = t1 + t2, Wl = t3+t4, w2 = t1 -t2, w3 = t3 -t4. (67) There are 5 multiplications and 15 additions, while the definition of cyclic con- volution involves 16 multiplications and 12 additions. We will prove later that 5 multiplications are necessary. Going back to our original multiplication problem (52), using (60), we have derived the realization This scheme uses one more than the minimum number of chain multiplications, but it requires far fewer parameter multiplications than (55). Of course, it must be admitted that the scheme is still rather complicated: If our goal is simply to compute the coefficients ~0, zl, . . . , 25 of the product of two given polyno- mials (x0 + xru + xzu2)(y~ + yru + yzu2 + ysu3), as a one-shot problem, our best bet is still to use the obvious method that does 12 multiplications and 6 additions-unless (say) the x s and y s are matrices. Note that if the x s are fixed as the y s vary, the new scheme does the evaluation with 7 multiplications and 17 additions. Even though (68) isn t especially useful as it stands, our derivation has
Visit our web design programs services for an affordable and reliable webhost to suit all your needs.

492 ARITHMETIC 4.6.4 kth coefficient wk is the bilinear form c ~i yj summed over all i and j with i + j G k (modulo n). The cyclic convolution of degree 4 can be obtained by applying rule (57). The first step is to find the factors of u4 -1, namely (U - l)(u + 1)(u2 + 1). We could write this as (u -1)(u2 + l), then apply rule (57), then use (57) again on the part modulo (u2 -1) = (U -l)(u + 1); but it is easier to generalize the Chinese remainder rule (57) directly to the case of several relatively prime factors. For example, we have z(u)y(u)modql(u)q2(u)q3(u) = al(U)q2(U)q3(U)(Z(U)Y(U)modql(u)) + a2(u)ql(u)q3( 11)(2(U)Y(U)modq2(u)) ( + u3(u)q1(11)42(u)(2(u)y(u)modg3cu,,> modql(uMuMu), (62) where ul(uMu)q3(u) + 4u)ql(u)q3(u) -t m(u)ql(u)q2(u) = 1. (The latter equation can be understood in another way, by noting that the partial fraction expansion of l/ql(u)q2(u)qdu) is ul(~)/ql(~)+u2(~)/q2(~)+~3(~)/q3(~). When each of the q s is a linear polynomial u -cy2, the generalized Chinese remainder rule reduces to ordinary interpolation as in Eq. (41), since f(u) mod (U -oi) = f(oi).) From (62) we obtain z(u)y(u) mod (u4 -1) = ( U3-tv~+U+1 Z( l)y( 1) -U3-Ui+U-1 z(-l)y(-1) -v(z(u)y(u) mod (u + 1))) mod (u4 -1). (63) The remaining problem is to evaluate z(u)y(u) mod (u2 + l), and it is time to invoke rule (58). First we reduce Z(U) and y(u) mod (u2 + l), obtaining X(U) = (TO -~2) -I-(~1 -23)~~ Y(u) = (YO -YZ) + (yl -y3)u. Then (58) tells us to evaluate X(U)Y(u) = 20 + Zru + Z2u2, and to reduce this in turn modulo (u2 + l), obtaining (20 -Z2) + 2 1~. The job of computing X(u)Y(u) is simple; we can use rule (56) with p(u) = U(U f 1) and we get 20 = XOY,, Z-1 = XOYO -(xo-x1)(Yo-Y~) + X,Y,, 2, = X,Y,. (We have thereby rediscovered the trick of Eq. 4.3.3-2 in a more systematic way.) Putting everything together yields the following realization A, B, C of degree-4 cyclic convolution: Here i stands for -1 and 2 for -2. The tensor for cyclic convolution of degree n satisfies tz,j,k = h-j,%, (65)
If you are searching for cheap webhost for your web application, please visit MySQL5 Web Hosting services.

4.6.4 EVALUATION OF POLYNOMIALS 491 where ~(U)?(U) + b(u)q(u) = 1; this is essentially the Chinese remainder theorem applied to polynomials. In the third place, to evaluate the coefficients of z(~)y(~)modp(u) when p(u) has only one irreducible factor over the field of coefficients, one can use the identity duly(u) mod p(u) = (4~) mod du))(y(u) moddu)) mod p(u). (58) Repeated application of (56) (577, and (58) tends to produce efficient schemes, as we shall see. For our example problem (52), let us choose P(U) = u5 -u and apply (56); the reason for this choice of p(u) will appear as we proceed. Writing p(u) = u(u -l), rule (57) reduces to x(u)y(u) mod ~(21~ -1) = (-(U -l)zoye + u4(x(u)y(u) mod (u -1))) mod (u5 -u). (59) Here we have used the fact that z(u)y(u) mod u = zeyo; in general it is a good idea to choose p(u) in such a way that p(O) = 0, so that this simplification can be used. If we could now determine the coefficients we, wi, ws, ws of the polynomial z(u)y(u)mod(~~ -1) = wo + wiu + wsu2 + wsu3, our problem would be solved, since u4(z(u)y(u) mod (u4 -1)) mod (ti5 -u) = wou4 + wiu + w2u2 + w3u3, and the combination of (56) and (59) would reduce to (This formula can, of course, be verified directly.) The problem remaining to be solved is to compute ~(u)y(u)mod(u~ -1); and this subproblem is interesting in itself. Let us momentarily allow X(U) to be of degree 3 instead of degree 2. Then the coefficients of z(u)y(u) mod (u -1) are respectively zoyo + TlYQ + 572Y2 + 23Y1, zO!/l + ZlYO + 22Y3 + z3!/2, zoy2 + ZlYl + Z2Yo + Z3Y3, TOY3 + XlY2 + Z2Yl + Z3Y0, and the corresponding tensor is In general when deg(z) = deg(y) = n-l, the coefficients of z(u)y(u) mod (~ -1) are called the cyclic convolution of (~0, x1, . . . , qP1) and (ye, yl, . . . , ynPl). The
Please visit our professional web hosting services to find out about cheap and reliable webhost service that will surely answer all your demands.

490 ARITHMETIC 4.6.4 For brevity, we may write (52) as z(u)y(u) = Z(U), letting Z(U) denote the polynomial ~0 + zlu + x2u2, etc. Note that we have come full circle from the way we began this section, since Eq. (1) refers to u(z), not x(u); the notation has changed because the coefficients of the polynomials are now the variables of interest to us. If each of the six matrices in (53) is regarded as a vector of length 12 indexed by (i, j), it is clear that the vectors are linearly independent, since they are nonzero in different positions; hence the rank of (53) is at least 6 by Lemma T. Conversely, it is possible to obtain the coefficients ~0, 21, . . . , zs by making only six chain multiplications, for example by computing X(O)Y(O), XP)Y(l), -. .P x(5)!/(5); (54) this gives the values of z(O), z(l), . . . , z(5), and the formulas developed above for interpolation will yield the coefficients of z(u). The evaluation of x(j) and y(j) can be carried out entirely in terms of additions and/or parameter multiplications, and the interpolation formula merely takes linear combinations of these values. Thus, all of the chain multiplications are shown in (54) and the rank of (53) is 6. (We used essentially this same technique when multiplying high-precision numbers in Algorithm 4.3.3C.) The realization A, B, C of (53) sketched in the above paragraph turns out to be Thus, the scheme does indeed require the minimum number of chain multiplica- tions, but it is completely impractical because it involves so many additions and parameter multiplications. We shall now study a practical approach to the generation of more efficient schemes, suggested by S. Winograd. In the first place, to evaluate the coefficients of x(~)y(u) when deg(z) = m and deg(y) = n, one can use the identity 44~04 = (xb.4~(4 mod p(4) + z~Y~P(~, (56) when p(u) is any manic polynomial of degree m+n. The polynomial p(u) should be chosen so that the coefficients of x(u)y(~)modp(u) are easy to evaluate. In the second place, to evaluate the coefficients of x(u)y(u)modp(u), when the polynomial p(u) can be factored into q(u)r(u) where gcd(q(u), T(U)> = 1, one can use the identity x(~>Y(u) mod q(u)r(u) = (4u)r(u)(x(u)~(u) mod q(u)) + W&~(XWY(~ mod +4)) mod &4@4 (57)
We recommend you use shared web hosting services, because many users agree that it is cheap, reliable and customer-satisfying webhost.