TY - GEN
T1 - Evaluating Straight-Line Programs over Balls
AU - Van Der Hoeven, Joris
AU - Lecerf, Grégoire
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/9/7
Y1 - 2016/9/7
N2 - Interval arithmetic achieves numerical reliability for a wide range of applications, at the price of a performance penalty. For applications to homotopy continuation, one key ingredient is the efficient and reliable evaluation of complex polynomials represented by straight-line programs. This is best achieved using ball arithmetic, a variant of interval arithmetic. In this article, we describe strategies for reducing the performance penalty of basic operations on balls. We also show how to bound the effect of rounding errors at the global level of evaluating a straight-line program. This allows us to introduce a new and faster "transient" variant of ball arithmetic.
AB - Interval arithmetic achieves numerical reliability for a wide range of applications, at the price of a performance penalty. For applications to homotopy continuation, one key ingredient is the efficient and reliable evaluation of complex polynomials represented by straight-line programs. This is best achieved using ball arithmetic, a variant of interval arithmetic. In this article, we describe strategies for reducing the performance penalty of basic operations on balls. We also show how to bound the effect of rounding errors at the global level of evaluating a straight-line program. This allows us to introduce a new and faster "transient" variant of ball arithmetic.
KW - ball arithmetic
KW - polynomial evaluation
KW - software implementation
UR - https://www.scopus.com/pages/publications/84988985308
U2 - 10.1109/ARITH.2016.12
DO - 10.1109/ARITH.2016.12
M3 - Conference contribution
AN - SCOPUS:84988985308
T3 - Proceedings - Symposium on Computer Arithmetic
SP - 142
EP - 149
BT - Proceedings - 2016 IEEE 23rd Symposium on Computer Arithmetic, ARITH 2016
A2 - Hormigo, Javier
A2 - Revol, Nathalie
A2 - Montuschi, Paolo
A2 - Oberman, Stuart
A2 - Schulte, Michael
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 23rd IEEE Symposium on Computer Arithmetic, ARITH 2016
Y2 - 10 July 2016 through 13 July 2016
ER -