# complexity {spam}

### 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`

.

Documentation reproduced from package spam, version 1.3-0. License: LGPL-2