spam (version 0.20-3)

complexity: Complexity for Sparse Matrices

Description

A few results of computational complexities for selected sparse algoritms in spam

Details

A Cholesky factorization of an n-matrix requires n^3/3 flops. In case of banded matrices (bandwidth p, p<

George and Liu (1981) proves that any reordering would require at least O(n^3/2) flops for the factorization and produce at least O(n log(n)) fill-ins for square lattices with a local neighbor hood. They also show that algorithms based on nested dissection are optimal in the order of magnitude sense.

More to follow.

References

George, A. and Liu, J. (1981) Computer Solution of Large Sparse Positive Definite Systems, Prentice Hall.

See Also

det, solve, forwardsolve, backsolve and ordering.