Tutorial: Exact Numerical Computation in Algebra and Geometry

Tutorial:
Exact Numerical Computation
in Algebra and Geometry
Chee K. Yap
Courant Institute of Mathematical Sciences
New York University
and
Korea Institute of Advanced Study (KIAS)
Seoul, Korea
34th ISSAC, July 28–31, 2009
Yap (NYU) Tutorial: Exact Numerical Computation ISSAC, July 2009 1 / 113Tutorial: Exact Numerical Computation in Algebra
and Geometry
Many problems in Computational Science & Engineering (CS&E) 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 naturally incorporate iteration, subdivision and approximation into
our design of 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) ENC and Zero Problems
(b) Explicitization and Subdivision Algorithms
(c) Complexity Analysis of AdaptivityOverview of Tutorial
Background is algebraic and geometric computation
Motivation: much of computing world (CS&E) is continuous
But Theoretical Computer Science has gone completely discrete
The discrete view alone is inadequate for CS&E.
What role for exact computation in the continuum?
Geometric insights ...