Incomplete LU factorization

Builds on Sparse matrix Triangular matrix LU decomposition M-matrix Incomplete Cholesky factorization

Definition

Let $A$ be a real $n \times n$ sparse matrix. Let $P \subseteq \set{1, \dots, n}^2$ be a set of positions that contains every diagonal position $(i, i)$ . An incomplete LU factorization of $A$ with pattern $P$ is a pair $(L, U)$ such that:

$L$ is unit lower triangular and $U$ is upper triangular;
$l_{ij} = 0$ and $u_{ij} = 0$ for every position $(i, j) \notin P$ ;
$(L U)_{ij} = a_{ij}$ for every $(i, j) \in P$ .

When $P$ is the set of positions with $a_{ij} \ne 0$ together with the diagonal, it is called ILU(0).

Remarks

If $P$ is the set of all positions and $A$ has an LU decomposition with unit lower triangular $L$ , the two factorizations coincide. Example: if $A$ is tridiagonal and has an LU decomposition, its exact factors are bidiagonal. They vanish outside the pattern of $A$ , so they form the ILU(0) factorization. Non-example: let $A$ be the $2 \times 2$ identity, let $P$ be all positions, and let $L$ have rows $(1, 0)$ and $(1, 1)$ , with $U = I$ . Clauses 1 and 2 hold, but clause 3 fails, since $(L U)_{21} = 1 \ne 0 = a_{21}$ . The factors are computed by Gaussian elimination in which each update outside $P$ is discarded. For a general matrix a zero pivot can occur, and then the factorization does not exist. It exists for every pattern when $A$ is an M-matrix. For symmetric positive definite $A$ the symmetric analogue is the incomplete Cholesky factorization. Variants use levels of fill, written ILU( $k$ ), or thresholds, written ILUT.

Reading path

To understand this page from the ground up, read these 6 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Incomplete Cholesky factorization concept
LU decomposition concept
M-matrix concept
Sparse matrix concept
Triangular matrix concept
Incomplete LU factorization definition

Tag	`EMYPFVX322`
URI	`m2://EMYPFVX322`
Kind	definition
Writing	W0 stub
MSC	65F08, 65F50, 65F10
Defines	Incomplete LU factorization
Uses	Sparse matrix, Triangular matrix, LU decomposition, M-matrix, Incomplete Cholesky factorization

Incomplete LU factorization

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here