I have an upper trapezoidal matrix stored in column major format. That is, my matrix looks like this:

enter image description here

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?

  • $\begingroup$ Is your matrix 3x3 or a general one? $\endgroup$ – Tolga Birdal Aug 4 '14 at 22:30
  • 1
    $\begingroup$ 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. $\endgroup$ – Jay Lemmon 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.

  • 1
    $\begingroup$ But I'd still be storing the householders for the LQ in a row major way, wouldn't I? Which runs in to all the same issues I mentioned with the RQ decomposition. $\endgroup$ – Jay Lemmon Aug 22 '14 at 0:08
  • $\begingroup$ Would using Given's rotations solve your memory access problems? $\endgroup$ – user2457602 Aug 25 '14 at 23:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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