English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  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

Basic

show hide
Genre: Journal Article
Latex : On the complexity of the {Descartes} method when using approximate arithmetic

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Sagraloff, Michael1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: Root isolation; Descartes method; Subdivision methods; Numerical computation; Complexity bounds; Approximate coefficients
 Abstract: 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

show
hide
Language(s): eng - English
 Dates: 2014-112014-11
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: Abstract
Keywords
1. Introduction
2. Preliminaries
3. A modified Descartes method
4. Algorithm
5. Conclusion
Acknowledgements
Appendix A.
References
 Rev. Type: -
 Identifiers: BibTex Citekey: Sagraloff201479
DOI: 10.1016/j.jsc.2014.01.005
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Journal of Symbolic Computation
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: Amsterdam : Elsevier
Pages: - Volume / Issue: 65 Sequence Number: - Start / End Page: 79 - 110 Identifier: ISSN: 0747-7171