2
$\begingroup$

is anyone here aware of whether there exist bounds on the optimal bandwidths of 2D/3D FEM stiffness matrices?

Edit: more specifically, I would like to have bounds on the minimum bandwidth after optimally reordering the matrix. (This definition of bandwidth is the usual one in graph theory.)

$\endgroup$
5
  • 1
    $\begingroup$ I think that the upper bound is $n-1$ for an $n \times n$ matrix. This happens when an element is composed of the first and last nodes in the mesh. $\endgroup$
    – Chenna K
    Aug 22 at 13:01
  • $\begingroup$ sorry, I should have clarified a bit. In Graph theory the bandwidth refers to the minimum bandwidth after reordering. So I was talking about the minimum bandwidth. See here: en.wikipedia.org/wiki/… $\endgroup$
    – bobo
    Aug 22 at 13:37
  • 1
    $\begingroup$ Without further assumptions about the mesh, the upper bound is $n-1$ for a $\sqrt{n}$ by $\sqrt{n}$ mesh. There are examples of unstructured meshes where reordering does not reduce the bandwidth. $\endgroup$ Aug 22 at 18:17
  • 1
    $\begingroup$ I'm pretty sure you want the lower bound in your first sentence. $\endgroup$ Aug 22 at 22:20
  • $\begingroup$ You are right.. what I wanted was a sharp lower bound on the minimal bandwidth. The nomenclature is slightly confusing as I am essentially interested in the graph-theoretic bandwidth, i.e. after optimally reordering it. As you pointed out, I would like to know how much we can reduce the bandwidth. $\endgroup$
    – bobo
    Aug 23 at 14:25
4
$\begingroup$

Let's take an $n\times n$ mesh (with $N=n^2$ unknowns) and think about whether you can enumerate them in such a way that you end up with a bandwidth less than $m=n=\sqrt{N}$? You get this bandwidth with a 5-point stencil if you enumerate the first row left to right, then the next row left to right, etc. In that case, each degree of freedom $i$ couples with $i-1$ and $i+1$ (left and right neighbors) as well as with $i+n$ and $i-n$ (top and bottom neighbors), and each coupling results in a nonzero entry in the matrix. Try as you might, you will not find a better numbering, and so the lower bound for the bandwidth is $m=\sqrt{N}$. Of course, the (uninteresting) upper bound is $m=N$ which you essentially get with a random enumeration.

In the 3d context, similar arguments for a $n\times n \times n$ mesh with $N=n^3$ unknowns lead to a lower bound for the bandwidth of $m=n^2=N^{2/3}$.

One can generalize these sorts of considerations to unstructured meshes in which case the Cuthill-McKee algorithm provides a pretty decent enumeration of degrees of freedom. In that case, the lower bound for the bandwidth is given by the largest set of unknowns (a "layer") that are enumerated in one step of the algorithm, over which you would then take the minimum over all possible starting sets for the algorithm.

$\endgroup$
7
  • $\begingroup$ Small addition. For the finite difference example here, it is possible (for example, using Hilbert space filling curves) to reduce the average bandwidth per row at the expense of having some rows with large bandwidths. (This is useful when locality in terms of memory and cache accesses is the bottleneck) (Also, Cuthill-McKee achieves the same result and it is more general) However, in the strictest terms, the bandwidth of that matrix cannot be less than $\sqrt{N}$. $\endgroup$ Aug 23 at 1:13
  • 1
    $\begingroup$ That's right. There are methods that minimize the bandwidth of some rows of the matrix, but if you define "the bandwidth" as the maximum over all rows, then $\sqrt{N}$ in 2d and $N^{2/3}$ in 3d is the lower bound. $\endgroup$ Aug 23 at 2:29
  • $\begingroup$ Completely agree! The question made me think that maybe my addition could help the asker if they care about more technical details. $\endgroup$ Aug 23 at 2:34
  • $\begingroup$ Yes. Sometimes the bandwidth is not what you care about. For sparse direct solvers, "minimum degree" reorderings minimize the amount of fill-in. $\endgroup$ Aug 23 at 3:54
  • 1
    $\begingroup$ If you are using the linear continuous Galerkin method on quadrangles, it is easy to show that it is exactly the same method as 5-point finite difference. For higher order and/or discontinuous methods, a graph theoretical analysis can be done -given an ordering-, and it is not that hard. Finding a lower bound is trickier, but can be done assuming we know something about the mesh (structure, connectivity, ...). But, I think, this is one of the cases where stating the theorem/lemma properly is more difficult than proving it rigorously. $\endgroup$ Aug 23 at 15:16

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.