Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study

DOI10.1016/j.jco.2004.09.008zbMath1098.65052OpenAlexW1967910430MaRDI QIDQ2387419

Mariano De Leo, Ezequiel Dratman, Guillermo Matera

Publication date: 2 September 2005

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2004.09.008

zbMATH Keywords

complexitypositive solutionspolynomial systemshomotopy methodssymbolic methodssemi-linear parabolic problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Numerical computation of solutions to systems of equations (65H10) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20) Real polynomials: location of zeros (26C10) Complexity and performance of numerical algorithms (65Y20)

Related Items

On the solution of the polynomial systems arising in the discretization of certain ODEs, Approximation of the solution of certain nonlinear ODEs with linear complexity, A concise proof of the Kronecker polynomial system solver from scratch, Efficient approximation of the solution of certain nonlinear reaction-diffusion equations with small absorption, Newton's method and a mesh-independence principle for certain semilinear boundary-value problems

Uses Software

• Kronecker

Cites Work

• Polynomial equation solving by lifting procedures for ramified fibers
• Deformation techniques to solve generalised Pham systems
• Bernstein's theorem in affine space
• Definability and fast quantifier elimination in algebraically closed fields
• Geometric theory of semilinear parabolic equations
• Blowup in diffusion equations: A survey
• Two-sided bounds on the inverses of diagonally dominant tridiagonal matrices
• Lower bounds for diophantine approximations
• Straight-line programs in geometric elimination theory
• The hardness of polynomial equation solving
• Computing parametric geometric resolutions
• Algebraic Geometry. I: Complex projective varieties.
• Blow-up in quasilinear parabolic equations. Transl. from the Russian by Michael Grinfeld
• Mixed-volume computation by dynamic lifting applied to polynomial system solving
• Deformation techniques for efficient polynomial equation solving.
• On the efficiency of effective Nullstellensätze
• Numerical Decomposition of the Solution Sets of Polynomial Systems into Irreducible Components
• The Role of Critical Exponents in Blowup Theorems
• The intrinsic complexity of parametric elimination methods
• Homotopies Exploiting Newton Polytopes for Solving Sparse Polynomial Systems
• Blow-up vs. spurious steady solutions
• NUMERICAL BLOW-UP FOR A NONLINEAR PROBLEM WITH A NONLINEAR BOUNDARY CONDITION
• What can be computed in algebraic geometry?
• A Product-Decomposition Bound for Bezout Numbers
• Moving Mesh Methods for Problems with Blow-Up
• A Polyhedral Method for Solving Sparse Polynomial Systems
• Solving Real Polynomial Systems with Real Homotopies
• Sylvester-Habicht sequences and fast Cauchy index computation
• On the time-space complexity of geometric elimination procedures
• A Gröbner free alternative for polynomial system solving
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item