Triangular Factorization Task

A Triangular Factorization Task is a matrix factorization task that factors a matrix as the product of a lower triangular matrix and an upper triangular matrix.

• AKA: LU Decomposition.
• Context:
  • It can be solved by a LU Decomposition System (that implements an LU decomposition algorithm).
  • …
• Counter-Example(s):
  • Gaussian Elimination.
  • Square Root Method.
  • SVD Factorization.
• See: Linear Programming Algorithm, Linear Algebra Library, Permutation Matrix, Gaussian Elimination, System of Linear Equations, Determinant.

---

---

References

2014

• (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/LU_decomposition Retrieved:2014-9-27.
  • In numerical analysis, LU decomposition (where 'LU' stands for 'Lower Upper', and also called LU factorization) factors a matrix as the product of a lower triangular matrix and an upper triangular matrix. The product sometimes includes a permutation matrix as well. The LU decomposition can be viewed as the matrix form of Gaussian elimination. Computers usually solve square systems of linear equations using the LU decomposition, and it is also a key step when inverting a matrix, or computing the determinant of a matrix. The LU decomposition was introduced by mathematician Alan Turing.

2013

• http://people.sc.fsu.edu/~jpeterson/GaussElim.pdf
  • QUOTE: This chapter deals with the factorization of arbitrary matrices into products of triangular matrices. Since the solution of a linear n × n system can be easily obtained once the matrix is factored into the product of tria ngular matrices, we will concentrate on the factorization of square matrices. S pecifically, we will show that an arbitrary n × n matrix A has the factorization P A = LU where P is an n × n permutation matrix, L is an n × n unit lower triangular matrix, and U is an n × n upper triangular matrix. In connection with this factoriza tion we will discuss pivoting, i.e., row interchange, strategies. We will also explore circums tances for which A may be factored in the forms A = LU or A = LL T. Our results for a square system will be given for a matrix with real elements but can ea sily be generalized for complex matrices. The corresponding results for a general m × n matrix will be accumulated in Section 1.4. In the general case an arbitrary m × n matrix A has the factorization P A = LU where P is an m × m permutation matrix, L is an m×m unit lower triangular matrix, and U is an m × n matrix having row echelon structure.

---