# How does a Sparse Direct Solver know about dimensionality of a problem being solved?

It is claimed that the time and memory complexities of sparse direct solver are $O(N^2)$ and $O(N^{4/3})$ for 3D problems and $O(N^{1.5})$ and $O(N \log N)$ for 2D, respectively.

But how does a general-purpose direct solver know about dimensionality? If I call a direct solver with an arbitrary matrix, what is the complexity then? Is it then hidden in constants inside asymptotic estimations?

• From my (limited) experience, the solver doesn't "know" about the dimensionality but instead "knows" about the number of non-zeros per row/column. The complexities you state are (IMO) thumb rules rather than a norm. A 2D problem of Maxwell equations will behave differently as compared to one of Heat Transfer. However, 2D problems will have lesser non-zero elements than 3D problems thus accelerating the process. For instance, in Heat Transfer, a 1D problem matrix is tridiagonal while a 2D problem has 5 nonzero elements per row. – Inquest Mar 31 '12 at 13:47
• Well, talking about FD for 2D, once can use higher order schemes in 2D resulting in more non-zero per row. In FE high order elements can be used and so on. – Alexander Mar 31 '12 at 13:50
• True. But one can use higher order schemes in higher dimensions as well. As I said, stating that 2D problems are $O(N\ln N)$ seems to be more of a thumbrule. – Inquest Mar 31 '12 at 14:31
• The point is that number of nonzeros per row is not an indication of dimensionality. You're right, but I'm wondering why these estimates where chosen as the reference ones. – Alexander Mar 31 '12 at 14:55
• @Nunoxic: $O(N\log N)$ is the typical complexity of iterative solvers, but the question was about direct solvers, that would compute the exact solution in $O(complexity)$ exact real operations. – Arnold Neumaier Mar 31 '12 at 16:24

However, the sparsity patttern reveals the dimension indirectly. In particular, the complexity estimates you report are based on the assumption that you have a sufficiently fine discretization of a 2D or 3D problem, and holds only asymptotically as the refinement goes uniformly to zero. (A 3D model of a long, thin bar is most likely $O(N)$ though in three dimensions, as two of the three dimensionswill hardly be refined in practice.)