ParaMonte Fortran 2.0.0
Parallel Monte Carlo and Machine Learning Library
See the latest version documentation.
pm_matrixLUP Module Reference

This module contains procedures and generic interfaces relevant to the partially LU Pivoted decomposition of matrix operations and linear algebra. More...

Data Types

interface  setMatLUP
 Return the LU-Pivoted decomposition of the input square matrix mat(ndim,ndim).
More...
 

Variables

character(*, SK), parameter MODULE_NAME = "@pm_matrixLUP"
 

Detailed Description

This module contains procedures and generic interfaces relevant to the partially LU Pivoted decomposition of matrix operations and linear algebra.

In numerical analysis and linear algebra, lower–upper (LU) decomposition or factorization factors a matrix as the product of a lower triangular matrix and an upper triangular matrix.
The product sometimes also involves a permutation matrix.
LU decomposition can be viewed as the matrix form of Gaussian elimination.
Computers usually solve square systems of linear equations using 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 the Polish astronomer Tadeusz Banachiewicz in 1938.
The LU factorization is sometimes also referred to as LR decomposition, factoring into left and right triangular matrices.

Definition

Let \(A\) be a square matrix.
An LU factorization refers to the factorization of \(A\), with proper row and/or column orderings or permutations, into two factors – a lower triangular matrix \(L\) and an upper triangular matrix \(U\):

\begin{equation} A = LU ~. \end{equation}

In the lower triangular matrix all elements above the diagonal are zero.
In the upper triangular matrix all the elements below the diagonal are zero.
For example, for a \(3 \times 3\) matrix \(A\), its LU decomposition looks like this:

\begin{equation} \begin{bmatrix} a_{11}&a_{12}&a_{13} \\ a_{21}&a_{22}&a_{23} \\ a_{31}&a_{32}&a_{33} \end{bmatrix} = \begin{bmatrix} \ell_{11}&0&0\\ \ell_{21}&\ell_{22}&0\\ \ell_{31}&\ell_{32}&\ell_{33} \end{bmatrix} \begin{bmatrix} u_{11}&u_{12}&u_{13}\\ 0&u_{22}&u_{23}\\ 0&0&u_{33} \end{bmatrix} ~. \end{equation}

Without a proper ordering or permutations in the matrix, the factorization may fail to materialize.
For example, it is easy to verify (by expanding the matrix multiplication) that \(a_{11}=\ell_{11}u_{11}\).
If \(a_{11}=0\), then at least one of \(\ell_{11}\) and \(u_{11}\) has to be zero, which implies that either \(L\) or \(U\) is singular.
This is impossible if \(A\) is nonsingular (invertible).
This is a procedural problem.
It can be removed by simply reordering the rows of \(A\) so that the first element of the permuted matrix is nonzero.
The same problem in subsequent factorization steps can be removed the same way; see the basic procedure below.

LU factorization with partial pivoting

It turns out that a proper permutation in rows (or columns) is sufficient for LU factorization.
LU factorization with partial pivoting (LUP) refers often to LU factorization with row permutations only:

\begin{equation} PA = LU ~, \end{equation}

where \(L\) and \(U\) are again lower and upper triangular matrices, and \(P\) is a permutation matrix, which, when left-multiplied to \(A\), reorders the rows of \(A\).
It turns out that all square matrices can be factorized in this form, and the factorization is numerically stable in practice.
This makes LUP decomposition a useful technique in practice.

LU factorization with full pivoting

An LU factorization with full pivoting involves both row and column permutations:

\begin{equation} PAQ = LU ~, \end{equation}

where \(L\), \(U\) and \(P\) are defined as before, and \(Q\) is a permutation matrix that reorders the columns of \(A\).

Note
To solve systems of equations using the output LU factorization from the generic interfaces of this module, see pm_matrixMulTri.
See also
pm_matrixInv
pm_matrixChol
Test:
test_pm_matrixLUP


Final Remarks


If you believe this algorithm or its documentation can be improved, we appreciate your contribution and help to edit this page's documentation and source file on GitHub.
For details on the naming abbreviations, see this page.
For details on the naming conventions, see this page.
This software is distributed under the MIT license with additional terms outlined below.

  1. If you use any parts or concepts from this library to any extent, please acknowledge the usage by citing the relevant publications of the ParaMonte library.
  2. If you regenerate any parts/ideas from this library in a programming environment other than those currently supported by this ParaMonte library (i.e., other than C, C++, Fortran, MATLAB, Python, R), please also ask the end users to cite this original ParaMonte library.

This software is available to the public under a highly permissive license.
Help us justify its continued development and maintenance by acknowledging its benefit to society, distributing it, and contributing to it.

Author:
Amir Shahmoradi, Friday 1:54 AM, April 21, 2017, Institute for Computational Engineering and Sciences (ICES), The University of Texas, Austin, TX

Variable Documentation

◆ MODULE_NAME

character(*, SK), parameter pm_matrixLUP::MODULE_NAME = "@pm_matrixLUP"

Definition at line 113 of file pm_matrixLUP.F90.