<div class="gmail_quote">On Wed, Apr 20, 2011 at 17:31, Alexander Grayver <span dir="ltr"><<a href="mailto:agrayver@gfz-potsdam.de">agrayver@gfz-potsdam.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div id=":13l">I came across with paper in one of the referenced journal where authors claim that LU decomposition has complexity of<br>
O(n^1.5) and one solution using factorized matrix can be calculated in O(n*logn).</div></blockquote></div><br><div>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.</div>
<div><br></div><div><div>Alan George, Joseph Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, Englewood Cliffs, NJ, 1981.</div><div><br></div><div>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.</div>
</div><div><br></div>