Computing Real Roots of Real Polynomials

Sagraloff, Michael; Mehlhorn, Kurt

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

成果報告書

Computing Real Roots of Real Polynomials

MPS-Authors

/persons/resource/persons45332

Sagraloff, Michael
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45021

Mehlhorn, Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

1308.4088v2
(プレプリント), 795KB

付随資料 (公開)

There is no public supplementary material available

引用

Sagraloff, M., & Mehlhorn, K. (2013). Computing Real Roots of Real Polynomials. Retrieved from http://arxiv.org/abs/1308.4088.

引用: https://hdl.handle.net/11858/00-001M-0000-0024-4591-A

要旨

Computing the real roots of a polynomial is a fundamental problem of computational algebra. We describe a variant of the Descartes method that isolates the real roots of any real square-free polynomial given through coefficient oracles. A coefficient oracle provides arbitrarily good approximations of the coefficients. The bit complexity of the algorithm matches the complexity of the best algorithm known, and the algorithm is simpler than this algorithm. The algorithm derives its speed from the combination of Descartes method with Newton iteration. Our algorithm can also be used to further refine the isolating intervals to an arbitrary small size. The complexity of root refinement is nearly optimal.