Univariate Algebraic Kernel and Application to Arrangements
Identifieur interne : 003876 ( Main/Exploration ); précédent : 003875; suivant : 003877Univariate Algebraic Kernel and Application to Arrangements
Auteurs : Sylvain Lazard [France] ; Luis Pe Aranda [France] ; Elias Tsigaridas [France]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: We present a cgal-based univariate algebraic kernel, which provides certified real-root isolation of univariate polynomials with integer coefficients and standard functionalities such as basic arithmetic operations, greatest common divisor (gcd) and square-free factorization, as well as comparison and sign evaluations of real algebraic numbers. We compare our kernel with other comparable kernels, demonstrating the efficiency of our approach. Our experiments are performed on large data sets including polynomials of high degree (up to 2 000) and with very large coefficients (up to 25 000 bits per coefficient). We also address the problem of computing arrangements of x-monotone polynomial curves. We apply our kernel to this problem and demonstrate its efficiency compared to previous solutions available in cgal.
Url:
DOI: 10.1007/978-3-642-02011-7_20
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001403
- to stream Istex, to step Curation: 001386
- to stream Istex, to step Checkpoint: 000983
- to stream Main, to step Merge: 003954
- to stream Main, to step Curation: 003876
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Univariate Algebraic Kernel and Application to Arrangements</title>
<author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name>
</author>
<author><name sortKey="Pe Aranda, Luis" sort="Pe Aranda, Luis" uniqKey="Pe Aranda L" first="Luis" last="Pe Aranda">Luis Pe Aranda</name>
</author>
<author><name sortKey="Tsigaridas, Elias" sort="Tsigaridas, Elias" uniqKey="Tsigaridas E" first="Elias" last="Tsigaridas">Elias Tsigaridas</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:557D4E2A4E8CAD101547C8C8C470999145985253</idno>
<date when="2009" year="2009">2009</date>
<idno type="doi">10.1007/978-3-642-02011-7_20</idno>
<idno type="url">https://api.istex.fr/ark:/67375/HCB-JB9XD61P-9/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001403</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001403</idno>
<idno type="wicri:Area/Istex/Curation">001386</idno>
<idno type="wicri:Area/Istex/Checkpoint">000983</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000983</idno>
<idno type="wicri:doubleKey">0302-9743:2009:Lazard S:univariate:algebraic:kernel</idno>
<idno type="wicri:Area/Main/Merge">003954</idno>
<idno type="wicri:Area/Main/Curation">003876</idno>
<idno type="wicri:Area/Main/Exploration">003876</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Univariate Algebraic Kernel and Application to Arrangements</title>
<author><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name>
<affiliation wicri:level="1"><country xml:lang="fr">France</country>
<wicri:regionArea>INRIA Nancy - Grand Est, LORIA</wicri:regionArea>
<wicri:noRegion>LORIA</wicri:noRegion>
<wicri:noRegion>LORIA</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Pe Aranda, Luis" sort="Pe Aranda, Luis" uniqKey="Pe Aranda L" first="Luis" last="Pe Aranda">Luis Pe Aranda</name>
<affiliation wicri:level="1"><country xml:lang="fr">France</country>
<wicri:regionArea>INRIA Nancy - Grand Est, LORIA</wicri:regionArea>
<wicri:noRegion>LORIA</wicri:noRegion>
<wicri:noRegion>LORIA</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Tsigaridas, Elias" sort="Tsigaridas, Elias" uniqKey="Tsigaridas E" first="Elias" last="Tsigaridas">Elias Tsigaridas</name>
<affiliation wicri:level="1"><country xml:lang="fr">France</country>
<wicri:regionArea>INRIA Sophia-Antipolis - Méditerrané</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: We present a cgal-based univariate algebraic kernel, which provides certified real-root isolation of univariate polynomials with integer coefficients and standard functionalities such as basic arithmetic operations, greatest common divisor (gcd) and square-free factorization, as well as comparison and sign evaluations of real algebraic numbers. We compare our kernel with other comparable kernels, demonstrating the efficiency of our approach. Our experiments are performed on large data sets including polynomials of high degree (up to 2 000) and with very large coefficients (up to 25 000 bits per coefficient). We also address the problem of computing arrangements of x-monotone polynomial curves. We apply our kernel to this problem and demonstrate its efficiency compared to previous solutions available in cgal.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
</country>
</list>
<tree><country name="France"><noRegion><name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name>
</noRegion>
<name sortKey="Lazard, Sylvain" sort="Lazard, Sylvain" uniqKey="Lazard S" first="Sylvain" last="Lazard">Sylvain Lazard</name>
<name sortKey="Pe Aranda, Luis" sort="Pe Aranda, Luis" uniqKey="Pe Aranda L" first="Luis" last="Pe Aranda">Luis Pe Aranda</name>
<name sortKey="Pe Aranda, Luis" sort="Pe Aranda, Luis" uniqKey="Pe Aranda L" first="Luis" last="Pe Aranda">Luis Pe Aranda</name>
<name sortKey="Tsigaridas, Elias" sort="Tsigaridas, Elias" uniqKey="Tsigaridas E" first="Elias" last="Tsigaridas">Elias Tsigaridas</name>
<name sortKey="Tsigaridas, Elias" sort="Tsigaridas, Elias" uniqKey="Tsigaridas E" first="Elias" last="Tsigaridas">Elias Tsigaridas</name>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003876 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 003876 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Main |étape= Exploration |type= RBID |clé= ISTEX:557D4E2A4E8CAD101547C8C8C470999145985253 |texte= Univariate Algebraic Kernel and Application to Arrangements }}
This area was generated with Dilib version V0.6.33. |