2
$\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

  • 0
    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.2011-04-17

1 Answers 1

5

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.