Sparse LU Factorizations

Description

sparseLU is the class of sparse, row- and column-pivoted LU factorizations of n \times n real matrices A, having the general form

P_{1} A P_{2} = L U

or (equivalently)

A = P_{1}' L U P_{2}'

where P_{1} and P_{2} are permutation matrices, L is a unit lower triangular matrix, and U is an upper triangular matrix.

Slots

Dim, Dimnames

inherited from virtual class MatrixFactorization.

L

an object of class dtCMatrix, the unit lower triangular L factor.

U

an object of class dtCMatrix, the upper triangular U factor.

p, q

0-based integer vectors of length Dim[1], specifying the permutations applied to the rows and columns of the factorized matrix. q of length 0 is valid and equivalent to the identity permutation, implying no column pivoting. Using R syntax, the matrix P_{1} A P_{2} is precisely A[p+1, q+1] (A[p+1, ] when q has length 0).

Extends

Class LU, directly. Class MatrixFactorization, by class LU, distance 2.

Instantiation

Objects can be generated directly by calls of the form new("sparseLU", ...), but they are more typically obtained as the value of lu(x) for x inheriting from sparseMatrix (often dgCMatrix).

Methods

determinant

signature(from = "sparseLU", logarithm = "logical"): computes the determinant of the factorized matrix A or its logarithm.

expand

signature(x = "sparseLU"): see expand-methods.

expand1

signature(x = "sparseLU"): see expand1-methods.

expand2

signature(x = "sparseLU"): see expand2-methods.

solve

signature(a = "sparseLU", b = .): see solve-methods.

References

Davis, T. A. (2006). Direct methods for sparse linear systems. Society for Industrial and Applied Mathematics. doi:10.1137/1.9780898718881

Golub, G. H., & Van Loan, C. F. (2013). Matrix computations (4th ed.). Johns Hopkins University Press. doi:10.56021/9781421407944

See Also

Class denseLU for dense LU factorizations.

Class dgCMatrix.

Generic functions lu, expand1 and expand2.

Examples

showClass("sparseLU")
set.seed(2)

A <- as(readMM(system.file("external", "pores_1.mtx", package = "Matrix")),
        "CsparseMatrix")
(n <- A@Dim[1L])

## With dimnames, to see that they are propagated :
dimnames(A) <- dn <- list(paste0("r", seq_len(n)),
                          paste0("c", seq_len(n)))

(lu.A <- lu(A))
str(e.lu.A <- expand2(lu.A), max.level = 2L)

ae1 <- function(a, b, ...) all.equal(as(a, "matrix"), as(b, "matrix"), ...)
ae2 <- function(a, b, ...) ae1(unname(a), unname(b), ...)

## A ~ P1' L U P2' in floating point
stopifnot(exprs = {
    identical(names(e.lu.A), c("P1.", "L", "U", "P2."))
    identical(e.lu.A[["P1."]],
              new("pMatrix", Dim = c(n, n), Dimnames = c(dn[1L], list(NULL)),
                  margin = 1L, perm = invertPerm(lu.A@p, 0L, 1L)))
    identical(e.lu.A[["P2."]],
              new("pMatrix", Dim = c(n, n), Dimnames = c(list(NULL), dn[2L]),
                  margin = 2L, perm = invertPerm(lu.A@q, 0L, 1L)))
    identical(e.lu.A[["L"]], lu.A@L)
    identical(e.lu.A[["U"]], lu.A@U)
    ae1(A, with(e.lu.A, P1. %*% L %*% U %*% P2.))
    ae2(A[lu.A@p + 1L, lu.A@q + 1L], with(e.lu.A, L %*% U))
})

## Factorization handled as factorized matrix
b <- rnorm(n)
stopifnot(identical(det(A), det(lu.A)),
          identical(solve(A, b), solve(lu.A, b)))