InforLorV4, Main, Curation, bibRecord, 00A157

Real Solving for Positive Dimensional Systems

Identifieur interne : 00A157 ( Main/Curation ); précédent : 00A156; suivant : 00A158

Real Solving for Positive Dimensional Systems

Auteurs : Philippe Aubry [France] ; Fabrice Rouillier [France] ; M. Safey El Din [France]

Source :

RBID : Hal:inria-00072654

English descriptors

mix :
- connected components, grobner bases, polynomial systems, real algebraic variety, real roots, triangular sets.

Abstract

Finding one point on each semi-algebraically connected component of a real algebraic variety, or at least deciding if such a variety is empty or not, is a fundamental problem of computational real algebraic geometry. Even though numerous studies have been done on the subject, only a few number of efficient implementations exists. In this paper, we propose a new efficient and practical algorithm for computing such points. By studying the critical points of the restriction to the variety of the distance function to one well chosen point, we show how to provide a set of zero-dimensional systems whose zeroes contain at least one point on each semi-algebraically connected component of the studied variety, without any assumption neither on the variety (smoothness or compactness for example) nor on the system of equations that define it. Once such a result is computed, one can then apply, for each computed zero-dimensional system, any symbolic or numerical algorithm for counting or approximating the solutions. We have made experiments using a set of pure exact methods. The practical efficiency of our method is due to the fact that we do not apply any infinitesimal deformations, conversely to the existing methods based on similar strategy.

Url:

https://hal.inria.fr/inria-00072654

Links toward previous steps (curation, corpus...)

to stream Hal, to step Corpus: Pour aller vers cette notice dans l'étape Curation :003F63
to stream Hal, to step Curation: Pour aller vers cette notice dans l'étape Curation :003F63
to stream Hal, to step Checkpoint: Pour aller vers cette notice dans l'étape Curation :006171
to stream Main, to step Merge: Pour aller vers cette notice dans l'étape Curation :00A805

Links to Exploration step

