# Code to update dense QR and Cholesky factorizations

I am looking for some production-ready code to update dense QR and/or Cholesky factorizations (by adding / removing rows and columns or making small-rank updates -- yes, I need all these cases).

I have done my Googleliterature research, but I have found very little:

• Matlab has this covered, but unfortunately this is for a C++ project, so it is not easy to interface with it. I'd much rather have C/C++ or Fortan, especially the "traditional" LAPACK-style code.
• LAPACK has nothing, as far as I can tell. There was something in LINPACK (LAPACK's precursor), but as far as I can tell it has not been updated in the last 30 years at least.
• There is some code by Craig Lucas for one of these subtasks (adding/deleting columns only for a QR factorization), and some code by Daniel Kressner for adding rows to a QR factorization only. Both of them are only limited to one of the subtasks that I need, and, to quote Kressner's page,

It is not tested thoroughly and should be understood as research code.

• Surprisingly, there is mature code for the same task for sparse matrices, in Tim Davis' Suitesparse. I don't suppose that the code will be efficient on a dense matrix.

• Michael Saunders' LUSOL has the corresponding code for a (sparse) LU factorization (unsymmetric case).

So it seems like there is plenty of code for doing similar and related tasks, but not exactly for this problem, which seems surprising.

Am I overlooking some obvious choice? Is there a library to do it?

• Look at algorithm 686 from the ACM TOMS Library: FORTRAN subroutines for updating the QR decomposition. There is a link to the FORTRAN 77 code on that same page. The paper can also be downloaded from here. Dec 16, 2015 at 15:26
• Do you not have access to Matlab Coder (codegen)? The output from that might not be the easiest to integrate, but I think one could write a simple LAPACK-style interface to the resultant C/C++. Dec 16, 2015 at 21:46
• @horchler I don't think our academic license covers that. Anyway, qrupdate is not Matlab code, but a built-in binary blob. Does codegen work also with those? Would I need to ship some Matlab libraries with it? And what would be the licensing status of the resulting code + libraries? Dec 16, 2015 at 21:58
• Yes, codegen works with many compiled Matlab functions. I thought that qrupdate would be supported, but sadly it appears that it isn't (I confirmed with a small test). You might find this page helpful for deployment. As far as licensing goes, see section 5 of edit([matlabroot filesep 'license_agreement.txt']) (starts at line 1177 in my version). Dec 16, 2015 at 22:51
• Anyway you can try to implement it by yourself reading paragraph 12.5.1 of this book: Golub, Gene H. and Charles Van Loan, Matrix Computations, Third Edition, Johns Hopkins University Press, Baltimore, 1996 (If you google it you can find a copy)
– N74
Dec 17, 2015 at 9:32

## 1 Answer

You can use the package qrupdate that is the one linked in Octave.

It's in Fortran... but it should be self contained. If you need to link it to a C++ project you can look at the Octave source code, file floatQR.cc.