Dagwood: 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 on, 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: BAUR, W., AND STRASSEN, V. The complexity of partial derivatives. Theor. Comput. Sci. 22 (1983), 317-330.
• 2: Michael Ben-Or, A deterministic algorithm for sparse multivariate polynomial interpolation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.301-309, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62241]
• 3: CAVINESS, B. F., AND EPSTEIN, H.I. A note on the complexity of algebraic differentiation, inf. Proc. Lett. 7 (1978), 122-124.
• 4: 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
• 5: CLAYBROOK, B.G. A new approach to the symbolic factorization of multivariate polynomials. Artif. Intell. 7 (1976), 203-241.
• 6: 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]
• 7: 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]
• 8: 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]
• 9: HEINTZ, J., AND SCHNORR, C.P. Testing polynomials which are easy to compute. In Monographie de L'Enseignement Math~matique, vol. 30. Imprimerie Kundig, Gen~ve, 1982, 237-254.
• 10: 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]
• 11: IMIRZIAN, G. M., JOHNSON, K., AND KALTOFEN, E. Factoring determinants of Latin squares. In preparation.
• 12: KALTOFEN, E. Computing with polynomials given by straight-line programs lh Sparse factorization. In Proceedings of the 26th IEEE Symposium on the Foundations of Computer Science (1985). IEEE, New York, 1985, 451-458.
• 13: Erich Kaltofen, Sparse Hensel Lifting, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.4-17, April 01-03, 1985
• 14: 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]
• 15: KALTOFEN, E. Factorization of polynomials given by straight-line programs. Mathematical Sciences Research Institute Preprint, vol. 02018-86, Berkeley, Calif., 1986. To appear in "Randomness in computation," Advances in Computing Research, S. Micali, Ed., JAI Press, Greenwich, Conn.
• 16: Erich Kaltofen, Greatest common divisors of polynomials given by straight-line programs, Journal of the ACM (JACM), v.35 n.1, p.231-264, Jan. 1988 [doi>10.1145/42267.45069]
• 17: Erich Kaltofen , Yagati N. Lakshman, Improved Sparse Multivariate Polynomial Interpolation Algorithms, Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation, p.467-474, July 04-08, 1988
• 18: 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]
• 19: Joel Moses, Symbolic integration: the stormy decade, Communications of the ACM, v.14 n.8, p.548-560, Aug. 1971 [doi>10.1145/362637.362651]
• 20: PLAISTED, D.A. Sparse complex polynomials and polynomial reducibility. J. Comput. Syst. Sci. 14 (1977), 210-221.
• 21: 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]
• 22: STOUTEMYER, D. R. Which polynomial representation is best? In Proceedings of the 3rd MACSYMA Users' Conference. General Electric, Schenectady, N.Y., 1984, 221-243.
• 23: STRASSEN, V. Vermeidung von Divisionen. J. reine u. angew. Math. 264 (1973), 182-202. In German.
• 24: VALIANT, L. Reducibility by algebraic projections. L'Enseignement math. 28 (1982), 253-268.
• 25: WANG, P.S. An improved multivariate polynomial factorization algorithm. Math. Comput. 32 (1978), 1215-1231.
• 26: Paul S. Wang, Early detection of true factors in univariate polynominal factorization, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.225-235, March 28-30, 1983
• 27: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979
• 28: 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]
• 29: ZIPPEL, R.E. Interpolating polynomials from their values. Manuscript, Symbolics, Inc., Jan. 1988.

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Representations (general and polynomial)
      I.1.3 Languages and Systems
          Subjects: Special-purpose algebraic systems

General Terms:
Algorithms, Design, Measurement, Performance

Keywords:
factorization, implementation in LISP, implicit representation, multivariate polynomial, program optimization, randomized algorithm, straight-line program