# 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. Mar 31, 2012 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. Mar 31, 2012 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. Mar 31, 2012 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. Mar 31, 2012 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. Mar 31, 2012 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.)
Implicit in "2D" and "3D" here is the notion that matrix in question arises from a 2D or 3D discretization of a PDE modelling local physics. That is, each unknown in the system couples only to other unknowns associated with physical locations in a neighborhood that shrinks to zero as the discretization is refined. There are $$O(1)$$ nonzeros per row in the matrix, and the graph corresponding to these nonzeros (as an adjacency matrix) has a structure which depends critically on the dimensionality of the underlying problem. The structure of this graph directly affects how direct solvers behave (see @arnold-neumaier 's answer).