``Computing by the Numbers: Algorithms, Precision, and Complexity''
Workshop in Celebration of Richard Brent's 60th Birthday
July 20-21, 2006
Weierstrass Institute for Applied Analysis and Stochastics, Berlin.
TALK TITLE:
Complexity of Real Approximation: Brent Revisited
Chee Yap, Courant Institute and KIAS
ABSTRACT
Multiprecision computation is of growing importance,
both theoretically as well as practically.
It is an integral part of the foundation of a
theory of numerical and scientific computation.
Over 30 years ago, Brent showed through
a series of papers the efficiency of multiprecision arithmetic
for a large class of fundamental numerical functions.
His complexity bounds have remain unsurpassed today.
These results were formulated in an abstract model
using three axioms.
We re-examine these axioms from
the viewpoint of a general model of numerical approximations.
This leads to a number of issues:
- (1) Local versus global versus uniform complexity
- (2) Turing machine versus Sch\"onhage's pointer machines
- (3) Weak Mode versus Strong Mode of multiprecision computation
- (4) Asymptotic versus non-asymptotic error analysis
- (5) Exact versus inexact operations
- (6) Zero problems
We illustrate these issues with several
recent results. Such results suggests
that much ground work remains to be done in building
a complexity theory of multiprecision computation.