Cholesky Factor Updating Techniques for Rank 2 Matrix Modifications
Richard H. Bartels, Linda Kaufman · SIAM Journal on Matrix Analysis and Applications · 1989
Gill, Golub, Murray, and Saunders have described five methods by which the Cholesky factors of a positive definite matrix may be updated when the matrix is subjected to a symmetric rank 1 modification. For a negative rank 1 update, a modification of one of their methods was given by Lawson and Hanson and analyzed by Bojanczyk, Brent, van Dooren, and de Hoog. In many minimization algorithms, symmetric rank 2 modifications are found. This paper shows how each of the rank 1 methods gives rise to a single-application rank 2 method. For some of the methods, this involves a new Householder transformation technique designed to eliminate elements of two vectors at once using a rank 1 correction of the identity matrix. The authors’ experiments on scalar, vector, and shared-memory multiple-instructions multiple-data machines show that it is more economical to perform rank 2 updates rather than two rank 1 updates. In their comparison, the authors do not consider pipelining two applications of the rank 1 algorithms, which in certain instances is possible.