[petsc-users] complexity of solvers

[Jed Brown]

On Wed, Apr 20, 2011 at 17:31, Alexander Grayver <agrayver at gfz-potsdam.de>wrote:

> I came across with paper in one of the referenced journal where authors
> claim that LU decomposition has complexity of
> O(n^1.5) and one solution using factorized matrix can be calculated in
> O(n*logn).
>

These are the bounds for 2D problems with optimal ordering. For 3D, the
bounds are O(n^2) time and O(n^{4/3}) space.

Alan George, Joseph Liu, Computer Solution of Large Sparse Positive Definite
Systems, Prentice-Hall, Englewood Cliffs, NJ, 1981.

S.C. Eisenstat, M.H. Schultz, A.H. Sherman, Applications of an element model
for Gaussian elimination, in: Sparse Matrix Computations (Proc. Symp.,
Argonne Nat. Lab., Lemont, Ill., 1975), Academic Press, New York, 1976, pp.
85–96.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20110420/7ca8839c/attachment.htm>