Cholesky update/downdate

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Cholesky update/downdate

Yves Deville
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.

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-devel
Reply | Threaded
Open this post in threaded view
|

Re: Cholesky update/downdate

Douglas Bates-2
On Thu, Dec 29, 2011 at 8:05 AM, Yves Deville <[hidden email]> 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.
>
> ______________________________________________
> [hidden email] mailing list
> https://stat.ethz.ch/mailman/listinfo/r-devel

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-devel
Reply | Threaded
Open this post in threaded view
|

Re: Cholesky update/downdate

Yves Deville
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.

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-devel