Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a matrix A and vector B, solve

$Ax=B$

Using LU Decomposition with full Pivoting;

$PAQ=LU$

where P and Q are row and column permutation vectors (correct me if I'm wrong)

What I don't understand is what to do with the permutation matrices to finish the solution. I know in partial pivoting, its simple

$Lz=PB$

$Ux=z$

But what do I do with Q?

PS If anyone is a C head, you're help would be appreciated in the implementation

share|improve this question
    
Remember that permutation matrices are orthogonal... –  J. M. Apr 17 '11 at 15:42
    
And since Q is the column permutation, and B is a single column, it can effectively be thrown away? –  Andrew Bolster Apr 17 '11 at 15:45
    
No; remember that in partial pivoting, the row permutation is "undone" by first permuting the right hand side. Undoing a column permutation corresponds to permuting the result after multiplying the RHS vector with the inverses of the triangular matrices. –  J. M. Apr 17 '11 at 16:00

1 Answer 1

up vote 2 down vote accepted

Recall that permutation matrices have the property that $P^{-1} = P^T$, so we can re-arrange the factorization to write $A$ in the form $A = P^TLUQ^T$. After that, it is straightforward to solve:

$\begin{align} Lz &= Pb \\ Uy &= z \\ x &= Qy \\ \end{align}$

Note that $Q$ can't be just "ignored" because it is a "column permutation". It is a column permutation by virtue of how it is used (right-multiplication), not by virtue of the structure of the matrix, and it does have an effect when applied to a column vector with left-multiplication.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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