Real Root Isolation of Polynomial Equations Based on Hybrid Computation

Fei Shen (), Wenyuan Wu () and Bican Xia ()
Additional contact information
Fei Shen: Peking University, LMAM & School of Mathematical Sciences
Wenyuan Wu: Chongqing Institute of Green and Intelligent Technology, Chinese Academy of Sciences
Bican Xia: Peking University, LMAM & School of Mathematical Sciences

A chapter in Computer Mathematics, 2014, pp 375-396 from Springer

Abstract: Abstract A new algorithm for real root isolation of zero-dimensional nonsingular square polynomial systems based on hybrid computation is presented in this paper. First, approximate the (complex) roots of the given polynomial equations via homotopy continuation method. Then, for each approximate root, an initial box relying on the Kantorovich theorem is constructed, which contains the corresponding accurate root. Finally, the Krawczyk interval iteration with interval arithmetic is applied to the initial boxes so as to check whether or not the corresponding approximate roots are real and to obtain the real root isolation boxes. Moreover, an empirical construction of initial box is provided for speeding-up the computation in practice. Our experiments on many benchmarks show that the new hybrid method is very efficient. The method can find all real roots of any given zero-dimensional nonsingular square polynomial systems provided that the homotopy continuation method can find all complex roots of the equations.

Keywords: Real Root Isolation; Approximate Root; Homotopy Continuation Method; Iteration Interval; Accurate Root (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-662-43799-5_26

Ordering information: This item can be ordered from
http://www.springer.com/9783662437995

DOI: 10.1007/978-3-662-43799-5_26

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().