Analytic Computational Complexity

Edited By J. F. Traub. Proceedings Of The Symposium On Analytic Computational Complexity, Held By The Computer Science Department, Carnegie-mellon University, Pittsburgh, Pennsylvania, On April 7-8, 1975. Includes Index. Includes Bibliographies. Content: Front Matter, Page iii Copyright, Page iv LIST OF INVITED AUTHORS, Page vii PREFACE, Page ix, J.F. Traub INTRODUCTION, Pages 1-4, J.F. Traub SOME REMARKS ON PROOF TECHNIQUES IN ANALYTIC COMPLEXITY, Pages 5-14, S. Winograd STRICT LOWER AND UPPER BOUNDS ON ITERATIVE COMPUTATIONAL COMPLEXITY, Pages 15-34, J.F. Traub, H. Woźniakowski THE COMPLEXITY OF OBTAINING STARTING POINTS FOR SOLVING OPERATOR EQUATIONS BY NEWTON'S METHOD, Pages 35-57, H.T. Kung A CLASS OF OPTIMAL-ORDER ZERO-FINDING METHODS USING DERIVATIVE EVALUATIONS, Pages 59-73, Richard P. Brent MAXIMAL ORDER OF MULTIPOINT ITERATIONS USING n EVALUATIONS, Pages 75-107, H. Woźniakowski OPTIMAL USE OF INFORMATION IN CERTAIN ITERATIVE PROCESSES, Pages 109-125, Robert MEERSMAN THE USE OF INTEGRALS IN THE SOLUTION OF NONLINEAR EQUATIONS IN N DIMENSIONS, Pages 127-141, B. Kacewicz Complexity and Differential Equations, Pages 143-149, M.H. SCHULTZ MULTIPLE-PRECISION ZERO-FINDING METHODS AND THE COMPLEXITY OF ELEMENTARY FUNCTION EVALUATION, Pages 151-176, Richard P. Brent NUMERICAL STABILITY OF ITERATIONS FOR SOLUTION OF NONLINEAR EQUATIONS AND LARGE LINEAR SYSTEMS, Pages 177-190, H. Woźniakowski ON THE COMPUTATIONAL COMPLEXITY OF APPROXIMATION OPERATORS II, Pages 191-204, JOHN R. RICE HENSEL MEETS NEWTON — ALGEBRAIC CONSTRUCTIONS IN AN ANALYTIC SETTING, Pages 205-215, DAVID Y.Y. YUN O((n log n)3/2) ALGORITHMS FOR COMPOSITION AND REVERSION OF POWER SERIES, Pages 217-225, Richard P. Brent, H.T. Kung K-PARALLEL SEARCH TECHNIQUES, Page 229, E. Arjomandi, D.G. Corneil ENTROPY MEASURES IN PROVING LOWER BOUNDS: A CASE STUDY, Page 231, Ian Munro ON THE ADDITIVE OPTIMALITY OF FAST ALGORITHMS FOR MATRIX MULTIPLICATION, Page 233, Robert L. Probert UPPER-BOUND TO THE TIME FOR PARALLEL EVALUATION OF ARITHMETIC EXPRESSIONS, Page 235, David D. Muller, Franco P. Preparata PARALLEL EVALUATION OF DIVISION-FREE EXPRESSIONS, Page 237, Franco P. Preparata, David E. Muller UPPER BOUNDS ON THE COMPUTATIONAL COMPLEXITY OF ORDINARY DIFFERENTIAL EQUATION INITIAL VALUE PROBLEMS, Page 239, Arthur G. Werschulz 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