Skip to Main content Skip to Navigation

Computing Sampling Points on a Singular Real Hypersurface using Lagrange's System

Mohab Safey El Din 1, 2
1 SALSA - Solvers for Algebraic Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : Let $f$ be a polynomial in $\mathbbQ[X_1, ..., X_n]$ of degree bounded by $D$ and, for $t\in\mathbbQ$, $\mathcalH_t\subset\mathbbC^n$ the hypersurface defined by $f-t=0$. Consider a polynomial $\phi\in\mathbbQ[X_1, ..., X_n]$ and the mapping $\phi:\mathbbC^n\rightarrow\mathbbC$. Suppose the ideal $I$ generated by $\langleL.\mathbfgrad(f)-\mathbfgrad(\phi)\rangle$ is equi-dimensional, has dimension $1$ and the ideal $I+\langlef\rangle$ is zero-dimensional. In this case, we provide efficient algorithmic tools to compute the limits of the critical points of $\phi$ restricted to $\mathcalH_t$ when $t\rightarrow0$. We prove that for a generic choice of a point (resp. a line) the above result apply when $\phi$ is the square of the euclidean distance to the chosen point (resp. the projection on the chosen line). Then, we provide algorithms to compute at least one point in each connected component of $\mathcalH_0\cap\mathbbR^n$ which based on the improved computation of the limits of the critical points of a polynomial mapping restricted to $\mathcalH_t$. The worst-case complexity of our algorithms is polynomial in $D^n$ in terms of arithmetic operations in $\mathbbQ$. We prove it improves previous strategies based on the use of infinitesimal arithmetic. Practical experiments confirm these are the first algorithms dealing with this problem mixing practical efficiency and asymptotically optimal complexity.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 8:49:00 PM
Last modification on : Tuesday, January 12, 2021 - 9:36:03 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:26:25 PM


  • HAL Id : inria-00070542, version 1


Mohab Safey El Din. Computing Sampling Points on a Singular Real Hypersurface using Lagrange's System. [Research Report] RR-5464, INRIA. 2005, pp.19. ⟨inria-00070542⟩



Record views


Files downloads