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
