Efficient RQ decomposition

I have an upper trapezoidal matrix stored in column major format. That is, my matrix looks like this: I'd like to RQ decompose it, and store Q in the rectangular part of my upper trapezoidal matrix. For QR decomposition, I can store Q in the lower portion of the matrix, as a sequence of column vectors ($v$) which form Householder transformations ($I - 2 v v^T$).

However, the same approach taken here would have me store the vectors for the householder transformations as rows in the rectangular portion of the upper trapezoidal matrix. However, because the matrix isn't stored row major, that's not going to be cache efficient.

Is there a way to store Q from the RQ decomposition in the rectangular portion of the upper trapezoidal matrix in a way that lets me use it in a column major way? If not using Householder Transformations, maybe a different method?

Right now my thought is to require the column vectors in the rectangular portion to be padded with extra space so that the rectangular portion is square, and then I store the householder vectors as columns. But that can potentially be a lot of extra memory. Is there a better way?

• Is your matrix 3x3 or a general one? Aug 4 '14 at 22:30
• A general one. My thinking at the moment is to transpose the entire matrix and reverse the order of the columns before trying to decompose it. Worst case that doubles the memory, but I can't think of anything better, and decomposing it in that form is basically like a QR decomposition, which is efficient. Aug 5 '14 at 18:50

You can try an LQ factorization, similar to what you have in mind. It is mathematically equivalent to QR on $A^T$ http://www.netlib.org/lapack/lug/node41.html.