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