Google Groups

Re: [julia-dev] qrupdate/cholupdate


Viral Shah Jun 10, 2012 9:57 AM
Posted in group: julia-dev
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
> >
> >
> >
> >
>