A Comparative Study of Two Real Root Isolation Methods
Recent progress in polynomial elimination has rendered the computation of the real roots of ill-conditioned polynomials of high degree (over 1000) with huge coefficients (several thousand digits) a critical operation in computer algebra. To rise to the occasion, the only method-candidate that has...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Vilnius University Press
2005-10-01
|
| Series: | Nonlinear Analysis |
| Subjects: | |
| Online Access: | http://www.zurnalai.vu.lt/nonlinear-analysis/article/view/15110 |
| Summary: | Recent progress in polynomial elimination has rendered the computation of the real roots of ill-conditioned polynomials of high degree (over 1000) with huge coefficients (several thousand digits) a critical operation in computer algebra.
To rise to the occasion, the only method-candidate that has been considered by various authors for modification and improvement has been the Collins-Akritas bisection method [1], which is a based on a variation of Vincent’s theorem [2].
The most recent example is the paper by Rouillier and Zimmermann [3], where the authors present “... a new algorithm, which is optimal in terms of memory usage and as fast as both Collins and Akritas’ algorithm and Krandick variant ...” [3]
In this paper we compare our own continued fractions method CF [4] (which is directly based on Vincent’s theorem) with the best bisection method REL described in [3]. Experimentation with the data presented in [3] showed that, with respect to time, our continued fractions method CF is by far superior to REL, whereas the two are about equal with respect to space. |
|---|---|
| ISSN: | 1392-5113 2335-8963 |