PLU-factorization

PLU is LU with pivoting (although ``P'' stands for permutation).

• Permutation matrices $P_{n \times n}$:
  • Each row or each column has exactly one 1 and for the rest.
  • Example: $\left[ \begin{array} {ccc} 0 & 1 & 0 \ 1 & 0 & 0 \ 0 & 0 & 1 \end{array} \right]$
  • Property: P^T P = P P^T = I
• What if a₁₁ = 0 happens in LU-factorization?
  • Want to find a permutation matrix P, such that A = PLU.
• Algorithm

  1.

  If n = 1, return P = 1, L = 1, U = a₁₁.

  2.

  Find a non-zero element a_i1 in the first row of A. (If not, then the system is not solvable.)

  3.

  Define a permutation matrix $Q_{n \times n}$ such that

  • q_1i = q_i1 = 1,
  • q_jj = 1 for $j \neq 1, j \neq i$,
  • All the other elements of Q are 0.

  4.

  Let B = QA. Notice that $b_{11} = a_{i1} \neq 0$.

  5.

  Write B as

  6.

  Define $B_1 = B' - c \cdot r^T / b_{11}$. Recursively compute B₁ = P₁ L₁ U₁

  7.

  Return

• Correctness of the algorithm? By induction.
• Operation count? Same as LU.