Univariate Algebraic Kernel and Application to Arrangements
Identifieur interne : 001386 ( Istex/Curation ); précédent : 001385; suivant : 001387Univariate 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
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :001403
Links to Exploration step
ISTEX:557D4E2A4E8CAD101547C8C8C470999145985253Le 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>
<affiliation wicri:level="1"><mods:affiliation>INRIA Nancy - Grand Est, LORIA, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>INRIA Nancy - Grand Est, LORIA</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: Sylvain.Lazard@inria.fr</mods:affiliation>
<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"><mods:affiliation>INRIA Nancy - Grand Est, LORIA, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>INRIA Nancy - Grand Est, LORIA</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: Luis.Penaranda@inria.fr</mods:affiliation>
<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"><mods:affiliation>INRIA Sophia-Antipolis - Méditerrané, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>INRIA Sophia-Antipolis - Méditerrané</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: Elias.Tsigaridas@inria.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</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>
</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"><mods:affiliation>INRIA Nancy - Grand Est, LORIA, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>INRIA Nancy - Grand Est, LORIA</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: Sylvain.Lazard@inria.fr</mods:affiliation>
<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"><mods:affiliation>INRIA Nancy - Grand Est, LORIA, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>INRIA Nancy - Grand Est, LORIA</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: Luis.Penaranda@inria.fr</mods:affiliation>
<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"><mods:affiliation>INRIA Sophia-Antipolis - Méditerrané, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>INRIA Sophia-Antipolis - Méditerrané</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: Elias.Tsigaridas@inria.fr</mods:affiliation>
<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>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001386 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 001386 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Istex |étape= Curation |type= RBID |clé= ISTEX:557D4E2A4E8CAD101547C8C8C470999145985253 |texte= Univariate Algebraic Kernel and Application to Arrangements }}
![]() | This area was generated with Dilib version V0.6.33. | ![]() |