``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.

Conference Site: http://www.mathematik.hu-berlin.de/%7Egaggle/EVENTS/2006/BRENT60/

Complexity of Real Approximation: Brent Revisited
Chee Yap, Courant Institute and KIAS


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: 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.