HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00070542
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 8:49:00 PM
Last modification on : Friday, February 4, 2022 - 3:07:41 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:26:25 PM

Identifiers

  • HAL Id : inria-00070542, version 1

Citation

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⟩

Share

Metrics

Record views

83

Files downloads

61