jump to search box

Condition : the geometry of numerical algorithms / by Peter Bürgisser, Felipe Cucker.

Availability

At the Library

Other libraries

Author/Creator:
Bürgisser, Peter, 1962- author.
Language:
English.
Publication date:
2013
Publication:
Berlin : Springer, 2013.
Format:
  • Book
  • xxxi, 554 pages : illustrations ; 25 cm.
Contents:
  • Condition in linear algebra (adagio)
  • Normwise condition of linear equation solving
  • Vector and matrix norms
  • Turing's condition number
  • Condition and distance to ill-posedness
  • An alternative characterization of condition
  • The singular value decomposition
  • Least squares and the Moore-Penrose 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 ill-conditioned
  • 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 ill-posedness
  • The GCC condition number and spherical caps
  • The GCC condition number and images of balls
  • The GCC condition number and well-conditioned 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
  • Ill-posedness and degeneracy
  • Degeneracy
  • A brief discussion on ill-posedness
  • Interior-point methods
  • Primal-dual interior-point methods : basic ideas
  • Existence and uniqueness of the central path
  • Analysis of IPM for linear programming
  • Condition-based 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 primal-dual pairs
  • Condition and linear programming optimization
  • The condition number K (d)
  • K(d) and optimal solutions
  • Computing the optimal basis
  • An interior-point 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án-pardo 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
  • Condition-based analysis of LV
  • A near-solution to smale's 17th problem
  • A deterministic homotopy continuation
  • An elimination procedure for zero-finding
  • Some inequalities of combinatorial numbers
  • Real polynomial systems
  • Homogeneous systems with real coefficients
  • On the condition for real zero-counting
  • Smale's a-theory
  • An algorithm for real zero-counting
  • 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 equation-solving
  • 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 shub-smale starting system
  • Equivariant Morse function
  • Good starting pairs in one variable
  • Approximating condition geodesies
  • Self-convexity of u-norm in higher degrees
  • Structured systems of polynomial equations
  • Systems with singularities
  • Conic condition numbers of real problems with high codimension of ill-posedness
  • Feasibility of real polynomial systems
  • Bibliography
  • Notation
  • -- concepts
  • -- and the people who crafted them.
Contributor:
Cucker, Felipe, 1958- author.
Series:
Grundlehren der mathematischen Wissenschaften ; 349.
Subjects:
ISBN:
9783642388958
3642388957

powered by Blacklight
© Stanford University. Stanford, California 94305. (650) 725-1064. Terms of Use | Copyright Complaints | Opt Out of Analytics
jump to top