8
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 3
    $\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
    Commented Mar 31, 2012 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
    Commented Mar 31, 2012 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
    Commented Mar 31, 2012 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
    Commented Mar 31, 2012 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$
    – Arnold Neumaier
    Commented Mar 31, 2012 at 16:24

2 Answers 2

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
0
1
$\begingroup$

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

The class of estimates you cite are remarkable in that they hold broadly, giving useful information about how a direct solver will behave for systems arising from discretized PDEs, regardless of the particular physics or discretization, depending only on the dimensionality of the problem.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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