TY - GEN
T1 - Empirical study of an evaluation-based subdivision algorithm for complex root isolation
AU - Kamath, Narayan
AU - Voiculescu, Irina
AU - Yap, Chee K.
N1 - Funding Information:
This study was carried out with research grants from the Instituto de Salud Carlos III (FIS PS09/02417 and RETIC REDINSCOR RD06/0003/0010) and the Generalitat Valenciana (PROMETEO 2010/093), Spain.
PY - 2011
Y1 - 2011
N2 - We provide an empirical study of subdivision algorithms for isolating the simple roots of a polynomial in any desired box region B 0 of the complex plane. One such class of algorithms is based on Newton-like interval methods (Moore, Krawczyk, Hansen-Sengupta). Another class of subdivision algorithms is based on function evaluation. Here, Yakoubsohn discussed a method that is purely based on an exclusion predicate. Recently, Sagraloff and Yap introduced another algorithm of this type, called Ceval. We describe the first implementation of Ceval in Core Library. We compare its performance to the above mentioned algorithms, and also to the well-known MPSolve software from Bini and Florentino. Our results suggest that certified evaluation-based methods such as Ceval are encouraging and deserve further exploration.
AB - We provide an empirical study of subdivision algorithms for isolating the simple roots of a polynomial in any desired box region B 0 of the complex plane. One such class of algorithms is based on Newton-like interval methods (Moore, Krawczyk, Hansen-Sengupta). Another class of subdivision algorithms is based on function evaluation. Here, Yakoubsohn discussed a method that is purely based on an exclusion predicate. Recently, Sagraloff and Yap introduced another algorithm of this type, called Ceval. We describe the first implementation of Ceval in Core Library. We compare its performance to the above mentioned algorithms, and also to the well-known MPSolve software from Bini and Florentino. Our results suggest that certified evaluation-based methods such as Ceval are encouraging and deserve further exploration.
KW - Ceval algorithm interval Newton methods
KW - Complex root isolation
KW - Solving bi-variate systems
KW - Subdivision algorithms
UR - http://www.scopus.com/inward/record.url?scp=84865024604&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84865024604&partnerID=8YFLogxK
U2 - 10.1145/2331684.2331710
DO - 10.1145/2331684.2331710
M3 - Conference contribution
AN - SCOPUS:84865024604
SN - 9781450305150
T3 - SNC'11 - Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation
SP - 155
EP - 164
BT - SNC'11 - Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation
T2 - SNC'11 - Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation
Y2 - 7 June 2011 through 9 June 2011
ER -