Dear R-devel members, I am looking for a fast Cholesky update/downdate. The matrix A being symmetric positive definite (n, n) and factorized as A = L %*% t(L), the goal is to factor the new matrix A +- C %*% t(C) where C is (n, r). For instance, C is 1-column when adding/removing an observation in a linear regression. Of special interest is the case where A is sparse. Looking at the 'Matrix' package (help and source code), it seems that the CHOLMOD library shipped with 'Matrix' allows this, but is not (yet?) interfaced in 'Matrix', where the 'update' method for Cholesky decomposition objects seems limited to a new matrix A + m*I with a scalar (diagonal) modification. If this is true: are there plans to implement such up/downdates? Best, Yves Yves Deville, statistical consultant, France.
Cholesky update/downdate
3 messages · Douglas Bates, Yves Deville
On Thu, Dec 29, 2011 at 8:05 AM, Yves Deville <deville.yves at alpestat.com> wrote:
Dear R-devel members,
I am looking for a fast Cholesky update/downdate. The matrix A being symmetric positive definite (n, n) and factorized as A = L %*% t(L), the goal is to factor the new matrix ?A +- C %*% t(C) where C is (n, r). For instance, C is 1-column when adding/removing an observation in a linear regression. Of special interest is the case where A is sparse.
Looking at the 'Matrix' package (help and source code), it seems that the CHOLMOD library shipped with 'Matrix' allows this, but is not (yet?) interfaced in 'Matrix', where the 'update' method for Cholesky decomposition objects seems limited to a new matrix A + m*I with a scalar (diagonal) modification.
The CHOLMOD library provides sparse matrix methods, especially the Cholesky decomposition and modifications to that decomposition, which is where the name comes from. Do you expect to work with sparse matrices? I haven't seem too much code for update/downdate operations on the Cholesky decomposition for dense matrices. There were rank-1 update/downdate methods in Linpack but they didn't make it through to Lapack.
If this is true: are there plans to implement such up/downdates? Best, Yves Yves Deville, statistical consultant, France.
______________________________________________ R-devel at r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-devel
Hi Douglas, thanks for your answer. My question indeed arises from a sparse matrix context: 'A' is sparse symmetric, and 'C' must also be sparse since it would otherwise fill. It comes from a Bayes regression with a very large number of parameters; a loop over blocks will do the job in my specific case. Yet I wondered about this since similar need for "covariance updating" may arise from linear filtering or kriging. Douglas Bates wrote
The CHOLMOD library provides sparse matrix methods, especially the Cholesky decomposition and modifications to that decomposition, which is where the name comes from. Do you expect to work with sparse matrices? I haven't seem too much code for update/downdate operations on the Cholesky decomposition for dense matrices. There were rank-1 update/downdate methods in Linpack but they didn't make it through to Lapack.