Math 2.0

Numerical analysis Definition

Homotopy continuation for polynomial systems

Builds on Numerical continuationPolynomials in several variablesComplex numbersBézout's theoremHomotopy

Definition

Let f=(f1,…,fn)f = (f_1, \dots, f_n) be a system of polynomials in nn variables with complex coefficients, and let di≥1d_i \ge 1 be the degree of fif_i. Let g=(g1,…,gn)g = (g_1, \dots, g_n) be a start system with known solutions. An example is the total-degree start system gi(x)=xidi−1g_i(x) = x_i^{d_i} - 1, whose d1d2⋯dnd_1 d_2 \cdots d_n solutions are the tuples of roots of unity. Fix a complex number γ\gamma and define the homotopy H(x,t)=(1−t) γ g(x)+t f(x),x∈ℂn, t∈[0,1].H(x, t) = (1 - t) \, \gamma \, g(x) + t \, f(x), \qquad x \in \C^n, \ t \in [0, 1]. Homotopy continuation for ff is the following procedure. For each solution x0x_0 of gg, it follows the path x(t)x(t) with H(x(t),t)=0H(x(t), t) = 0 and x(0)=x0x(0) = x_0 by numerical continuation, for tt from 00 towards 11. It returns the limits of x(t)x(t) as t→1t \to 1.

Remarks

With the total-degree start system and a generic choice of γ\gamma, the paths are smooth and do not meet for t∈[0,1)t \in [0, 1). Every isolated solution of ff is then the limit of at least one path, and the number of paths is the Bézout number d1⋯dnd_1 \cdots d_n, the bound of Bézout's theorem. Choosing γ\gamma at random is called the gamma trick; with probability one it avoids the values of γ\gamma for which paths collide or blow up before t=1t = 1. Example: for f(x)=x2−4f(x) = x^2 - 4 in one variable, g(x)=x2−1g(x) = x^2 - 1 and γ=1\gamma = 1, one gets H(x,t)=x2−1−3tH(x, t) = x^2 - 1 - 3t, and the two paths x(t)=±1+3tx(t) = \pm\sqrt{1 + 3t} start at ±1\pm 1 and end at ±2\pm 2. Non-example: with γ=−1\gamma = -1 and the same ff and gg, one gets H(x,t)=(2t−1)x2+1−5tH(x, t) = (2t - 1) x^2 + 1 - 5t, whose leading coefficient vanishes at t=1/2t = 1/2, so both paths go to infinity there and the procedure fails. Some paths may diverge or end at singular or non-isolated solutions; practical codes detect and handle these endgames.

Reading path

To understand this page from the ground up, read these 24 pages in order. The foundations come first.

Show the path as a graph
Complex numbers, object, no evidence levelComplex numbersobjectGroup, concept, no evidence levelGroupconceptHomotopy, concept, no evidence levelHomotopyconceptIntersection multiplicity, concept, no evidence levelIntersection multipli…conceptIntersection theory, concept, no evidence levelIntersection theoryconceptNumerical continuation, concept, no evidence levelNumerical continuationconceptPlane curve, concept, no evidence levelPlane curveconceptPolynomials in several variables, concept, no evidence levelPolynomials in severa…conceptProjective space, concept, no evidence levelProjective spaceconceptRing, definition, no evidence levelRingdefinitionCommutative ring, definition, no evidence levelCommutative ringdefinitionPolynomial ring, definition, no evidence levelPolynomial ringdefinitionUnit of a ring, definition, no evidence levelUnit of a ringdefinitionZero divisor, definition, no evidence levelZero divisordefinitionField, definition, no evidence levelFielddefinitionPolynomial evaluation, definition, no evidence levelPolynomial evaluationdefinitionIntegral domain, definition, no evidence levelIntegral domaindefinitionRoot of a polynomial, definition, no evidence levelRoot of a polynomialdefinitionIrreducible element, definition, no evidence levelIrreducible elementdefinitionSplit polynomial, definition, no evidence levelSplit polynomialdefinitionIrreducible polynomial, definition, no evidence levelIrreducible polynomialdefinitionAlgebraically closed field, definition, no evidence levelAlgebraically closed …definitionBézout's theorem, statement, no evidence levelBézout's theoremstatementHomotopy continuation for polynomial systems, definition, no evidence levelHomotopy continuation…definition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Complex numbers object
  2. Group concept
  3. Homotopy concept
  4. Intersection multiplicity concept
  5. Intersection theory concept
  6. Numerical continuation concept
  7. Plane curve concept
  8. Polynomials in several variables concept
  9. Projective space concept
  10. Ring definition
  11. Commutative ring definition
  12. Polynomial ring definition
  13. Unit of a ring definition
  14. Zero divisor definition
  15. Field definition
  16. Polynomial evaluation definition
  17. Integral domain definition
  18. Root of a polynomial definition
  19. Irreducible element definition
  20. Split polynomial definition
  21. Irreducible polynomial definition
  22. Algebraically closed field definition
  23. Bézout's theorem statement
  24. Homotopy continuation for polynomial systems definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Numerical_algebraic_geometry
About this page
TagF9FTASTFSX
URIm2://F9FTASTFSX
Kinddefinition
WritingW0 stub
MSC65H14, 65H20, 14Q65
DefinesHomotopy continuation for polynomial systems
UsesNumerical continuation, Polynomials in several variables, Complex numbers, Bézout's theorem, Homotopy

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.