[petsc-users] complexity of solvers

[Alexander Grayver]

Hello,

Probably my question might seem stupid, but I don't know better place to 
ask.
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). They have sparse matrix with 13 nnz per row.
What I've thought so far is that the complexity of the LU decomposition 
depends on the sparsity of the matrix and in worst case
of dense matrix can be estimated as O(n^3). I have not seen any 
estimates of the LU decomposition complexity for sparse matrices.
Is that possible at all?

I also always assume the same situation for iterative solvers with the 
worst case of O(n^2) when the matrix is dense.

Regards,
Alexander