Hal:inria-00072654

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Real Solving for Positive Dimensional Systems</title>
<author><name sortKey="Aubry, Philippe" sort="Aubry, Philippe" uniqKey="Aubry P" first="Philippe" last="Aubry">Philippe Aubry</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-233" status="VALID"><idno type="RNSR">199712651U</idno>
<orgName>Laboratoire d'Informatique de Paris 6</orgName>
<orgName type="acronym">LIP6</orgName>
<desc><address><addrLine>4 Place JUSSIEU 75252 PARIS CEDEX 05</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.lip6.fr/</ref>
</desc>
<listRelation><relation active="#struct-93591" type="direct"></relation>
<relation name="UMR7606" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-93591" type="direct"><org type="institution" xml:id="struct-93591" status="VALID"><orgName>Université Pierre et Marie Curie - Paris 6</orgName>
<orgName type="acronym">UPMC</orgName>
<desc><address><addrLine>4 place Jussieu - 75005 Paris</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.upmc.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7606" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Rouillier, Fabrice" sort="Rouillier, Fabrice" uniqKey="Rouillier F" first="Fabrice" last="Rouillier">Fabrice Rouillier</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2343" status="OLD"><idno type="RNSR">199822082R</idno>
<orgName>Polynomials, Combinatorics, Arithmetic</orgName>
<orgName type="acronym">POLKA</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/polka</ref>
</desc>
<listRelation><relation active="#struct-160" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-300291" type="indirect"></relation>
<relation active="#struct-300292" type="indirect"></relation>
<relation active="#struct-300293" type="indirect"></relation>
<relation active="#struct-2496" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-300291" type="direct"></relation>
<relation active="#struct-300292" type="direct"></relation>
<relation active="#struct-300293" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName>
<orgName type="acronym">UHP</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName>
<orgName type="acronym">INPL</orgName>
<date type="end">2011-12-31</date>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université Nancy 2</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Institut national polytechnique de Lorraine</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
</affiliation>
</author>
<author><name sortKey="Safey El Din, M" sort="Safey El Din, M" uniqKey="Safey El Din M" first="M." last="Safey El Din">M. Safey El Din</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-233" status="VALID"><idno type="RNSR">199712651U</idno>
<orgName>Laboratoire d'Informatique de Paris 6</orgName>
<orgName type="acronym">LIP6</orgName>
<desc><address><addrLine>4 Place JUSSIEU 75252 PARIS CEDEX 05</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.lip6.fr/</ref>
</desc>
<listRelation><relation active="#struct-93591" type="direct"></relation>
<relation name="UMR7606" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-93591" type="direct"><org type="institution" xml:id="struct-93591" status="VALID"><orgName>Université Pierre et Marie Curie - Paris 6</orgName>
<orgName type="acronym">UPMC</orgName>
<desc><address><addrLine>4 place Jussieu - 75005 Paris</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.upmc.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7606" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:inria-00072654</idno>
<idno type="halId">inria-00072654</idno>
<idno type="halUri">https://hal.inria.fr/inria-00072654</idno>
<idno type="url">https://hal.inria.fr/inria-00072654</idno>
<date when="2000">2000</date>
<idno type="wicri:Area/Hal/Corpus">003F63</idno>
<idno type="wicri:Area/Hal/Curation">003F63</idno>
<idno type="wicri:Area/Hal/Checkpoint">006171</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">006171</idno>
<idno type="wicri:Area/Main/Merge">00A805</idno>
<idno type="wicri:Area/Main/Curation">00A157</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Real Solving for Positive Dimensional Systems</title>
<author><name sortKey="Aubry, Philippe" sort="Aubry, Philippe" uniqKey="Aubry P" first="Philippe" last="Aubry">Philippe Aubry</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-233" status="VALID"><idno type="RNSR">199712651U</idno>
<orgName>Laboratoire d'Informatique de Paris 6</orgName>
<orgName type="acronym">LIP6</orgName>
<desc><address><addrLine>4 Place JUSSIEU 75252 PARIS CEDEX 05</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.lip6.fr/</ref>
</desc>
<listRelation><relation active="#struct-93591" type="direct"></relation>
<relation name="UMR7606" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-93591" type="direct"><org type="institution" xml:id="struct-93591" status="VALID"><orgName>Université Pierre et Marie Curie - Paris 6</orgName>
<orgName type="acronym">UPMC</orgName>
<desc><address><addrLine>4 place Jussieu - 75005 Paris</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.upmc.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7606" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Rouillier, Fabrice" sort="Rouillier, Fabrice" uniqKey="Rouillier F" first="Fabrice" last="Rouillier">Fabrice Rouillier</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2343" status="OLD"><idno type="RNSR">199822082R</idno>
<orgName>Polynomials, Combinatorics, Arithmetic</orgName>
<orgName type="acronym">POLKA</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/polka</ref>
</desc>
<listRelation><relation active="#struct-160" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-300291" type="indirect"></relation>
<relation active="#struct-300292" type="indirect"></relation>
<relation active="#struct-300293" type="indirect"></relation>
<relation active="#struct-2496" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-300291" type="direct"></relation>
<relation active="#struct-300292" type="direct"></relation>
<relation active="#struct-300293" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName>
<orgName type="acronym">UHP</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName>
<date type="end">2011-12-31</date>
<desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName>
<orgName type="acronym">INPL</orgName>
<date type="end">2011-12-31</date>
<desc><address><country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName>
<desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université Nancy 2</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
<placeName><settlement type="city">Nancy</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Institut national polytechnique de Lorraine</orgName>
<orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName>
</affiliation>
</author>
<author><name sortKey="Safey El Din, M" sort="Safey El Din, M" uniqKey="Safey El Din M" first="M." last="Safey El Din">M. Safey El Din</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-233" status="VALID"><idno type="RNSR">199712651U</idno>
<orgName>Laboratoire d'Informatique de Paris 6</orgName>
<orgName type="acronym">LIP6</orgName>
<desc><address><addrLine>4 Place JUSSIEU 75252 PARIS CEDEX 05</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.lip6.fr/</ref>
</desc>
<listRelation><relation active="#struct-93591" type="direct"></relation>
<relation name="UMR7606" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-93591" type="direct"><org type="institution" xml:id="struct-93591" status="VALID"><orgName>Université Pierre et Marie Curie - Paris 6</orgName>
<orgName type="acronym">UPMC</orgName>
<desc><address><addrLine>4 place Jussieu - 75005 Paris</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.upmc.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7606" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>connected components</term>
<term>grobner bases</term>
<term>polynomial systems</term>
<term>real algebraic variety</term>
<term>real roots</term>
<term>triangular sets</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Finding one point on each semi-algebraically connected component of a real algebraic variety, or at least deciding if such a variety is empty or not, is a fundamental problem of computational real algebraic geometry. Even though numerous studies have been done on the subject, only a few number of efficient implementations exists. In this paper, we propose a new efficient and practical algorithm for computing such points. By studying the critical points of the restriction to the variety of the distance function to one well chosen point, we show how to provide a set of zero-dimensional systems whose zeroes contain at least one point on each semi-algebraically connected component of the studied variety, without any assumption neither on the variety (smoothness or compactness for example) nor on the system of equations that define it. Once such a result is computed, one can then apply, for each computed zero-dimensional system, any symbolic or numerical algorithm for counting or approximating the solutions. We have made experiments using a set of pure exact methods. The practical efficiency of our method is due to the fact that we do not apply any infinitesimal deformations, conversely to the existing methods based on similar strategy.</div>
</front>
</TEI>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Curation

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00A157 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Curation/biblio.hfd -nk 00A157 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Curation
   |type=    RBID
   |clé=     Hal:inria-00072654
   |texte=   Real Solving for Positive Dimensional Systems
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

Real Solving for Positive Dimensional Systems

Real Solving for Positive Dimensional Systems

Source :

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri