6
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Is your matrix 3x3 or a general one? $\endgroup$
    – Tolga Birdal
    Commented Aug 4, 2014 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
    Commented Aug 5, 2014 at 18:50

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 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
    Commented Aug 22, 2014 at 0:08
  • $\begingroup$ Would using Given's rotations solve your memory access problems? $\endgroup$
    – user2457602
    Commented Aug 25, 2014 at 23:17

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.