<pre>

Path: news.mathworks.com!not-for-mail
From: &lt;HIDDEN&gt;
Newsgroups: comp.soft-sys.matlab
Subject: in [Q, R, E] = qr(A), how E is determined ?
Date: Tue, 5 May 2009 17:51:10 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 24
Message-ID: &lt;gtpuae$4b7$1@fred.mathworks.com&gt;
Reply-To: &lt;HIDDEN&gt;
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset=&quot;ISO-8859-1&quot;
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1241545870 4455 172.30.248.35 (5 May 2009 17:51:10 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Tue, 5 May 2009 17:51:10 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1196827
Xref: news.mathworks.com comp.soft-sys.matlab:537615


Hi,

   I'm trying to implement qr factorization, as it works in matlab, in another programming language. I've found an algorithm to do the qr factorization (but without ordering abs(diag(R)). That's the part I'm missing. On qr's help page, it is said:

&quot;[Q,R,E] = qr(A) for full matrix A, produces a permutation matrix E, an upper triangular matrix R with decreasing diagonal elements, and a unitary matrix Q so that A*E = Q*R. The column permutation E is chosen so that abs(diag(R)) is decreasing.&quot;

I've looked also at the fortran implementation of qr in netlib at this address :

http://www.netlib.org/lapack/double/dgeqp3.f

there I can get the permutation (=pivot) matrix is received as an input parameter:

(...)
*  JPVT    (input/output) INTEGER array, dimension (N)
*          On entry, if JPVT(J).ne.0, the J-th column of A is permuted
*          to the front of A*P (a leading column); if JPVT(J)=0,
*          the J-th column of A is a free column.
*          On exit, if JPVT(J)=K, then the J-th column of A*P was the
*          the K-th column of A.
(...)

it seems that the pivot strategy is determined outside of the fortran routine, somewhere in matlab internals. Now I'm able to find the correct permutation matrix by searching it with a brute-force approach, i.e. simply exploring all the permutations until I find one good, that makes abs(diag(R)) decreasing; but that could bring the elaboration time to exponential or even factorial dimensions. I'm guessing if, given a not ordered Q-R factorization, is there some transformation or formula (like the gauss algorithm for finding linear independent columns) that &quot;understands&quot; rapidly how the permutation matrix E must be. So, how is E determined in the qr routine ?

many thanks, Marco
<pre>