Rank-one update of QR factorization

[gillesmy]

Hello,

I was wondering if Lapack implements rank-one updates of the thin QR factorization, that is, an update

Q'R' := QR + v*u^T, with Q -- m x n, R -- n x n, v -- m x 1 and v -- n x 1.

I am interested in the setting m >> n.

An algorithm is proposed in the 1976 paper

J.W Daniel, W.B. Gragg, L. Kaufman, G.W. Stewart
Reorthogonalization and Stable Algorithms for Updating the Gram-Schmidt QR Factorization

I have already found a topic on this forum about adding/deleting columns/rows to the QR factorization, but nothing about rank one updates.

If lapack does not implement such an algorithm (or at least its basic building blocks), does someone known if there is an efficient implementation available ?

Thank you in advance !

[Julien Langou]

hello,

• Matlab has the functionality has [q1,r1] = qrupdate(q,r,u,v)
• The only Fortran implementation I am aware of (no need to have two when it's well done!) is available through the function DRNK1. The interface is:
  

  Code: Select all

   DRNK1(Q,LDQ,M,N,R,LDR,U,V,WK,INFO)

  
  The source code is available from the ACM TOMS paper: L. Reichel and W. B. Gragg. Algorithm 686: FORTRAN subroutines for updating the QR decomposition. ACM Trans. Math. Soft., 16:369–377, 1990.
• There is no such functionality in LINPACK, nor in LAPACK. I think there is a related functionality in the NAG library but I am not sure.
• Why do you need this? We can add it in our wish list of functionality to have in LAPACK if this is relevant.

Julien.

[gillesmy]

Thank you julien for your prompt reply.

I am aware of Matlab qrupdate, however it only works when q and r are square matrices.

I am currently experimenting on subspace tracking algorithms for high dimensional problems. I have update rules relying on the qr factorization. The update is typically written as one or two rank one updates of the current subspace.

I have looked for the pdf/code of Reichel and Gragg on the Internet but it seems that it is not available freely. Is it ? Maybe it is the code that I am looking for.

I have also taken a look at the NAG library, but I have not seen routines for updating/downdating matrix factorizations.

To me, it would be and excellent idea to add the feature to Lapack ;-).

[sven]

If you have access to the NAG Library you might want to take a look at routine F06QPF

http://www.nag.co.uk/numeric/FL/nagdoc_fl22/xhtml/F06/f06qpf.xml

to see if that helps you. It does not update the Q matrix, but does return the information to allow you to do that yourself. (F06QXF may help with updating Q.)

Best wishes,

Sven Hammarling.