A certified numerical algorithm for the topology of resultant and discriminant curves

DOI10.1016/J.JSC.2016.03.011zbMATH Open1354.14052arXiv1412.3290OpenAlexW2315753911MaRDI QIDQ346543FDOQ346543

Authors: Rémi Imbach, Guillaume Moroz, Marc Pouget 

Publication date: 29 November 2016

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Abstract: Let $mathcalC$ be a real plane algebraic curve defined by the resultant of two polynomials (resp. by the discriminant of a polynomial). Geometrically such a curve is the projection of the intersection of the surfaces $P(x,y,z)=Q(x,y,z)=0$ (resp. $P(x,y,z)=fracpartialPpartialz(x,y,z)=0$), and generically its singularities are nodes (resp. nodes and ordinary cusps). State-of-the-art numerical algorithms compute the topology of smooth curves but usually fail to certify the topology of singular ones. The main challenge is to find practical numerical criteria that guarantee the existence and the uniqueness of a singularity inside a given box $B$, while ensuring that $B$ does not contain any closed loop of $mathcalC$. We solve this problem by first providing a square deflation system, based on subresultants, that can be used to certify numerically whether $B$ contains a unique singularity $p$ or not. Then we introduce a numeric adaptive separation criterion based on interval arithmetic to ensure that the topology of $mathcalC$ in $B$ is homeomorphic to the local topology at $p$. Our algorithms are implemented and experiments show their efficiency compared to state-of-the-art symbolic or homotopic methods.

Full work available at URL: https://arxiv.org/abs/1412.3290

Recommendations

• On the topology of real algebraic plane curves
• On the topology of planar algebraic curves
• Certified numerical algorithm for isolating the singularities of the plane projection of generic smooth space curves
• On the computation of the topology of plane curves
• On the topology and visualization of plane algebraic curves

zbMATH Keywords

discriminantsingularitiesinterval arithmeticnumerical algorithmresultantnode and cusp singularitiessubresultanttopology of algebraic curves

Mathematics Subject Classification ID

Singularities of curves, local rings (14H20) Plane and space curves (14H50) Real algebraic sets (14P05) Computational aspects of algebraic curves (14Q05) Numerical algorithms for computer arithmetic, etc. (65Y04)

Cites Work

• HOM4PS-2.0: a software package for solving polynomial systems by the polyhedral homotopy continuation method
• Rigorous global search: continuous problems
• Efficient isolation of polynomial's real roots.
• ISOLATE
• On the exact computation of the topology of real algebraic curves
• Using Algebraic Geometry
• Fixed points, zeros and Newton's method
• Derived eigenvalues of symmetric matrices, with applications to distance geometry
• Newton's method with deflation for isolated singularities of polynomial systems
• On the complexity of solving a bivariate polynomial system
• Deflation algorithm for the multiple roots of a system of nonlinear equations
• Topology and arrangement computation of semi-algebraic planar curves
• Homotopies for solving polynomial systems within a bounded domain
• Explicit factors of some iterated resultants and discriminants
• Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken
• Algorithm 921: alphaCertified: certifying solutions to polynomial systems
• Exclusion Regions for Systems of Equations
• An elementary approach to subresultants theory.
• Robust certified numerical homotopy tracking
• On the number of branches of an 1-dimensional semianalytic set
• Computing the topology of a real algebraic plane curve whose defining equations are available only ``by values
• A numerical approach to compute the topology of the apparent contour of a smooth mapping from \(\mathbb{R}^2\) to \(\mathbb{R}^2\)
• Motivations for an arbitrary precision interval arithmetic and the MPFI library
• Title not available (Why is that?)
• Safe Starting Regions for Iterative Methods
• Title not available (Why is that?)
• Empirical Evaluation of Innovations in Interval Branch and Bound Algorithms for Nonlinear Systems
• Deflation and certified isolation of singular zeros of polynomial systems
• Title not available (Why is that?)
• Certified parallelotope continuation for one-manifolds
• Adaptive isotopic approximation of nonsingular curves: The parameterizability and nonlocal isotopy approach
• Finding all real points of a complex curve
• On the topology of real algebraic plane curves
• On location and approximation of clusters of zeros: Case of embedding dimension one

Cited In (4)

• Visualizing planar and space implicit real algebraic curves with singularities
• Certified numerical algorithm for isolating the singularities of the plane projection of generic smooth space curves
• Reliable Computation of the Singularities of the Projection in $$\mathbb R^3$$ of a Generic Surface of $$\mathbb R^4$$
• Subresultants of several univariate polynomials in Newton basis

Uses Software

• HOM4PS
• MPFI
• INTOPT_90
• Bertini
• alphaCertified
• ISOLATE
• insulate

This page was built for publication: A certified numerical algorithm for the topology of resultant and discriminant curves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q346543)