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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – Inquest
    Mar 31 '12 at 13:47
  • $\begingroup$ 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. $\endgroup$
    – Alexander
    Mar 31 '12 at 13:50
  • $\begingroup$ 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. $\endgroup$
    – Inquest
    Mar 31 '12 at 14:31
  • $\begingroup$ 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. $\endgroup$
    – Alexander
    Mar 31 '12 at 14:55
  • $\begingroup$ @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. $\endgroup$ Mar 31 '12 at 16:24

A sparse direct solver knows the matrix, and hence its dimensions and its sparsity pattern. Of course it doesn't know the dimension of the problem dimension before discretization.

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.)

Now direct solvers are based on a tree decomposition of the sparsity graph, and its width determines the complexity. Now nested dissection arguments provide bounds on the treewidth and hence the complexity estimates you mentioned.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.