TY - GEN
T1 - An approach for certifying homotopy continuation paths
T2 - 43rd ACM International Symposium on Symbolic and Algebraic Computation, ISSAC 2018
AU - Xu, Juan
AU - Burr, Michael
AU - Yap, Chee
N1 - Publisher Copyright:
© 2018 Association for Computing Machinery.
PY - 2018/7/11
Y1 - 2018/7/11
N2 - Homotopy continuation is a well-known method in numerical root-finding. Recently, certified algorithms for homotopy continuation based on Smale’s alpha-theory have been developed. This approach enforces very strong requirements at each step, leading to small step sizes. In this paper, we propose an approach that is independent of alpha-theory. It is based on the weaker notion of well-isolated approximations to the roots. We apply it to univariate polynomials and provide experimental evidence of its feasibility.
AB - Homotopy continuation is a well-known method in numerical root-finding. Recently, certified algorithms for homotopy continuation based on Smale’s alpha-theory have been developed. This approach enforces very strong requirements at each step, leading to small step sizes. In this paper, we propose an approach that is independent of alpha-theory. It is based on the weaker notion of well-isolated approximations to the roots. We apply it to univariate polynomials and provide experimental evidence of its feasibility.
KW - Certified Computation
KW - Homotopy Continuation
KW - Interval Arithmetic
KW - Well-Isolated Roots
UR - http://www.scopus.com/inward/record.url?scp=85054934434&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85054934434&partnerID=8YFLogxK
U2 - 10.1145/3208976.3209010
DO - 10.1145/3208976.3209010
M3 - Conference contribution
AN - SCOPUS:85054934434
T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC
SP - 399
EP - 406
BT - ISSAC 2018 - Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation
PB - Association for Computing Machinery
Y2 - 16 July 2018 through 19 July 2018
ER -