Efficient Isolation of a Polynomial Real Roots
Identifieur interne : 006B52 ( Main/Merge ); précédent : 006B51; suivant : 006B53Efficient Isolation of a Polynomial Real Roots
Auteurs : Fabrice Rouillier ; Paul ZimmermannSource :
- Journal of Computational and Applied Mathematics ; 2004.
English descriptors
- KwdEn :
Abstract
This paper revisits an algorithm isolating the real roots of a univariate polynomial using Descartes' rule of signs. It follows work of Vincent, Uspensky, Collins and Akritas, Johnson, Krandick. Our first contribution is a generic algorithm which enables one to describe all the known algorithms based on Descartes' rule of sign and the bissection strategy in a unified framework. Using that framework, a new algorithm is presented, which is optimal in terms of memory usage and as fast as both Collins and Akritas' algorithm and Krandick variant, independently of the input polynomial. From this new algorithm, we derive an adaptive semi-numerical version, using multi-precision interval arithmetic. We finally show that these critical optimizations have important consequences since our new algorithm still works with huge polynomials, including orthogonal polynomials of degree 1000 and more, which were out of reach of previous methods.
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: 003C70
- to stream Crin, to step Curation: 003C70
- to stream Crin, to step Checkpoint: 000677
Links to Exploration step
CRIN:rouillier02aLe document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="457">Efficient Isolation of a Polynomial Real Roots</title></titleStmt><publicationStmt><idno type="RBID">CRIN:rouillier02a</idno><date when="2004" year="2004">2004</date><idno type="wicri:Area/Crin/Corpus">003C70</idno><idno type="wicri:Area/Crin/Curation">003C70</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">003C70</idno><idno type="wicri:Area/Crin/Checkpoint">000677</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">000677</idno><idno type="wicri:Area/Main/Merge">006B52</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Efficient Isolation of a Polynomial Real Roots</title><author><name sortKey="Rouillier, Fabrice" sort="Rouillier, Fabrice" uniqKey="Rouillier F" first="Fabrice" last="Rouillier">Fabrice Rouillier</name></author><author><name sortKey="Zimmermann, Paul" sort="Zimmermann, Paul" uniqKey="Zimmermann P" first="Paul" last="Zimmermann">Paul Zimmermann</name></author></analytic><series><title level="j">Journal of Computational and Applied Mathematics</title><imprint><date when="2004" type="published">2004</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>descartes' rule</term><term>real root</term><term>univariate polynomial</term><term>uspensky</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="4039">This paper revisits an algorithm isolating the real roots of a univariate polynomial using Descartes' rule of signs. It follows work of Vincent, Uspensky, Collins and Akritas, Johnson, Krandick. Our first contribution is a generic algorithm which enables one to describe all the known algorithms based on Descartes' rule of sign and the bissection strategy in a unified framework. Using that framework, a new algorithm is presented, which is optimal in terms of memory usage and as fast as both Collins and Akritas' algorithm and Krandick variant, independently of the input polynomial. From this new algorithm, we derive an adaptive semi-numerical version, using multi-precision interval arithmetic. We finally show that these critical optimizations have important consequences since our new algorithm still works with huge polynomials, including orthogonal polynomials of degree 1000 and more, which were out of reach of previous methods.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006B52 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 006B52 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Merge
|type= RBID
|clé= CRIN:rouillier02a
|texte= Efficient Isolation of a Polynomial Real Roots
}}
| This area was generated with Dilib version V0.6.33. |  |