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

• BaSt83: W. Baur and V. Strassen, "The complexity of partial derivatives," Theoretical Comp. Sci., vol. 22, pp. 317-330, 1983.
• CaEp78: B.F. Caviness and H. }. Epstein, "A note on the complexity of algebraic differentiation," Inf. Proc. Lett., vol. 7, pp. 122-124, 1978.
• CGGG83: Bruce W. Char , Keith O. Geddes , W. Morven Gentleman , Gaston H. Gonnet, The design of maple: A compact, portable and powerful computer algebra system, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.101-115, March 28-30, 1983
• Ga85a: Joachim von zur Gathen, Irreducibility of multivariate polynomials, Journal of Computer and System Sciences, v.31 n.2, p.225-264, Sept. 1985 [doi>10.1016/0022-0000(85)90043-1]
• Gon84: Gaston H. Gonnet, Determining equivalence of expressions in random polynomial time, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.334-341, December 1984 [doi>10.1145/800057.808698]
• 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.
• IbMo83: Oscar H. Ibarra , Shlomo Moran, Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs, Journal of the ACM (JACM), v.30 n.1, p.217-228, Jan. 1983 [doi>10.1145/322358.322373]
• 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.
• Ka85d: Erich Kaltofen, Sparse Hensel Lifting, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.4-17, April 01-03, 1985
• Ka86b: E Kaltofen, Computing with polynomials given by straight-line programs I: greatest common divisors, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.131-142, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22160]
• Ka86a: E Kaltofen, Uniform closure properties of P-computable functions, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.330-337, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12163]
• Mar71: William A. Martin, Determining the Equivalence of Algebraic Expressions by Hash Coding, Journal of the ACM (JACM), v.18 n.4, p.549-558, Oct. 1971 [doi>10.1145/321662.321668]
• Mo71: Joel Moses, Algebraic simplification: a guide for the perplexed, Communications of the ACM, v.14 n.8, p.527-537, Aug. 1971 [doi>10.1145/362637.362648]
• Pl77: D.A. Plaisted, "Sparse complex polynomials and polynomial reducibility," d. Comp. System Sci., vol. 14, pp. 210-221, 1977.
• Schw80: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
• Stou84: D.R. Stoutemyer, "Which polynomial representation is best?," Third MACSYMA Users' Conference, pp. 221- 243, General Electric, 1984.
• St73a: V. Str~ssen, "Vermeidung yon Divisionen," J. reine u. angew. Math., vol. 264, pp. 182-202, 1973.
• Va82: L. Valiant, "Reducibility by algebraic projections," L'Enseignement mathb.matique, vol. 28, pp. 253-268, 1982.
• Zi79: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979
• Zi81: Richard Zippel, Newton's iteration and the sparse Hensel algorithm (Extended Abstract), Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.68-72, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806372]
• GaKa85b: Joachim von zur Gathen , Erich Kaltofen, Factoring sparse multivariate polynomials, Journal of Computer and System Sciences, v.31 n.2, p.265-287, Sept. 1985 [doi>10.1016/0022-0000(85)90044-3]
• 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

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Polynomials, methods for

General Terms:
Algorithms, Design, Performance, Theory