4
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$
    – GoHokies
    Commented Dec 16, 2015 at 15:26
  • $\begingroup$ 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++. $\endgroup$
    – horchler
    Commented Dec 16, 2015 at 21:46
  • $\begingroup$ @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? $\endgroup$
    – Federico Poloni
    Commented Dec 16, 2015 at 21:58
  • 1
    $\begingroup$ 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). $\endgroup$
    – horchler
    Commented Dec 16, 2015 at 22:51
  • $\begingroup$ 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) $\endgroup$
    – N74
    Commented Dec 17, 2015 at 9:32

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.