Rank 1 updates to Cholesky and QR factorizations

[ViralBShah]

Matlab has cholupdate for rank 1 updates and downdates to Cholesky factorizations. It would be nice to have something similar, but perhaps with better syntax.

LINPACK had these, but LAPACK left out the Cholesky update/downdate capabilities.

http://icl.cs.utk.edu/lapack-forum/viewtopic.php?f=2&t=2646

For the dense case, perhaps these should be implemented in julia. For the sparse case, I believe that CHOLMOD does provide these capabilities.

Updated by @andreasnoack:

• Dense Cholesky
• Sparse Cholesky
• Dense QR (actually there are three different storage schemes)

[ViralBShah]

Cc: @dmbates @andreasnoack

[mlubin]

I think qrupdate is the best package out there for this. It's GPL. Implementing this in Julia won't be a walk in the park; it's over 6000 lines of fortran (some of which is duplicated logic for different types of matrices).

[GordStephen]

Did this ever make it in? I can't find it anywhere, but I also don't know my way around linalg that well.

[ViralBShah]

This is still open.

[GordStephen]

Ok, good to know. I'm not really qualified to be adding cross-platform binary dependencies to Julia, but I did get a rudimentary version of cholupdate! (calling qrupdate) up and running for personal use on my local machine, if it's of use to anyone in the future: https://gist.github.com/GordStephen/be274faa22417d6f26a1

[ViralBShah]

Perhaps make it a package?

[GordStephen]

Good idea - I might not get to it this week but when I do I'll add in functionality for the other input types supported by qrupdate as well.

[andreasnoack]

We should be able to add pure Julia Cholesky updates without too much effort. We already have the necessary components and the algorithm is fairly simple. I can take a look. The QR row updates are probably more complicated.

[tkelman]

See @mpf's https://github.com/mpf/QRupdate.jl

[klkeys]

Any progress on sparse rank-1 Cholesky updates? I ask because I noticed that CHOLMOD is supposed to export them. See the reference publication here.

[tkelman]

If those are available in cholmod, I don't think we have wrappers for them yet.

[klkeys]

ahahaha sorry @tkelman I was updating the comment a minute too late. Are the wrappers difficult to code? I suddenly have occasion to use them, but I am not very good with C/Fortran...

[tkelman]

I get an access denied on that link. Writing ccall wrappers is conceptually not too bad, though CHOLMOD has a pretty confusing API at times. Some quality time with the API docs and/or headers along with http://docs.julialang.org/en/release-0.4/manual/calling-c-and-fortran-code/ and looking at the existing bindings in https://github.com/JuliaLang/julia/blob/master/base/sparse/cholmod.jl should get you started.

[papamarkou]

I need to use rank 1 Cholesky updates for an adaptive algorithm I am working on, to bring down complexity from O(n^3) to O(n^2), and was a bit unclear from this open issue if there is some preliminary yet operational support (either built-in or by invoking QRupdate)?