Condition : the geometry of numerical algorithms
 Author/Creator
 Bürgisser, Peter, 1962 author.
 Language
 English.
 Publication
 Berlin : Springer, 2013.
 Physical description
 xxxi, 554 pages : illustrations ; 25 cm.
 Series
 Grundlehren der mathematischen Wissenschaften ; 349.
Access
Available online

Stacks

Unknown
QA297 .B954 2013

Unknown
QA297 .B954 2013
More options
Contributors
 Contributor
 Cucker, Felipe, 1958 author.
Contents/Summary
 Contents

 Condition in linear algebra (adagio)
 Normwise condition of linear equation solving
 Vector and matrix norms
 Turing's condition number
 Condition and distance to illposedness
 An alternative characterization of condition
 The singular value decomposition
 Least squares and the MoorePenrose inverse
 Probabilistic analysis
 A crash course on integration
 A crash course on probability : I
 Basic facts
 Gaussian distributions
 The X² Distribution
 Uniform distributions on spheres
 Expectations of nonnegative random variables
 Caps and tubes in spheres
 Average and smoothed analyses
 Probabilistic analysis of Cwi (A, x)
 Probabilistic analysis of Krs (A)
 Preconditioning
 Average analysis
 Uniform smoothed analysis
 Additional considerations
 Probabilistic analysis for other norms
 Probabilistic analysis for Gaussian distributions
 Error analysis of triangular linear systems
 Random triangular matrices are illconditioned
 Backward analysis of triangular linear systems
 Componentwise condition of random sparse matrices
 Componentwise condition numbers
 Determinant computation
 Matrix inversion
 Solving linear equations
 Error bounds for triangular linear systems
 Additional considerations
 On norms and mixed condition numbers
 On the underlying probability measure
 Probabilistic analysis of rectangular matrices
 A crash course on probability : II
 Large deviations
 Random Gaussian matrices
 A bound on the expected spectral norm
 Tail bounds for k(A)
 Tail bounds for (A)
 Proof of theorem 4.16
 Expectations : proof of theorem 4.2
 Complex matrices
 Condition numbers and iterative algorithms
 The cost of computing : a primer in complexity
 The method of steepest descent
 The method of conjugate gradients
 Conjugate gradient on random data
 Intermezzo I : condition of structured data
 Condition in linear optimization (Andante)
 A condition number for polyhedral conic systems
 Condition and continuity
 Basic facts on convexity
 Convex sets
 Polyhedra
 The polyhedral cone feasibility problem
 The GCC condition number and distance to illposedness
 The GCC condition number and spherical caps
 The GCC condition number and images of balls
 The GCC condition number and wellconditioned solutions
 Condition of solutions and condition numbers
 The perceptron algorithm for feasible cones
 The ellipsoid method
 A few facts about ellipsoids
 The ellipsoid method
 Polyhedral conic systems with integer coefficients
 Linear programs and their solution sets
 Linear programs and duality
 The geometry of solution sets
 The combinatorics of solution sets
 Illposedness and degeneracy
 Degeneracy
 A brief discussion on illposedness
 Interiorpoint methods
 Primaldual interiorpoint methods : basic ideas
 Existence and uniqueness of the central path
 Analysis of IPM for linear programming
 Conditionbased analysis of IPM for PCFP
 Reformulation
 Algorithmic solution
 Analysis
 Finite precision for decision and counting problems
 The linear programming feasibility problem
 A condition number for polyhedral feasibility
 Deciding feasibility of primaldual pairs
 Condition and linear programming optimization
 The condition number K (d)
 K(d) and optimal solutions
 Computing the optimal basis
 An interiorpoint algorithm
 A reduction to polyhedral feasibility problems
 Optimizers and optimal bases : the condition viewpoint
 Approximating the optimal value
 Average analysis of the RCC condition number
 Proof of theorem 12.1
 The group ... and its action
 Probabilities
 Probabilistic analyses of the GCC condition number
 The probability of primal and dual feasibility
 Spherical convexity
 A bound on the volume of tubes
 Two essential reductions
 A crash course on probability : III
 Average analysis
 Smoothed analysis
 Intermezzo II : the condition of the condition
 Condition in polynomial equation solving (allegro con brio)
 A geometric framework for condition numbers
 Condition numbers revisited
 Complex zeros of univariate polynomials
 A geometric framework
 Linear equation solving
 Complex projective space
 Projective space as a complex manifold
 Distances in projective space
 Condition measures on manifolds
 Eigenvalues and eigenvectors
 Computation of the Kernel
 Homotopy continuation and Newton's method
 Homotopy methods
 Newton's method
 Homogeneous polynomial systems
 A unitarily invariant inner product
 A unitarily invariant condition number
 Orthogonal decompositions of Hd
 A condition number theorem
 Bézout's theorem
 A projective Newton's method
 A higher derivative estimate
 A lipschitz estimate for the condition number
 Smale's 17th problem : I
 The adaptive linear homotopy for Hd
 Interlude : randomization
 Randomized algorithms
 A Las Vegas homotopy method
 A crash course on probability : IV
 Normal Jacobians of projections
 The standard distribution on the solution variety
 Beltránpardo randomization
 Analysis of algorithm LV
 Average analysis of unorm, uav, and umax
 Smale's 17th problem : II
 The main technical result
 Outline of the proof
 Normal Jacobians of linearizations
 Induced probability distributions
 Smoothed analysis of LV
 Conditionbased analysis of LV
 A nearsolution to smale's 17th problem
 A deterministic homotopy continuation
 An elimination procedure for zerofinding
 Some inequalities of combinatorial numbers
 Real polynomial systems
 Homogeneous systems with real coefficients
 On the condition for real zerocounting
 Smale's atheory
 An algorithm for real zerocounting
 Grids and graphs
 Proof of theorem 19.1
 On the average number of real zeros
 Feasibility of underdetermined and semialgebraic systems
 Probabilistic analysis of conic condition numbers : I. the complex case
 The basic idea
 Volume of tubes around linear subspaces
 Volume of algebraic varieties
 A crash course on probability : V
 Proof of theorem 20.1
 Applications
 Linear equationsolving
 Eigenvalue computations
 Complex polynomial systems
 Probabilistic analysis of conic condition numbers : II. the real case
 On the volume of tubes
 Curvature Integrals
 Weyl's tube formula
 A crash course on probability : VI
 Bounding integrals of curvature
 Proof of theorem 21.1
 The smooth case
 The general case
 Proof of theorem 21.1
 An application
 Tubes around convex sets
 Integrals of curvature for boundaries of convex sets
 Proof of theorem 13.18
 Conic condition numbers and structured data
 Smoothed analysis for adversarial distributions
 Appendix
 Big oh, little oh, and other comparisons
 Differential geometry
 Submanifolds of Rn
 Abstract smooth manifolds
 Integration on manifolds
 Sard's theorem and transversality
 Riemannian metrics
 Orthogonal and unitary groups
 Curvature of hypersurfaces
 Algebraic geometry
 Varieties
 Dimension and regular points
 Elimination theory
 Degree
 Resultant and discriminant
 Volumes of complex projective varieties
 Integral geometry
 Poincaré's formula
 The principal kinematic formula
 Notes
 Coda : open problems
 Probabilistic analysis of growth factors
 Eigenvalue problem
 Smale's 9th problem
 Smoothed analysis of RCC condition number
 Improved average analysis of Grassmann condition
 Smoothed analysis of Grassmann condition
 Robustness of condition numbers
 Average complexity of IPMs for linear programming
 Smale's 17th problem
 The shubsmale starting system
 Equivariant Morse function
 Good starting pairs in one variable
 Approximating condition geodesies
 Selfconvexity of unorm in higher degrees
 Structured systems of polynomial equations
 Systems with singularities
 Conic condition numbers of real problems with high codimension of illposedness
 Feasibility of real polynomial systems
 Bibliography
 Notation
  concepts
  and the people who crafted them.
 Publisher's Summary
 This book gathers threads that have evolved across different mathematical disciplines into seamless narrative. It deals with condition as a main aspect in the understanding of the performance regarding both stability and complexity of numerical algorithms. While the role of condition was shaped in the last halfcentury, so far there has not been a monograph treating this subject in a uniform and systematic way. The book puts special emphasis on the probabilistic analysis of numerical algorithms via the analysis of the corresponding condition. The exposition's level increases along the book, starting in the context of linear algebra at an undergraduate level and reaching in its third part the recent developments and partial solutions for Smale's 17th problem which can be explained within a graduate course. Its middle part contains a conditionbased course on linear programming that fills a gap between the current elementary expositions of the subject based on the simplex method and those focusing on convex programming.
(source: Nielsen Book Data)
Subjects
Bibliographic information
 Publication date
 2013
 Responsibility
 by Peter Bürgisser, Felipe Cucker.
 Series
 Grundlehren der mathematischen Wissenschaften ; 349
 ISBN
 9783642388958 (hbk.)
 3642388957 (hbk.)
 9783642388965 (eBook)
 3642388965 (eBook)