Mjollnir

Bandwidth Reduction

My advisor and I visited Butler University in 1989 because they were working with Delft University of Technology on the numerical modeling of the transport of sorbing organic contaminants in aquifers - the very subject of my thesis. But after seeing their work, I commented that the best part of their technology was their scheme to renumber their finite-element grids to achieve a well banded matrix. Everything else they did was bog-standard. They probably weren't too happy with my assessment, and admitted that they bought that particular piece of their kit.

A few years later the USAF sent me to something called Squadron Officer School in Montgomery, Alabama for a few weeks of intense boredom in preparation for becoming a Major. Not being a fan of the deep south, I spent my free time in my room or in the library, assiduously avoiding homework, the sweltering heat and humidity, and the religious and redneck community.

One evening I thought of the bandwidth reduction problem again and decided to give it a go. And after creating some Fortran code (ANSI X3.9 or X3J3) with the military extensions (MIL-STD-1753), I filed it away on my bookcase and forgot about it. After all, it turned out to be quite a simple routine.

Then when my home server died last year (2016) and I started looking for content to replace what I'd lost (I'm apparently not a fan of backing up trivial digital information) I found a few of these routines. While converting this to JavaScript, I noticed some places for improvement, but didn't bother incorporating any. And except for the interface to the UI, this is a true transliteration of one period of boredom from 1991.


The initial population of this matrix is just for show - from a very small 2D FE-grid around an object. It is quite small, but suitable as a demonstration. You can click on the Clear button to remove the links and start over with a single diagonal. Clicking on the numbers will toggle the values. A - means no-connection and a * means a connection. Each value represents one link in the finite-element grid, and if node n is connected to node m, node m will also be connected to node n.

When the Solve button is pressed, the initial bandwidth is calculated (and displayed below), and the entire matrix is copied to the lower matrix where the renumbering happens. The top matrix is left unchanged.

Changing the size of the matrix will also clear the matrix.

The routine processes one line at a time - starting at the diagonal and looking for a no-connection to the right. It then starts at the right and steps back looking for a connection. These two are swapped, and it continues from there walking to the right until the end of the line is reached. When this line is done, the next line starts from the last column of the previous section that had data. And when all the lines are done, the matrix is transposed on the off diagonal and the process repeats. This is done about three times or more, though simple problems are fully optimized on a single pass. If you want, there's buttons below the solution where you can step through these functions one at a time.

The left column of numbers is the new numbering that should be applied to the original finite-element grid to achieve a reduced bandwidth for matrix operations whose stability requires it.

You can step through the problem one function at a time:

The initial bandwidth is ?, and the final bandwidth is ?.

The final left-column numbers are indices for the renumbering. For instance, if the order is [8,2,4,6,5,1,3,7], then grid point 8 should be number 1, 2 should be number 2, 4 should be number 3, and so on. And this solution is not unique. The python code gives [8,4,2,5,6,3,1,7] (inverted, and it indexes by 0 instead of 1 but I've converted it for comparison).

The JavaScript is here. The Python equivalent is here.