Condition : the Geometry of Numerical Algorithms

Description

Condition Preface Motivation Structure Acknowledgements Contents Overture: On the Condition of Numerical Problems O.1 The Size of Errors O.2 The Cost of Erring O.3 Finite-Precision Arithmetic and Loss of Precision O.3.1 Precision … O.3.2 … and the Way We Lose It O.4 An Example: Matrix-Vector Multiplication O.5 The Many Faces of Condition O.5.1 Condition and Complexity O.5.2 Computing Condition Numbers O.5.3 Condition of Random Data O.5.4 Ill-posedness and Condition Part I: Condition in Linear Algebra (Adagio) Chapter 1: Normwise Condition of Linear Equation Solving 1.1 Vector and Matrix Norms 1.2 Turing's Condition Number 1.3 Condition and Distance to Ill-posedness 1.4 An Alternative Characterization of Condition 1.5 The Singular Value Decomposition 1.6 Least Squares and the Moore-Penrose Inverse Chapter 2: Probabilistic Analysis 2.1 A Crash Course on Integration Data Spaces and Measures Products of Data Spaces, Fubini's Theorem The Transformation Formula 2.2 A Crash Course on Probability: I 2.2.1 Basic Facts Densities and Probabilities Random Variables Pushforward Measures Independence Conditional Expectations 2.2.2 Gaussian Distributions 2.2.3 The chi2 Distribution 2.2.4 Uniform Distributions on Spheres 2.2.5 Expectations of Nonnegative Random Variables 2.2.6 Caps and Tubes in Spheres 2.2.7 Average and Smoothed Analyses 2.3 Probabilistic Analysis of Cwi(A,x) 2.4 Probabilistic Analysis of kappars(A) 2.4.1 Preconditioning 2.4.2 Average Analysis 2.4.3 Uniform Smoothed Analysis 2.5 Additional Considerations 2.5.1 Probabilistic Analysis for Other Norms 2.5.2 Probabilistic Analysis for Gaussian Distributions Chapter 3: Error Analysis of Triangular Linear Systems 3.1 Random Triangular Matrices Are Ill-conditioned 3.2 Backward Analysis of Triangular Linear Systems 3.3 Componentwise Condition of Random Sparse Matrices 3.3.1 Componentwise Condition Numbers 3.3.2 Determinant Computation 3.3.3 Matrix Inversion 3.3.4 Solving Linear Equations 3.4 Error Bounds for Triangular Linear Systems 3.5 Additional Considerations 3.5.1 On Norms and Mixed Condition Numbers 3.5.2 On the Underlying Probability Measure Chapter 4: Probabilistic Analysis of Rectangular Matrices 4.1 A Crash Course on Probability: II 4.1.1 Large Deviations 4.1.2 Random Gaussian Matrices 4.1.3 A Bound on the Expected Spectral Norm 4.2 Tail Bounds for kappa(A) 4.2.1 Tail Bounds for ||A†|| 4.2.2 Proof of Theorem 4.16 4.3 Expectations: Proof of Theorem 4.2 4.4 Complex Matrices Chapter 5: Condition Numbers and Iterative Algorithms 5.1 The Cost of Computing: A Primer in Complexity 5.2 The Method of Steepest Descent 5.3 The Method of Conjugate Gradients 5.4 Conjugate Gradient on Random Data Intermezzo I: Condition of Structured Data Part II: Condition in Linear Optimization (Andante) Chapter 6: A Condition Number for Polyhedral Conic Systems 6.1 Condition and Continuity 6.2 Basic Facts on Convexity 6.2.1 Convex Sets 6.2.2 Polyhedra 6.3 The Polyhedral Cone Feasibility Problem 6.4 The GCC Condition Number and Distance to Ill-posedness 6.5 The GCC Condition Number and Spherical Caps 6.6 The GCC Condition Number and Images of Balls 6.7 The GCC Condition Number and Well-Conditioned Solutions 6.8 Condition of Solutions and Condition Numbers 6.9 The Perceptron Algorithm for Feasible Cones Chapter 7: The Ellipsoid Method 7.1 A Few Facts About Ellipsoids 7.2 The Ellipsoid Method 7.3 Polyhedral Conic Systems with Integer Coefficients Chapter 8: Linear Programs and Their Solution Sets 8.1 Linear Programs and Duality 8.2 The Geometry of Solution Sets 8.3 The Combinatorics of Solution Sets 8.4 Ill-posedness and Degeneracy 8.4.1 Degeneracy 8.4.2 A Brief Discussion on Ill-posedness (a) Optimal Solution Problem (b) Optimal Basis Problem (c) Feasibility Problem (d) Optimal Value Problem Chapter 9: Interior-Point Methods 9.1 Primal-Dual Interior-Point Methods: Basic Ideas 9.2 Existence and Uniqueness of the Central Path 9.3 Analysis of IPM for Linear Programming 9.4 Condition-Based Analysis of IPM for PCFP 9.4.1 Reformulation 9.4.2 Algorithmic Solution 9.4.3 Analysis 9.5 Finite Precision for Decision and Counting Problems Chapter 10: The Linear Programming Feasibility Problem 10.1 A Condition Number for Polyhedral Feasibility 10.2 Deciding Feasibility of Primal-Dual Pairs Chapter 11: Condition and Linear Programming Optimization 11.1 The Condition Number K(d) 11.2 K(d) and Optimal Solutions 11.3 Computing the Optimal Basis 11.3.1 An Interior-Point Algorithm 11.3.2 A Reduction to Polyhedral Feasibility Problems 11.4 Optimizers and Optimal Bases: The Condition Viewpoint 11.5 Approximating the Optimal Value Chapter 12: Average Analysis of the RCC Condition Number 12.1 Proof of Theorem 12.1 12.1.1 The Group Gn and Its Action 12.1.2 Probabilities Chapter 13: Probabilistic Analyses of the GCC Condition Number 13.1 The Probability of Primal and Dual Feasibility 13.2 Spherical Convexity 13.3 A Bound on the Volume of Tubes 13.4 Two Essential Reductions 13.5 A Crash Course on Probability: III 13.6 Average Analysis 13.7 Smoothed Analysis Intermezzo II: The Condition of the Condition Part III: Condition in Polynomial Equation Solving (Allegro con brio) Chapter 14: A Geometric Framework for Condition Numbers 14.1 Condition Numbers Revisited 14.1.1 Complex Zeros of Univariate Polynomials 14.1.2 A Geometric Framework 14.1.3 Linear Equation Solving 14.2 Complex Projective Space 14.2.1 Projective Space as a Complex Manifold 14.2.2 Distances in Projective Space 14.3 Condition Measures on Manifolds 14.3.1 Eigenvalues and Eigenvectors 14.3.2 Computation of the Kernel Chapter 15: Homotopy Continuation and Newton's Method 15.1 Homotopy Methods 15.2 Newton's Method Chapter 16: Homogeneous Polynomial Systems 16.1 A Unitarily Invariant Inner Product 16.2 A Unitarily Invariant Condition Number 16.3 Orthogonal Decompositions of Hd 16.4 A Condition Number Theorem 16.5 Bézout's Theorem 16.6 A Projective Newton's Method 16.7 A Higher Derivative Estimate 16.8 A Lipschitz Estimate for the Condition Number Chapter 17: Smale's 17th Problem: I 17.1 The Adaptive Linear Homotopy for Hd 17.2 Interlude: Randomization 17.2.1 Randomized Algorithms 17.2.2 A Las Vegas Homotopy Method 17.3 A Crash Course on Probability: IV 17.4 Normal Jacobians of Projections 17.5 The Standard Distribution on the Solution Variety 17.6 Beltrán-Pardo Randomization 17.7 Analysis of Algorithm LV 17.8 Average Analysis of µnorm, µav, and µmax Chapter 18: Smale's 17th Problem: II 18.1 The Main Technical Result 18.1.1 Outline of the Proof 18.1.2 Normal Jacobians of Linearizations 18.1.3 Induced Probability Distributions 18.2 Smoothed Analysis of LV 18.3 Condition-Based Analysis of LV 18.4 A Near-Solution to Smale's 17th Problem 18.4.1 A Deterministic Homotopy Continuation 18.4.2 An Elimination Procedure for Zero-Finding 18.4.3 Some Inequalities of Combinatorial Numbers Chapter 19: Real Polynomial Systems 19.1 Homogeneous Systems with Real Coefficients 19.2 On the Condition for Real Zero-Counting 19.3 Smale's alpha-Theory 19.4 An Algorithm for Real Zero-Counting 19.4.1 Grids and Graphs 19.4.2 Proof of Theorem 19.1 19.5 On the Average Number of Real Zeros 19.6 Feasibility of Underdetermined and Semialgebraic Systems Chapter 20: Probabilistic Analysis of Conic Condition Numbers: I. The Complex Case 20.1 The Basic Idea 20.2 Volume of Tubes Around Linear Subspaces 20.3 Volume of Algebraic Varieties 20.4 A Crash Course on Probability: V 20.5 Proof of Theorem 20.1 20.6 Applications 20.6.1 Linear Equation-Solving 20.6.2 Eigenvalue Computations 20.6.3 Complex Polynomial Systems Chapter 21: Probabilistic Analysis of Conic Condition Numbers: II. The Real Case 21.1 On the Volume of Tubes 21.1.1 Curvature Integrals 21.1.2 Weyl's Tube Formula 21.2 A Crash Course on Probability: VI 21.3 Bounding Integrals of Curvature 21.4 Proof of Theorem 21.1 21.4.1 The Smooth Case 21.4.2 The General Case 21.4.3 Proof of Theorem 21.1 21.5 An Application 21.6 Tubes Around Convex Sets 21.6.1 Integrals of Curvature for Boundaries of Convex Sets 21.6.2 Proof of Theorem 13.18 21.7 Conic Condition Numbers and Structured Data 21.8 Smoothed Analysis for Adversarial Distributions Appendix A.1 Big Oh, Little Oh, and Other Comparisons A.2 Differential Geometry A.2.1 Submanifolds of Rn A.2.2 Abstract Smooth Manifolds A.2.3 Integration on Manifolds A.2.4 Sard's Theorem and Transversality A.2.5 Riemannian Metrics A.2.6 Orthogonal and Unitary Groups A.2.7 Curvature of Hypersurfaces A.3 Algebraic Geometry A.3.1 Varieties A.3.2 Dimension and Regular Points A.3.3 Elimination Theory A.3.4 Degree A.3.5 Resultant and Discriminant A.3.6 Volumes of Complex Projective Varieties A.4 Integral Geometry A.4.1 Poincaré's Formula A.4.2 The Principal Kinematic Formula Notes Overture Chapter 1 Chapter 2 Chapter 3 Chapter 4 Chapter 5 Intermezzo I Chapter 6 Chapter 7 Chapter 8 Chapter 9 Chapter 10 Chapter 11 Chapter 12 Chapter 13 Intermezzo II Chapter 14 Chapter 15 Chapter 16 Chapter 17 Chapter 18 Chapter 19 Chapter 20 Chapter 21 Coda: Open Problems P.1. Probabilistic Analysis of Growth Factors P.2. Eigenvalue Problem P.3. Smale's 9th Problem P.4. Smoothed Analysis of RCC Condition Number P.5. Improved Average Analysis of Grassmann Condition P.6. Smoothed Analysis of Grassmann Condition P.7. Robustness of Condition Numbers P.8. Average Complexity of IPMs for Linear Programming P.9. Smale's 17th Problem P.10. The Shub-Smale Starting System P.11. Equivariant Morse Function P.12. Good Starting Pairs in One Variable P.13. Approximating Condition Geodesics P.14. Self-Convexity of µnorm in Higher Degrees P.15. Structured Systems of Polynomial Equations P.16. Systems with Singularities P.17. Conic Condition Numbers of Real Problems with High Codimension of Ill-posedness P.18. Feasibility of Real Polynomial Systems Bibliography Notation … …Concepts … …and the People Who Crafted Them