SparseM (version 0.73)

SparseM.solve: Linear Equation Solving for Sparse Matrices

Description

chol performs a Cholesky decomposition of a symmetric positive definite sparse matrix x of class matrix.csr. backsolve performs a triangular back-fitting to compute the solutions of a system of linear equations in one step. backsolve and forwardsolve can also split the functionality of backsolve into two steps. solve combines chol and backsolve and will compute the inverse of a matrix if the right-hand-side is missing.

Usage

chol(x, pivot = FALSE, ...)
backsolve(r, x, k = NULL, upper.tri = NULL, transpose = NULL, twice = TRUE, ...)
forwardsolve(l, x, k = ncol(l), upper.tri = FALSE, transpose = FALSE)
solve(a, b, ...)

Arguments

a

symmetric positive definite matrix of class matrix.csr.

r

object of class matrix.csr.chol returned by the function chol.

l

object of class matrix.csr.chol returned by the function chol.

x,b

vector(regular matrix) of right-hand-side(s) of a system of linear equations.

k

inherited from the generic; not used here.

pivot

inherited from the generic; not used here.

upper.tri

inherited from the generic; not used here.

transpose

inherited from the generic; not used here.

twice

Logical flag: If true backsolve solves twice, see below.

...

further arguments passed to or from other methods.

Details

chol performs a Cholesky decomposition of a symmetric positive definite sparse matrix a of class matrix.csr using the block sparse Cholesky algorithm of Ng and Peyton (1993). The structure of the resulting matrix.csr.chol object is relatively complicated. If necessary it can be coerced back to a matrix.csr object as usual with as.matrix.csr. backsolve does triangular back-fitting to compute the solutions of a system of linear equations. For systems of linear equations that only vary on the right-hand-side, the result from chol can be reused. Contrary to the behavior of backsolve in base R, the default behavior of backsolve(C,b) when C is a matrix.csr.chol object is to produce a solution to the system $Ax = b$ where C <- chol(A), see the example section. When the flag twice is FALSE then backsolve solves the system $Cx = b$, up to a permutation -- see the comments below. The command solve combines chol and backsolve, and will compute the inverse of a matrix if the right-hand-side is missing. The determinant of the Cholesky factor is returned providing a means to efficiently compute the determinant of sparse positive definite symmetric matrices.

References

Koenker, R and Ng, P. (2002). SparseM: A Sparse Matrix Package for R, http://www.econ.uiuc.edu/~roger/research

Ng, E. G. and B. W. Peyton (1993), "Block sparse Cholesky algorithms on advanced uniprocessor computers", SIAM J. Sci. Comput., 14, pp. 1034-1056.

See Also

slm for sparse version of lm

Examples

data(lsq)
class(lsq) # -> [1] "matrix.csc.hb"
model.matrix(lsq)->design.o
class(design.o) # -> "matrix.csr"
dim(design.o) # -> [1] 1850  712
y <- model.response(lsq) # extract the rhs
length(y) # [1] 1850
t(design.o)%*%design.o -> XpX
t(design.o)%*%y -> Xpy
chol(XpX)->chol.o
backsolve(chol.o,Xpy)-> b1 # least squares solutions in two steps
solve(XpX,Xpy) -> b2 # least squares estimates in one step
backsolve(chol.o, forwardsolve(chol.o, Xpy), twice = FALSE) -> b3 # in three steps