QR and permutation matrix

10262015, 03:04 PM
(This post was last modified: 10262015 03:18 PM by Han.)
Post: #1




QR and permutation matrix
The QR() command returns the QR factorization of a matrix and includes a permutation matrix. I cannot seem to find an example of a matrix for which the QR factorization returns a permutation matrix that is nonidentity. Is anyone able to find such a case? From the looks of it, the QR() command does not appear to do any pivoting (the diagonals of R are not in nonincreasing order). For example:
M2:=[[1,2],[3,5],[1,7],[2,1]] QR(M2); returns Code: [ So is there no pivoting? And if not, then it appears the P matrix is superfluous. Graph 3D  QPI  SolveSys 

10262015, 05:04 PM
Post: #2




RE: QR and permutation matrix
There is indeed no need to have a permutation matrix, you can check that in giac in vecteur.cc in qr_ortho, the idn matrix is here for compatibility. There is pivoting in the sense that to reduce a given column the line with highest absolute value is choosen. Can you explain what is the reason behind having a permutation matrix?


10262015, 05:16 PM
Post: #3




RE: QR and permutation matrix
I actually do not need the permutation matrix. I was asking because I wanted to use the QR factorization for solving a system and if the permutation matrix is nonidentity then it would have required a few extra lines of code.
Is this the same case for LU factorizations (I.e safe to ignore the permutation matrix)? Graph 3D  QPI  SolveSys 

10262015, 07:24 PM
Post: #4




RE: QR and permutation matrix
(10262015 05:04 PM)parisse Wrote: There is indeed no need to have a permutation matrix, you can check that in giac in vecteur.cc in qr_ortho, the idn matrix is here for compatibility. There is pivoting in the sense that to reduce a given column the line with highest absolute value is choosen. I am not sure what you mean by this. If \[ A = \begin{bmatrix} a_{1} & a_{2} & \dotsm & a_{n} \\ \end{bmatrix} \] then the first step is to swap columns (if necessary) so that the column column \( a_1 \) is replaced with the column having largest norm? And then a Householder reflection is applied? (And similarly for submatrices) Is that what you meant by pivoting? Quote:Can you explain what is the reason behind having a permutation matrix? QR factorization with pivoting gives R with diagonal terms in nondecreasing order. This is useful for factoring rankdeficient matrices. Graph 3D  QPI  SolveSys 

10272015, 06:48 AM
Post: #5




RE: QR and permutation matrix
I see, it is probably like total pivoting vs partial pivoting. Partial pivoting is used in LU and QR, but in the LU case this adds a generically non trivial permutation matrix (PA=LU, P^1*L would not be triangular) while in the QR case the permutation is absorbed by Q.


« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)