1
$\begingroup$

In Golub and Van Loan's book, Matrix Computations, page 606, it is stated that:

With standard discretizations, 2-dimensional problems can be solved with $O(n^{3/2})$ work and $O(n \log{n})$ fill-in. For 3-dimensional problems, the typical costs are $O(n^2)$ work and $O(n^{4/3})$ fill-in.

Here, they refer to elliptic partial differential equation problems solved on a grid and $n$ refers to the number of unknowns. I guess it is trivial to calculate the cost (probably linear) for one-dimensional problems, but I don't know how to do that. I would appreciate any help for that.

$\endgroup$
6
$\begingroup$

It may help to define $N$, the number of discretization points along a 1D edge, and relate it to $n$, the number of unknowns in the system. In 2D on a square grid of points, $n = O(N^2)$. Nested dissection efficiently reduces the sparse system you usually get from discretizations by eliminating levels of "interior" points. The result is a more dense system the size of a few lines of "separator" points, which is of size $O(n^{1/2})$ and can be solved directly in $O(n^{3/2})$ time. The fill-in costs come from the fact that eliminating interior points at each level couples more points together (creating new connections in the matrix, hence fill-in).

The 3D costs come about similarly, except now $n = N^3$, and the separators are now planes with $O(N^2) = O(n^{2/3})$ points. Solving systems involving these planes then gives you the $O(n^2)$ cost).

However, for 1D problems, $n=N$, and you can order unknowns from left to right to get a tridiagonal system, which can be solved in $O(n)$ time with no fill-in with the Thomas algorithm.

Edit: Thanks to Bill for pointing out that this is for standard low-order finite difference/element schemes - for example, higher order FD lead to increased bandwidth, high order FEM leads to a block structure. The Thomas algo can be modified to give a similar orders of work/storage, though the constants involved increase.

$\endgroup$
  • $\begingroup$ Thank you @JLC. I need to learn graph theory to digest all but could you give me a hint why it becomes tridiagonal for 1D systems? And I am curious if this is true for graphs that are approximately 1D (long and thin). $\endgroup$ – Armut Dec 11 '14 at 7:52
  • $\begingroup$ Sure - each point represents a column, and the rows of the column are nonzero for points that connect to it. The diagonal is nonzero since a point connects to itself, and since you can order one point after another in 1D, each point connects to at most the point before/after, which leads to only nonzeros in the entries above and below each diagonal. $\endgroup$ – Jesse Chan Dec 11 '14 at 13:18
  • 1
    $\begingroup$ @JLC, this is only true in 1D for the 3-point finite difference operator. A 5-point 1D stencil for the Laplacian would have 2 more diagonals. Etc. $\endgroup$ – Bill Barth Dec 11 '14 at 13:32
  • 1
    $\begingroup$ Yes, agreed, and same w/splines or less-compactly supported discretizations. I'll edit that in. $\endgroup$ – Jesse Chan Dec 11 '14 at 13:44

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.