I am looking for information on the time complexity for solving sparse system Ax=b with direct solver. This system results from a finite-element discretization of an elliptic problem. The matrix A considered is symmetric definite positive, has n equations, m non-zeros and a constant bandwidth b. How the time complexity T for solving this system depends on n, m and b (T=O(??)) ?

Do you have some references about that?

Many thanks!

  • $\begingroup$ Hi janou195 and welcome to scicomp! In general, the complexity of a sparse direct solver depends largely on the choice of method and properties of the linear system itself. Your question is too broad to give any kind of meaningful answer. If you provide more information about the particular solver/problem, we may be able to help. Otherwise, this question will likely be closed. $\endgroup$ – Paul Nov 27 '14 at 22:30
  • $\begingroup$ Hi Paul. Yes I forgot to precise that the matrix is symmetric definite positive. That being said, I am interested in the complexity for standard/widely-used solving methods in finite-elements for elliptic problems (cholesky, ...). Thanks! $\endgroup$ – janou195 Nov 28 '14 at 8:17

The simple answer is that Gaussian elimination (without pivoting) for a matrix of bandwidth $b$ takes $O(nb^2)$ operations, without exploiting further sparsity properties.

In general it is difficult to exploit further sparsity inside the bandwidth with a direct algorithm; classical Gaussian elimination will fill up the bandwidth quickly.

Since the matrix is SPD, Gaussian elimination will be stable without the need for pivoting.

| cite | improve this answer | |

The complexity of direct solver for SPD problems depends essentially of the properties of the underlying graph. If your matrix comes from the discretization of an elliptic equation then it depends essentially on the mesh/ structure which supports the discretization. This is due to the fact that direct methods are based on elimination of unknowns which can generate fill-in (ie denser subgraphs) and therefore more work in the forecoming eliminations.

For instance if the graph of your matrix is a tree you can eliminate unknowns one by one and the complexity of a direct solver is $O(n)$ where is the number of nodes in the graph.

However if the graph is a planar graph (a graph that you can draw on a 2d plane), a well known result by Tarjan and Rose (1979) shows that the complexity is $O(n^{3/2})$. Thanks to their structures, those graphs provide fast elimination and are good candidate for direct methods.

However, at the other side of the spectrum, there are some graphs for which the complexity is maximal like complete graph for which we get $O(n^3$), their corresponding matrices are dense matrices.

| cite | improve this answer | |
  • $\begingroup$ Thanks you, your answer was really useful! $\endgroup$ – Labo Feb 29 at 7:09

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.