Numerical algebraic geometry

Numerical algebraic geometry is a field of computational mathematics, particularly computational algebraic geometry, which uses methods from numerical analysis to study and manipulate the solutions of systems of polynomial equations.[1][2][3]

Homotopy continuation

edit

The primary computational method used in numerical algebraic geometry is homotopy continuation, in which a homotopy is formed between two polynomial systems, and the isolated solutions (points) of one are continued to the other. This is a specialization of the more general method of numerical continuation.

Let   represent the variables of the system. By abuse of notation, and to facilitate the spectrum of ambient spaces over which one can solve the system, we do not use vector notation for  . Similarly for the polynomial systems   and  .

Current canonical notation calls the start system  , and the target system, i.e., the system to solve,  .[4][5] A very common homotopy, the straight-line homotopy, between   and   is  

In the above homotopy, one starts the path variable at   and continues toward  . Another common choice is to run from   to  . In principle, the choice is completely arbitrary. In practice, regarding endgame methods for computing singular solutions using homotopy continuation, the target time being   can significantly ease analysis, so this perspective is here taken.[6]

Regardless of the choice of start and target times, the   ought to be formulated such that  , and  .

One has a choice in  , including

  • Roots of unity
  • Total degree
  • Polyhedral
  • Multi-homogeneous

and beyond these, specific start systems that closely mirror the structure of   may be formed for particular systems. The choice of start system impacts the computational time it takes to solve  , in that those that are easy to formulate (such as total degree) tend to have higher numbers of paths to track, and those that take significant effort (such as the polyhedral method) are much sharper. There is currently no good way to predict which will lead to the quickest time to solve.[citation needed]

Actual continuation is typically done using predictor–corrector methods, with additional features as implemented. Predicting is done using a standard ODE predictor method, such as Runge–Kutta, and correction often uses Newton–Raphson iteration.

Because   and   are polynomial, homotopy continuation in this context is theoretically guaranteed to compute all solutions of  , due to Bertini's theorem. However, this guarantee is not always achieved in practice, because of issues arising from limitations of the modern computer, most namely finite precision. That is, despite the strength of the probability-1 argument underlying this theory, without using a priori certified tracking methods, some paths may fail to track perfectly for various reasons.

Witness set

edit

A witness set   is a data structure used to describe algebraic varieties. The witness set for an affine variety that is equidimensional consists of three pieces of information. The first piece of information is a system of equations  . These equations define the algebraic variety   that is being studied. The second piece of information is a linear space  . The dimension of   is the codimension of  , and chosen to intersect   transversely. The third piece of information is the list of points in the intersection  . This intersection has finitely many points and the number of points is the degree of the algebraic variety  . Thus, witness sets encode the answer to the first two questions one asks about an algebraic variety: What is the dimension, and what is the degree? Witness sets also allow one to perform a numerical irreducible decomposition, component membership tests, and component sampling. This makes witness sets a good description of an algebraic variety.

Certification

edit

Solutions to polynomial systems computed using numerical algebraic geometric methods can be certified, meaning that the approximate solution is "correct". This can be achieved in several ways, either a priori using a certified tracker,[7][8] or a posteriori by showing that the point is, say, in the basin of convergence for Newton's method.[9]

Software

edit

Several software packages implement portions of the theoretical body of numerical algebraic geometry. These include, in alphabetic order:

  • alphaCertified[9]
  • Bertini [5]
  • Hom4PS[10][11]
  • HomotopyContinuation.jl[12]
  • Macaulay2 (core implementation of homotopy tracking and NumericalAlgebraicGeometry[3] package)
  • PHCPack[13]

References

edit
  1. ^ Hauenstein, Jonathan D.; Sommese, Andrew J. (March 2017). "What is numerical algebraic geometry?". Journal of Symbolic Computation. 79: 499–507. doi:10.1016/j.jsc.2016.07.015.
  2. ^ Sommese, Andrew J.; Verschelde, Jan; Wampler, Charles W. (2005). "Introduction to Numerical Algebraic Geometry". In Bronstein, Manuel; Cohen, Arjeh M.; Cohen, Henri; Eisenbud, David; Sturmfels, Bernd; Dickenstein, Alicia; Emiris, Ioannis Z. (eds.). Solving polynomial equations : foundations, algorithms, and applications (PDF). Springer-verlag. doi:10.1007/3-540-27357-3_8. ISBN 978-3-540-24326-7.
  3. ^ a b Leykin, Anton (2000-01-01). "Numerical algebraic geometry". Journal of Software for Algebra and Geometry. 3 (1): 5–10. doi:10.2140/jsag.2011.3.5. ISSN 1948-7916.
  4. ^ Sommese, Andrew J.; Wampler, II, Charles W. (2005). The numerical solution of systems of polynomials arising in engineering and science. World Scientific. ISBN 978-981-256-184-8.
  5. ^ a b Bates, Daniel J.; Sommese, Andrew J.; Hauenstein, Jonathan D; Wampler, Charles W. (2013). Numerically solving polynomial systems with Bertini. Society for Industrial and Applied Mathematics. ISBN 978-1-61197-269-6.
  6. ^ Chen, Tianran; Li, Tien-Yien (2015). "Homotopy continuation method for solving systems of nonlinear and polynomial equations". Communications in Information and Systems. 15 (2): 276–277. doi:10.4310/CIS.2015.v15.n2.a1.
  7. ^ Beltrán, Carlos; Leykin, Anton (2012-03-01). "Certified Numerical Homotopy Tracking". Experimental Mathematics. 21 (1): 69–83. arXiv:0912.0920. doi:10.1080/10586458.2011.606184. ISSN 1058-6458. S2CID 2889087.
  8. ^ Beltrán, Carlos; Leykin, Anton (2013-02-01). "Robust Certified Numerical Homotopy Tracking". Foundations of Computational Mathematics. 13 (2): 253–295. arXiv:1105.5992. doi:10.1007/s10208-013-9143-2. ISSN 1615-3375. S2CID 32990257.
  9. ^ a b Hauenstein, Jonathan D.; Sottile, Frank (August 2012). "Algorithm 921: alphaCertified: Certifying Solutions to Polynomial Systems". ACM Transactions on Mathematical Software. 38 (4): 1–20. doi:10.1145/2331130.2331136. S2CID 13821271.
  10. ^ Chen, T.; Lee, T. L.; Li, T. Y. (2014). "Hom4PS-3: A Parallel Numerical Solver for Systems of Polynomial Equations Based on Polyhedral Homotopy Continuation Methods". In Hong, H.; Yap, C. (eds.). Mathematical software -- ICMS 2014 : 4th International Congress, Seoul, South Korea, August 5-9, 2014. Proceedings. pp. 183–190. doi:10.1007/978-3-662-44199-2_30. ISBN 978-3-662-44199-2. Retrieved 28 April 2020.
  11. ^ Hom4PS Team. "Featured Products". Hom4PS-3. Michigan State University. Retrieved 28 April 2020.{{cite web}}: CS1 maint: numeric names: authors list (link)
  12. ^ Breiding, Paul; Timme, Sascha (May 2018). "HomotopyContinuation.jl: A package for homotopy continuation in Julia". arXiv:1711.10911v2 [cs.MS].
  13. ^ Verschelde, Jan (1 June 1999). "Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation". ACM Transactions on Mathematical Software. 25 (2): 251–276. doi:10.1145/317275.317286. S2CID 15485257.
edit