What is the big-O complexity of solving the sparse Laplace equation in the plane?

Question

In MATLAB, you can get a 2d Laplacian via A = delsq(numgrid('S',N)); yielding a matrix $A$ that is $n \times n$ with $n = O(N^2)$, for a square domain discretized with an $N \times N$ grid.

Reviewing the literature, it is reiterated again and again that solving $Ax=b$ with nested dissection ordering takes $O(n\log n)$ space but $O(n^{1.5})$ FLOPS. Nevertheless, when one solves $Ax=b$ with MATLAB's backslash, one observes very robust $O(n)$ scaling, or maybe $O(n^{1.1})$:

MATLAB does not use nested dissection, it uses AMD, a variant of the minimum vertex order algorithm.

I'm reading all the literature that I can find on minimum vertex order algorithms. Every paper or book that I read, this algorithm is tested on some zoo of sparse matrices, and performance is measured experimentally, but I have not seen any big-O estimates for the 2d Laplacian.

Is there a big-O estimate for the 2d Laplacian? Can one really assert that MATLAB's sparse solvers work in $O(n)$ time on the 2d Laplacian? Also, what's the scaling for 3d Laplacians? I'm hoping this is somewhere in the classical literature, because if it isn't, it's probably because it's hard to answer.

Answer 1

I'm not sure if this is the final answer, but this paper claims that $O(n^{1.5})$ FLOPS with $O(n\log n)$ storage, is best possible across all possible reorderings of the rows and columns of $A$.

This flies in the face of my numerical experiments, so either $n$ is not large enough in my experiments, and we're not yet in the "asymptotic regime", or other effects are dominating the run time. For example, it might be that main memory is slow so FLOPS don't matter because writing out the $O(n\log n)$ storage dominates over the $O(n^{1.5})$ FLOPS. I can't run larger experiments because my poor macbook runs out of memory.