A few results of computational complexities for selected
sparse algoritms in spam
A Cholesky factorization of an n-matrix requires n^3/3 flops. In case of banded matrices (bandwidth p, p<<n) a factorization requires about 2np^2 flops. Forward- and backsolves for banded matrices require essentially 2np flops.
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.
George, A. and Liu, J. (1981) Computer Solution of Large Sparse Positive Definite Systems, Prentice Hall.
det, solve,
forwardsolve, backsolve and ordering.