Traub Analytic Computational Complexity

1. Auflage 2014
ISBN: 978-1-4832-5789-1
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 250 Seiten, Web PDF

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.

Autoren/Hrsg.

Traub, J. F.

Inhaltsverzeichnis

1;Front Cover;1
2;Analytic
Computational Complexity;4
3;Copyright Page;5
4;Table of Contents;6
5;LIST OF INVITED AUTHORS;8
6;PREFACE;10
7;CHAPTER 1.
INTRODUCTION;12
8;CHAPTER 2.
SOME REMARKS ON PROOF TECHNIQUES IN ANALYTIC COMPLEXITY;16
8.1;References;25
9;CHAPTER 3.
STRICT LÖWER AND UPPER BOUNDS ON ITERATIVE COMPUTATIONAL COMPLEXITY;26
9.1;1. INTRODUCTION;26
9.2;2. BASIC CONCEPTS;28
9.3;3. BOUNDS ON THE ERROR COEFFICIENT FUNCTION;32
9.4;4. THE VARIABLE ERROR COEFFICIENT MODEL;37
9.5;5. BOUNDS ON THE COMPLEXITY INDEX;39
9.6;6. SUMMARY AND EXTENS IONS TO THE MODEL;43
9.7;ACKNOWLEDCMNT;44
9.8;REFERENCES;44
10;CHAPTER 4.
THE COMPLEXITY OF OBTAINING STARTING POINTS FOR SOLVING OPERATOR EQUATIONS BY NEWTON'S METHOD;46
10.1;1. INTRODUCTION;46
10.2;2. METHODOLOGY AND A USEFUL LEMMA FOR PROVING LOWER BOUNDS;48
10.3;3. SOME RESULTS ON REAL VALUED FUNCTIONS OF ONE VARIABLE;50
10.4;4. A PROCEDURE TO OBTAIN GOOD STARTING POINTS FOR NEWTON'S
METHOD;54
10.5;5. SUMMARY AND CONCLUSIONS;66
10.6;ACKNOWLEDGMENTS;67
10.7;REFERENCES;67
11;CHAPTER 5.
A CLASS OF OPTIMAL-ORDER ZERO-FINDING METHODS USING DERIVATIVE EVALUATIONS;70
11.1;1. INTRODUCTION;70
11.2;2. MOTIVATION;72
11.3;3. A SIXTH-ORDER METHOD;73
11.4;4. METHODS OF ORDER 2v;76
11.5;5. RELATED NONLINEAR RUNGE-KUTTA METHODS;78
11.6;6. SOME NUMERICAL RESULTS;79
11.7;7. OTHER ZERO-FINDING METHODS;80
11.8;8. ACKNOWLEDGEMENT;82
11.9;REFERENCES;82
12;CHAPTER 6. MAXIMAL ORDER OF MULTIPOINT ITERATIONS USING n EVALUATIONS;86
12.1;1. INTRODUCTION;86
12.2;2. THE n-EVALUATION PROBLEM;87
12.3;3. EXISTENCE OF ITERATIONS;94
12.4;4. HERMITIAN INFORMATION;98
12.5;5. GENERAL INFORMATION, m = 0;109
12.6;6. FINAL REMARKS;115
12.7;ACKNCWLEDGMENT;117
12.8;REFERENCES;117
13;CHAPTER 7.
OPTIMAL USE OF INFORMATION IN CERTAIN ITERATIVE PROCESSES;120
13.1;1. Introduction;120
13.2;2. Some known results and conjectures;121
13.3;3. A solution to problem 1 for n = 3;123
13.4;4. A solution to a "problem 2" for . = Brent information.;131
13.5;References;135
14;CHAPTER 8.
THE USE OF INTEGRALS IN THE SOLUTION OF NONLINEAR EQUATIONS IN N DIMENSIONS;138
14.1;1. INTRODUCTION;139
14.2;2. AN INTERPOLATORY-INTEGRAL ITERATION I_ 1,s;140
14.3;3. ORDER OF THE INTEGRAL INFORMATION;144
14.4;4. COMPLEXITY INDEX;149
14.5;5. INTEGRAL INFORMATION WITH KERNELS;150
14.6;ACKNOWLEDGMENT;152
14.7;6. REFERENCES;152
15;Chapter 9. Complexity and Differential Equations;154
15.1;1. INTRODUCTION;154
15.2;2. GENERALIZED INTERPOLATION PROBLEMS;155
15.3;3. SPARSE LINEAR SYSTEMS;156
15.4;4. SPARSE NONLINEAR SYSTEMS;158
15.5;REFERENCES;159
16;CHAPTER 10.
MULTIPLE-PRECISION ZERO-FINDING METHODS AND THE COMPLEXITY OF ELEMENTARY FUNCTION EVALUATION;162
16.1;1. INTRODUCTION;162
16.2;2. BASIC MULTIPLE-PRECISION OPERATIONS;164
16.3;3. VARIABLE-PRECISION ZERO-FINDING METHODS;166
16.4;4. A VARIABLE-PRECISION SECANT METHOD;169
16.5;5. OTHER VARIABLE-PRECISION INTERPOLATORY METHODS;170
16.6;6. VARIABLE-PRECISION METHODS USING DERIVATIVES;172
16.7;7. THE ARITHMETIC-GEOMETRIC MEAN ITERATION;173
16.8;8. FAST MULTIPLE-PRECISION EVALUATION OF p;175
16.9;9. MULTIPLE-PRECISION EVALUATION OF LOG(X);177
16.10;10. MULTIPLE-PRECISION EVALUATION OF EXP(X);179
16.11;11. MULTIPLE-PRECISION OPERATIONS ON COMPLEX NUMBERS;180
16.12;12. MULTIPLE-PRECISION EVALUATION OF TRIGONOMETRIC FUNCTIONS;181
16.13;13. OPERATIONS ON FORMAL POWER SERIES;183
16.14;REFERENCES;186
17;CHAPTER 11.
NUMERICAL STABILITY OF ITERATIONS FOR SOLUTION OF NONLINEAR EQUATIONS AND LARGE LINEAR SYSTEMS;188
17.1;1. INTRODUCTION;189
17.2;2. NUMERICAL STABILITY OF ITERATIONS FOR NONLINEAR EQUATIONS;189
17.3;3. NUMERICAL STABILITY OF ITERATIONS FOR LARGE LINEAR SYSTEMS;194
17.4;REFERENCES;200
18;CHAPTER 12.
ON THE COMPUTATIONAL COMPLEXITY OF APPROXIMATION OPERATORS II;202
18.1;1. INTRODUCTION;202
18.2;2. DISCRETIZATION;204
18.3;3. LEAST SQUARES APPROXIMATION BY POLYNOMIALS;204
18.4;4. TCHEBYCHEFF APPROXIMATION BY POLYNOMIALS;209
18.5;5. PIECEWISE POLYNOMIAL APPROXIMATION;212
18.6;REFERENCES;214
19;CHAPTER 13.
HENSEL MEETS NEWTON ALGEBRAIC CONSTRUCTIONS IN AN ANALYTIC SETTING;216
19.1;1. INTRODUCTION;216
19.2;2. P-ADIC REPRESENTATION;217
19.3;3.0 NEWTON'S ITERATION;219
19.4;4. ORDER OF CONVERGENCE VERSUS COMPUTATIONAL EFFICIENCY;222
19.5;5. DISCUSSION AND CONCLUSION;224
19.6;REFERENCES;225
20;CHAPTER 14. . ((n log n)3/2) ALGORITHMS FOR COMPOSITION AND REVERSION OF POWER SERIES;228
20.1;1. INTRODUCTION;229
20.2;2. PRELIMINARY LEMMAS;230
20.3;3. THE COMPOSITION PROBLEM;232
20.4;4. THE REVERSION PROBLEM;234
20.5;ACKNOWLEDGMENT;235
20.6;REFERENCES;235
21;ABSTRACTS OF CONTRIBUTED PAPERS;238
21.1;K-PARALLEL SEARCH TECHNIQUES;240
21.2;ENTROPY MEASURES IN PROVING LOWER BOUNDS: A CASE STUDY;242
21.3;ON THE ADDITIVE OPTIMALITY OF FAST ALGORITHMS
FOR MATRIX MULTIPLICATION;244
21.4;UPPER-BOUND TO THE TIME FOR PARALLEL EVALUATION
OF ARITHMETIC EXPRESSIONS;246
21.5;PARALLEL EVALUATION OF DIVISION-FREE EXPRESSIONS;248
21.6;UPPER BOUNDS ON THE COIPUTATIONAL COMPLEXITY OF
ORDINARY DIFFERENTIAL EQUATION INITIAL VALUE PROBLEMS;250