Directed Cholesky factorizations and applications

Ferenc Domes (ferenc.domesunivie.ac.at)
Arnold Neumaier (arnold.neumaierunivie.ac.at)

Abstract: In exact arithmetic, the Cholesky factorization of a nonsingular symmetric matrix exists iff the matrix is positive definite. Several applications require safe tests for definiteness or to derive valid inequalities that use computations involving a Cholesky factorization. This paper introduces directed versions of the Cholesky factorization, from which rigorous conclusions can be drawn in spite of rounding errors. Applications are given to checking definiteness and to finding tight box enclosures for ellipsoids defined by strictly convex quadratic inequalities. This also provides a convenient preprocessing step for constrained optimization problems. Numerical tests show that even nearly singular problems can be handled successfully.

Keywords: directed Cholesky factorization, interval analysis, constraint satisfaction problems, bounding ellipsoids, interval hull, verification of positive definiteness, quadratic constraints,rounding error control, preprocessing, optimization, verified computing,computer assisted proofs

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: 2008, University of Vienna

Download: [PDF]

Entry Submitted: 02/28/2008
Entry Accepted: 02/28/2008
Entry Last Modified: 03/19/2008

Modify/Update this entry