Analytic Computational ComplexityJ.F. Traub Analytic Computational Complexity contains the proceedings of the Symposium on Analytic Computational Complexity held by the Computer Science Department, Carnegie-Mellon University, Pittsburgh, Pennsylvania, on April 7-8, 1975. The symposium provided a forum for assessing progress made in analytic computational complexity and covered topics ranging from strict lower and upper bounds on iterative computational complexity to numerical stability of iterations for solution of nonlinear equations and large linear systems. Comprised of 14 chapters, this book begins with an introduction to analytic computational complexity before turning to proof techniques used in analytic complexity. Subsequent chapters focus on the complexity of obtaining starting points for solving operator equations by Newton's method; maximal order of multipoint iterations using n evaluations; the use of integrals in the solution of nonlinear equations in N dimensions; and the complexity of differential equations. Algebraic constructions in an analytic setting are also discussed, along with the computational complexity of approximation operators. This monograph will be of interest to students and practitioners in the fields of applied mathematics and computer science. |
Contents
| 1 | |
| 5 | |
| 15 | |
CHAPTER 4
THE COMPLEXITY OF OBTAINING STARTING POINTS FOR SOLVING OPERATOR EQUATIONS BY NEWTONS METHOD | 35 |
CHAPTER 5
A CLASS OF OPTIMALORDER ZEROFINDING METHODS USING DERIVATIVE EVALUATIONS | 59 |
CHAPTER 6 MAXIMAL ORDER OF MULTIPOINT ITERATIONS USING n EVALUATIONS | 75 |
CHAPTER 7
OPTIMAL USE OF INFORMATION IN CERTAIN ITERATIVE PROCESSES | 109 |
CHAPTER 8
THE USE OF INTEGRALS IN THE SOLUTION OF NONLINEAR EQUATIONS IN N DIMENSIONS | 127 |
Chapter 9 Complexity and Differential Equations | 143 |
CHAPTER 10
MULTIPLEPRECISION ZEROFINDING METHODS AND THE COMPLEXITY OF ELEMENTARY FUNCTION EVALUATION | 151 |
CHAPTER 11
NUMERICAL STABILITY OF ITERATIONS FOR SOLUTION OF NONLINEAR EQUATIONS AND LARGE LINEAR SYSTEMS | 177 |
CHAPTER 12
ON THE COMPUTATIONAL COMPLEXITY OF APPROXIMATION OPERATORS II | 191 |
CHAPTER 13
HENSEL MEETS NEWTON ALGEBRAIC CONSTRUCTIONS IN AN ANALYTIC SETTING | 205 |
CHAPTER 14 ο n log n32 ALGORITHMS FOR COMPOSITION AND REVERSION OF POWER SERIES | 217 |
ABSTRACTS OF CONTRIBUTED PAPERS | 227 |
Other editions - View all
Common terms and phrases
algebraic Algorithm 4.2 analytic computational complexity arithmetic assume ation Banach spaces Birkhoff interpolation Brent 75 Carnegie-Mellon University comp complexity index Computer Science Computer Science Department consider defined denote Department of Computer derivatives efficient error coefficient evaluations of f example f satisfying finite formal power series function evaluations function f given Hence Hensel incidence matrix interpolation inverse inverse quadratic interpolation itera iteration phase Iterative Methods J. F. Traub Kacewicz 75 Kung and Traub Lemma lower bounds maximal order multiple-precision multiplication multipoint iterations Newton steps Newton's method Nonlinear Equations Note numerical stability obtain one-point operations Optimal Order order of information order of iteration p-adic paper polynomial power series precision problem prove root Runge-Kutta method Schultz search phase secant method Section Sharma 72 simple zero solve starting point technique Theorem 4.1 tion Traub 64 upper bound Winograd Wozniakowski 75 Zassenhaus zero-finding methods