A system for manipulating polynomials given by straight-line programs

ABSTRACT

We discuss the design, implementation, and benchmarking of a system that can manipulate symbolic expressions represented by their straight-line computations. Our system is capable of performing rational arithmetic, evaluating, differentiating, taking greatest common divisors of, and factoring polynomials in straight-line format. The straight-line results can also be converted to standard sparse format. We show by example that our system can handle problems for which conventional methods lead to excessive intermediate expression swell.

References

1. BaSt83.W. Baur and V. Strassen, "The complexity of partial derivatives," Theoretical Comp. Sci., vol. 22, pp. 317-330, 1983.
2. CaEp78.B.F. Caviness and H. }. Epstein, "A note on the complexity of algebraic differentiation," Inf. Proc. Lett., vol. 7, pp. 122-124, 1978.
3. CGGG83.B. W. Char, K. O. Geddes, W. M. Gentleman, and G. H. Gonnet, "The design of MAPLE: A compact, portable, and powerful c~mputer Mgebra system," Proe. EURO. CAL '83, Springer Lee. Notes Comp. Sci., vol. 162, pp. 102-115. t983.
4. Ga85a.J. yon zur Gathen, "Irreducibility of multivariate polynomials," J. Comp. System Sei., vol. 31, pp. 225-264, 1985.
5. Gon84.G.H. Gonnet, "Determining equivalence of expressions in random polynomial time," Proe. 16th ACM Syrup. Theory Comp., pp. 334-341, 1984.
6. HeSch82.J. Heintz and C. P. Sehnorr, "Testing Polynomials which are easy to compute," Monographie de L'Ensei~.Inement Math~matique, vol. 30, pp. 237-254, lmprimerie Kundig, Gen~ve, 1982.
7. IbMo83.O.H. lbarra and S. Moran, "Probabilistic algorithms for deciding equivalence of straight-line programs," J. ACM, vol. 30, pp. 217-228, 1983.
8. Ka85f.E. Kaltofen, "Computing with polynomials given by straight-line programs If; Sparse factorization," Proc. $6th IEEE Syrup. Foundations Comp. Sci., pp. 451-458, 1985.
9. Ka85d.E. Kaltofen, "Sparse Hensel lifting," Proc. EUROCAL ~85, Springer Lee. Notes Comp. Sci., vol. 204, pp. 4-17, 1985.
10. Ka86b.E. Kaltofen, "Great.est common divisors of polynomials given by straight-line programs," Math. Sci. Research Inst. Preprint, vol. 01918-86, Berkeley, CA, 1985. Preliminary version under the title "Computing with polynomials given by straight-line programs I: Greatest common divisors" in Proc. 17th A CM Syrup. Theory Comp., pp. 131-142, 1985.
11. Ka86a.E. Kaltofen, "Uniform closure properties of p-computable functions," Proe. 18th ACM Syrup. Theory Comp., p. to appear, 1986.
12. Mar71.W.A. Martin, "Determining the equivalence of algebraic expressions by hash coding." J. ACM. vol. 18, pp. 549- 558, 1971.
13. Mo71.J. Moses, "Algebraic simplification: A guide for the perplexed," Commun. ACM, vol. 14, pp. 548-560, 1971.
14. Pl77.D.A. Plaisted, "Sparse complex polynomials and polynomial reducibility," d. Comp. System Sci., vol. 14, pp. 210-221, 1977.
15. Schw80.J.T. Schwartz, "Fast probabilistic algorithms for verification of polynomial identities," d. ACM, vol. 27, pp. 701- 717, 1980.
16. Stou84.D.R. Stoutemyer, "Which polynomial representation is best?," Third MACSYMA Users' Conference, pp. 221- 243, General Electric, 1984.
17. St73a.V. Str~ssen, "Vermeidung yon Divisionen," J. reine u. angew. Math., vol. 264, pp. 182-202, 1973.
18. Va82.L. Valiant, "Reducibility by algebraic projections," L'Enseignement mathb.matique, vol. 28, pp. 253-268, 1982.
19. Zi79.R.E. Zippel, "Probabilistic algorithms for sparse polynomials," Proc. EUROSAM 79, Springer Lec. Notes Comp. Sci., vo|. 72, pp. 216-226, 1979.
20. Zi81.R.E. Zippel, "Newton's iteration and the sparse Hensel algorithm," Proc. '81 A CM Syrup. Symbolic Algebraic Comp.~ pp. 68-72, 1981.
21. GaKa85b.J. yon zur Gathen and E. Kaltofen, "Factoring sparse multivariate polynomials," J. Comp. System Sei., vol. 31, pp. 265-287, 1985.
22. Ka86c.E. Kaltofen, "Factorization of polynomials given by straight-line programs," Math. Sci. Research inst. Preprint, vol. 02018-86, Berkeley, CA, 1986. To appear in: Randomness in Computation, S. Micali ed., JAI Press, Greenwich, CT, January 1987.

Index Terms

• Computing methodologies

  • Symbolic and algebraic manipulation

    • Computer algebra systems

• Mathematics of computing

  • Mathematical analysis

    • Nonlinear equations

    • Numerical analysis

      • Computations on polynomials