Algorithms for Cholesky and QR Factorizations, and the Semidefinite Generalized Eigenvalue Problem

We consider algorithms for three problems in numerical linear algebra: computing the pivoted Cholesky factorization, solving the semidefinite generalized eigenvalue problem and updating the QR factorization. Fortran 77 codes exist in LAPACK for computing the Cholesky factorization (without pivoting) of a symmetric positive definite matrix using Level 2 and 3 BLAS. In LINPACK there is a Level 1 BLAS routine for computing the Cholesky factorization with complete pivoting of a symmetric positive semidefinite matrix. We present two new algorithms and Fortran 77 LAPACK-style codes for computing this pivoted factorization: one using Level 2 BLAS and one using Level 3 BLAS. We show that on modern machines the new codes can be many times faster than the LINPACK code. Also, with a new stopping criterion they provide more reliable rank detection and can have a smaller normwise backward error. The generalized eigenvalue problem Ax=lambda Bx in the case where A and B are real and symmetric and B is positive semidefinite is considered. We present an algorithm for solving this problem that has a potentially smaller operation count than existing methods and requires no further restrictions on A and B. The eigenvalues of the problem are classified as finite or infinite. Nonregular matrix pencils, where the eigenvalues can take any value, are also discussed and a deflation strategy is given. We include a MATLAB code for our algorithm and give some numerical experiments. We also treat the problem of updating the QR factorization, with applications to the least squares problem. Algorithms are presented that compute the factorization A-tilde = Q-tilde R-tilde where A-tilde is the matrix A=QR after it has had a number of rows or columns added or deleted. This is achieved by updating the factors Q and R, and we show this can be much faster than computing the factorization of A-tilde from scratch. We consider algorithms that exploit the Level 3 BLAS where possible and place no restriction on the dimensions of A or the number of rows and columns added or deleted. For some of our algorithms we present Fortran 77 LAPACK-style code and show the backward error of our updated factors is comparable to the error bounds of the QR factorization of A-tilde