Numerical algebraic geometry and symbolic computation

ABSTRACT

In a recent joint work with Andrew Sommese and Charles Wampler, numerical homotopy continuation methods have been developed to deal with positive dimensional solution sets of polynomial systems. As solving polynomial systems is such a fundamental problem, connections with recent research in symbolic computation are not hard to find. We will address two such connections.One part of the numerical output of our methods consists of a "membership test" used to determine whether a point lies on apositive dimensional solution component. While Grobner bases provide an exact answer to the ideal membership test, geometrical results can be obtained at a lower complexity, as shown by Marc Giusti and Joos Heintz [6]. The recent work of Gregoire Lecerf [7, 9] implements an irreducible decomposition in a symbolic manner.The factorization of multivariate polynomials with approximate coefficients was posed as an open problem in symbolic computation by Erich Kaltofen [8]. Providing a certificate for a numerical factorization by means of the linear trace is related to ideas of André Galligo and David Rupprecht [3, 4], which also appears in the works of Tateaki Sasaki [10] and collaborators. See also [1, 2] and [5].

REFERENCES

• 1: Robert M. Corless , Mark W. Giesbrecht , Mark van Hoeij , Ilias S. Kotsireas , Stephen M. Watt, Towards factoring bivariate approximate polynomials, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.85-92, July 2001, London, Ontario, Canada [doi>10.1145/384101.384114]
• 2: R. Corless, A. Galligo, I. Kotsireas, and S. Watt. A geometric-numeric algorithm for factoring multivariate polynomials.
• 3: André Galligo , David Rupprecht, Semi-numerical determination of irreducible branches of a reduced space curve, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.137-142, July 2001, London, Ontario, Canada [doi>10.1145/384101.384121]
• 4: André Galligo , David Rupprecht, Irreducible decomposition of curves, Journal of Symbolic Computation, v.33 n.5, p.661-677, May 2002 [doi>10.1006/jsco.2002.0528]
• 5: Shuhong Gao , Erich Kaltofen , John May , Zhengfeng Yang , Lihong Zhi, Approximate factorization of multivariate polynomials via differential equations, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.167-174, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005311]
• 6: M. Giusti and J. Heintz. La détermination de la dimension et des points isolées d'une variété algébrique peuvent s'effectuer en temps polynomial. In D. Eisenbud and L. Robbiano, editors, Computational Algebraic Geometry and Commutative Algebra, Cortona 1991, pages 216--256. Cambridge UP, 1993.
• 7: Marc Giusti , Grégoire Lecerf , Bruno Salvy, A Gröbner free alternative for polynomial system solving, Journal of Complexity, v.17 n.1, p.154-211, March 1, 2001 [doi>10.1006/jcom.2000.0571]
• 8: Erich Kaltofen , Robert M. Corless , David J. Jeffrey, Challenges of symbolic computation: my favorite open problems, Journal of Symbolic Computation, v.29 n.6, p.891-919, June 2000 [doi>10.1006/jsco.2000.0370]
• 9: Grégoire Lecerf, Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers, Journal of Complexity, v.19 n.4, p.564-596, August 2003 [doi>10.1016/S0885-064X(03)00031-1]
• 10: Tateaki Sasaki, Approximate multivariate polynomial factorization based on zero-sum relations, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.284-291, July 2001, London, Ontario, Canada [doi>10.1145/384101.384139]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Continuation (homotopy) methods

General Terms:
Algorithms

Keywords:
approximate factorization, irreducible decomposition, numerical homotopy continuation, polynomial systems