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

DOI10.1016/J.JSC.2016.03.011MaRDI QIDQ346543zbMATH OpenOpenAlexFDO

Authors Rémi Imbach, Guillaume Moroz, Marc Pouget

Publication date 29 November 2016

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

Full work available at URL https://arxiv.org/abs/1412.3290, https://hal.inria.fr/hal-01402194/file/topo_res_disc2.pdf

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)

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.

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

Cites work

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

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

Describes a project that uses

Uses Software

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

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)