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

-viral

On 10-Jun-2012, at 9:31 PM, Douglas Bates wrote:

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

>

>

> On Sun, Jun 10, 2012 at 7:55 AM, Viral Shah <

vi...@mayin.org> wrote:

> 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

>

>

> On Sunday, June 10, 2012 12:51:28 PM UTC+5:30, Jack Poulson wrote:

> 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

>

> On Saturday, June 9, 2012, Viral Shah <

vi...@mayin.org> wrote:

> > 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

> >

> >

> >

> >

>