Rank-one update of QR factorization

Post here if you have a question about LAPACK or ScaLAPACK algorithm or data format

Rank-one update of QR factorization

Postby gillesmy » Fri Jan 28, 2011 3:56 am

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 !
gillesmy
 
Posts: 2
Joined: Fri Jan 28, 2011 3:41 am

Re: Rank-one update of QR factorization

Postby Julien Langou » Fri Jan 28, 2011 11:40 am

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.
Julien Langou
 
Posts: 727
Joined: Thu Dec 09, 2004 12:32 pm
Location: Denver, CO, USA

Re: Rank-one update of QR factorization

Postby gillesmy » Sat Jan 29, 2011 3:28 am

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 ;-).
gillesmy
 
Posts: 2
Joined: Fri Jan 28, 2011 3:41 am

Re: Rank-one update of QR factorization

Postby sven » Sun Jan 30, 2011 11:35 am

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.
sven
 
Posts: 144
Joined: Wed Dec 22, 2004 4:28 am


Return to Algorithm / Data

Who is online

Users browsing this forum: No registered users and 1 guest