umfpack
Multifrontal sparse LU factorization for unsymmetric matrices
Multifrontal sparse LU factorization for unsymmetric matrices
UMFPACK computes a sparse LU factorization of a general (unsymmetric) square matrix A: PRAQ = LU where P and Q are permutation matrices, R is diagonal scaling, L is unit lower triangular, and U is upper triangular.
Key features:
- Multifrontal algorithm with BLAS-3 dense kernels
- Automatic strategy selection (symmetric vs unsymmetric)
- Fill-reducing orderings: AMD (symmetric), COLAMD (unsymmetric)
- Real and complex matrices (double precision)
- Row scaling for numerical stability
Typical workflow:
- umfpack_di_symbolic: Symbolic analysis (ordering, memory estimates)
- umfpack_di_numeric: Numerical LU factorization
- umfpack_di_solve: Solve Ax = b, A'x = b, etc.
- umfpack_di_free_symbolic, umfpack_di_free_numeric: Free memory
Algorithm
Multifrontal LU with threshold partial pivoting:
- Symbolic analysis: compute column elimination tree and frontal matrices
- COLAMD ordering for unsymmetric, AMD for symmetric patterns
- Identify supernodes: columns with identical nonzero patterns
- Numerical factorization (multifrontal):
- Process columns in elimination tree postorder
- For each frontal matrix: dense partial LU with threshold pivoting
- Assemble child contributions (extend-add operation)
- Extract L and U columns, pass remainder to parent front
- Solve phase: forward/back substitution through frontal matrices
Factorization: P·R·A·Q = L·U where:
- P, Q are permutation matrices (row/column reordering)
- R is diagonal scaling matrix (row equilibration)
- L is unit lower triangular, U is upper triangular Threshold pivoting: select pivot if |a_kk| ≥ τ·max_i|a_ik| (τ ≈ 0.1)
Complexity: Time: $O(nnz(L+U)$·f̄) where f̄ is average front size Typically $O(n^{1}.5)$ to $O(n^{2})$ for 2D problems, $O(n^{2})$ for 3D Space: $O(nnz(L+U)$ + front_stack) where front_stack depends on ordering
References:
- Davis (2004). "Algorithm 832: UMFPACK V4.3 - An unsymmetric-pattern multifrontal method". ACM Trans. Math. Software 30(2):196-199.
- Davis (2004). "A column pre-ordering strategy for the unsymmetric-pattern multifrontal method". ACM Trans. Math. Software 30(2):165-195.
- Duff, Reid (1983). "The Multifrontal Solution of Indefinite Sparse Symmetric Linear Equations". ACM Trans. Math. Software 9(3):302-325.
See Also
- klu.h for circuit simulation matrices (often faster for this case)
- cholmod.h for symmetric positive definite matrices
- umfpack_di_numeric() for numerical factorization
- umfpack_di_free_symbolic() to free returned object
- umfpack_di_symbolic() for symbolic analysis
- umfpack_di_solve() to solve using the factorization
- umfpack_di_numeric() for computing the factorization
- UMFPACK_CONTROL_* defines for parameter indices
- cs_compress in CSparse for similar functionality
Source
Header file: `UMFPACK/Include/umfpack.h`