TY - GEN

T1 - Exact numerical computation in algebra and geometry

AU - Yap, Chee K.

PY - 2009

Y1 - 2009

N2 - Many problems in Computational Science & Engineering (CSE) are defined on the continuum. Standard algorithms for these problems are numerical and approximate. Their computational techniques include iteration, subdivision, and approximation. Such techniques are rarely seen in exact or algebraic algorithms. In this tutorial, we discuss a mode of computation called exact numerical computation (ENC) that achieves exactness through numerical approximation. Through ENC, we can naturally incorporate iteration, subdivision and approximation into the design of exact algorithms for computer algebra and computational geometry. Such algorithms are both novel and practical. This tutorial on ENC is divided into three equal parts: (a) Zero Problems (b) Explicitation Problems (c) Techniques and Complexity Analysis of Adaptivity.

AB - Many problems in Computational Science & Engineering (CSE) are defined on the continuum. Standard algorithms for these problems are numerical and approximate. Their computational techniques include iteration, subdivision, and approximation. Such techniques are rarely seen in exact or algebraic algorithms. In this tutorial, we discuss a mode of computation called exact numerical computation (ENC) that achieves exactness through numerical approximation. Through ENC, we can naturally incorporate iteration, subdivision and approximation into the design of exact algorithms for computer algebra and computational geometry. Such algorithms are both novel and practical. This tutorial on ENC is divided into three equal parts: (a) Zero Problems (b) Explicitation Problems (c) Techniques and Complexity Analysis of Adaptivity.

KW - Adaptive complexity analysis

KW - Exact numerical computation

KW - Explicitization problems

KW - Numerical algebraic computation

KW - Numerical computational geometry

KW - Zero bounds

UR - http://www.scopus.com/inward/record.url?scp=77950415436&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77950415436&partnerID=8YFLogxK

U2 - 10.1145/1576702.1576757

DO - 10.1145/1576702.1576757

M3 - Conference contribution

AN - SCOPUS:77950415436

SN - 9781605586090

T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

SP - 387

EP - 388

BT - ISSAC 2009 - Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation

T2 - 2009 International Symposium on Symbolic and Algebraic Computation, ISSAC 2009

Y2 - 28 July 2009 through 31 July 2009

ER -