Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  On the Complexity of the Descartes Method when Using Approximate Arithmetic

Sagraloff, M. (2014). On the Complexity of the Descartes Method when Using Approximate Arithmetic. Journal of Symbolic Computation, 65, 79-110. doi:10.1016/j.jsc.2014.01.005.

Item is

Basisdaten

einblenden: ausblenden:
Genre: Zeitschriftenartikel
Latex : On the complexity of the {Descartes} method when using approximate arithmetic

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Sagraloff, Michael1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: Root isolation; Descartes method; Subdivision methods; Numerical computation; Complexity bounds; Approximate coefficients
 Zusammenfassung: In this paper, we introduce a variant of the Descartes method to isolate the real roots of a square-free polynomial F ( x ) = ∑ i = 0 n A i x i with arbitrary real coefficients. It is assumed that each coefficient of F can be approximated to any specified error bound. Our algorithm uses approximate arithmetic only, nevertheless, it is certified, complete and deterministic. We further provide a bound on the complexity of our method which exclusively depends on the geometry of the roots and not on the complexity of the coefficients of F. For the special case, where F is a polynomial of degree n with integer coefficients of maximal bitsize τ, our bound on the bit complexity writes as O ˜ ( n 3 τ 2 ) . Compared to the complexity of the classical Descartes method from Collins and Akritas (based on ideas dating back to Vincent), which uses exact rational arithmetic, this constitutes an improvement by a factor of n. The improvement mainly stems from the fact that the maximal precision that is needed for isolating the roots of F is by a factor n lower than the precision needed when using exact arithmetic.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2014-112014-11
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: Abstract
Keywords
1. Introduction
2. Preliminaries
3. A modified Descartes method
4. Algorithm
5. Conclusion
Acknowledgements
Appendix A.
References
 Art der Begutachtung: -
 Identifikatoren: BibTex Citekey: Sagraloff201479
DOI: 10.1016/j.jsc.2014.01.005
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Journal of Symbolic Computation
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Amsterdam : Elsevier
Seiten: - Band / Heft: 65 Artikelnummer: - Start- / Endseite: 79 - 110 Identifikator: ISSN: 0747-7171