# Bounds for the optimal bandwidth of 2D/3D FEM stiffness matrices

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

• 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. Aug 22 at 13:01
• 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/…
– bobo
Aug 22 at 13:37
• 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. Aug 22 at 18:17
• I'm pretty sure you want the lower bound in your first sentence. Aug 22 at 22:20
• 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.
– bobo
Aug 23 at 14:25

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}$$.
• 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}$. Aug 23 at 1:13
• 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. Aug 23 at 2:29