0
$\begingroup$

Hi, I'm attempting to implement a QR factorization with column pivoting so that the returned R matrix has decreasing diagonal elements (that is, $r_{i,i} \leq r_{i-1,i-1}$ for all $i\geq 2$). Mathematically, it would involve finding the matrix $P$ so that $AP=QR$, or $A=QRP^T$. I'm using Gram-Schmidt to compute QR.

One source I found was this: http://www.mathworks.de/matlabcentral/newsreader/view_thread/250632

Quote from the answer: "During the iteration #k, it is easy to show that if we pick among the set of remaining vectors (i.e., not yet included in the span) the vector that has the largest orthogonal component to the current subspace (generated by k first vectors), then the diagonal of R must decrease."

Sounds simple enough, but HOW do I determine which vector of the remaining ones that have the largest orthogonal component to the subspace that's already been found?

Thanks a lot in advance for any help on this matter!

Best regards Hallgeir

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Is there any reason why you prefer Gram-Schmidt (you're using the modified version I hope, classical Gram-schmidt has piss-poor numerical stability) over using Householder reflections? $\endgroup$
    – J. M. isn't a mathematician
    Commented Oct 25, 2010 at 4:28
  • 2
    $\begingroup$ Seconded. Also, check if you can link to the relevant LAPACK subroutine (netlib.org/lapack/lug/node42.html) instead of coding it from scratch. $\endgroup$
    – Federico Poloni
    Commented Oct 25, 2010 at 9:19
  • $\begingroup$ Hi, these are reasonable points of course, but the whole point was to learn how to actually implement it. And I do indeed use the modified version. :) I learn better by doing, and as such I find that implementing the algorithm is a useful way of achieving that. $\endgroup$
    – Hallgeir
    Commented Oct 26, 2010 at 5:31

1 Answer 1

Reset to default
0
$\begingroup$

At each step $k$, choose the column of the "reduced" working matrix $A(k:n,k:n)$ with largest Euclidean norm and bring it in front with a permutation. Notice that $r_{11}$ is the Euclidean norm of the first column...

Improve this answer
$\endgroup$
1
  • $\begingroup$ A little late reply from me (seems the email notification came quite late), but thank you very much! :) Seems to work perfectly! $\endgroup$
    – Hallgeir
    Commented Oct 26, 2010 at 5:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .