／var／logmarcus chiu

LU Decomposition／Factorization (Partial／Full Pivoting - LUP)

Created on

given matrix 𝐴 and vector 𝑦, find unknown vector 𝑥

Indent

𝐴𝑥 = 𝑦

One way to do this is to compute 𝐴⁻¹

However, 𝐴⁻¹ may suffer rounding errors while 𝐿𝑈 Decomposition does not

Indent

𝐴 = 𝐿𝑈
𝐴𝑥 = 𝐿𝑈𝑦

where:

  • 𝐿 is lower triangle matrix
  • 𝑈 is upper triangle matrix

LU Decomposition - Example

LU Decomposition - Other Types

LU Type

Description

Description

LU Decomposition With Partial Pivoting (LUP)

LU factorization with row permutations only

Indent

𝑃𝐴 = 𝐿𝑈

where:

  • 𝐿 is lower triangle matrix
  • 𝑈 is upper triangle matrix
  • 𝑃 is permutation matrix that reorders the rows of matrix 𝐴

LU Decomposition With Full Pivoting

LU factorization with both row & col permutations

Indent

𝑃𝐴𝑄 = 𝐿𝑈

where:

  • 𝐿 is lower triangle matrix
  • 𝑈 is upper triangle matrix
  • 𝑃 is permutation matrix that reorders the rows of matrix 𝐴
  • 𝑄 is permutation matrix that reorders the columns of matrix 𝐴

LDU Decomposition