qrupdate/cholupdate

[Viral Shah]

Matlab has cholupdate and qrupdate functions. How does it implement these? Can they be done with LAPACK?
http://www.mathworks.in/help/techdoc/ref/cholupdate.html
http://www.mathworks.in/help/techdoc/ref/qrupdate.html

I just noticed the qrupdate library, which provides routines for updating the factorizations of rank-1 updates to the original matrix? It supports updating of QR, Cholesky, and LU factorizations. Does anyone have any experience with it?

http://sourceforge.net/projects/qrupdate/


-viral

[Jack Poulson]

This question was answered in the following discussion on the LAPACK forum:

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

The answer is that it was in LINPACK, but is not (yet) in LAPACK. I don't know what MATLAB does, but Octave uses a package called QRUPDATE:

http://www.gnu.org/software/octave/doc/interpreter/Compiling-Octave-with-64_002dbit-Indexing.html

Jack

[Viral Shah]

Thanks. I had looked in LAPACK but did not find the update routines, and was wondering if I had missed something. I guess qrupdate is the way to go for now, if it is already in use by octave. It may even be a fun exercise to try write the update routines in julia.

-viral

[Alan Edelman]

most of these updates, i recall, are fairly easy formulas

[Douglas Bates]

On Sunday, June 10, 2012 8:48:02 AM UTC-5, Alan Edelman wrote:

most of these updates, i recall, are fairly easy formulas

The Cholesky update functions in Linpack were based on Given's rotations.  A rank-1 update of the Cholesky decomposition (given A = R'R, determine S in A + xx' = S'S) is straightforward and stable (imagine you have formed vcat(R, x) and use Givens rotations on the k'th row of R and the 'x' row to zero out the k'th element of x, k = 1:n).  Successive rank-1 downdates, which in essence reverse the preceding process) can become numerically unstable.  There was also a clever way in Linpack of forming the Cholesky decomposition of the same matrix after a cyclic shift of some or all of the columns.

One thing that could easily have been incorporated from Linpack into Lapack but wasn't, and I'm not sure why, is a pivoted Cholesky decomposition, similar to the pivoted QR decomposition.  It may again have been a question of numerical stability.

These types of operations would only be a big win for large, dense positive-definite systems.  In my experience large positive-definite systems are often sparse.  The CHOLMOD code provides for both the Cholesky decomposition and for updates (MODifications) of sparse positive-definite systems.

[Viral Shah]

I did notice that CHOLMOD does provide for updates - why do you say that they are only a big win for dense systems?

-viral