3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Remember that permutation matrices are orthogonal... $\endgroup$ – J. M. isn't a mathematician Apr 17 '11 at 15:42
  • $\begingroup$ And since Q is the column permutation, and B is a single column, it can effectively be thrown away? $\endgroup$ – Andrew Bolster Apr 17 '11 at 15:45
  • $\begingroup$ 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. $\endgroup$ – J. M. isn't a mathematician Apr 17 '11 at 16:00
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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