The following content has been provided by the University of Erlangen-Nürnberg.

Last time we have discussed several aspects of writing a classical simple finite element program.

We will finish these considerations today by having some thoughts about bandwidth reduction

and then we should be able really to write step by step admittedly simple

but complete finite element program for a linear elliptic boundary value problem.

This we will do as I said in the exercises step by step and we should have finished that after Christmas.

Okay, so what have we seen is that we have to take, we have seen how to put up the matrix,

we have seen the assembly process typically element wise oriented

and we have discussed now how to solve the emerging sets of linear equations.

We have remembered what we know about direct solvers.

Later on we will discuss a little bit more in detail iterative solvers and more advanced methods.

What we have seen for using direct solvers under the assumption that no pivoting is necessary in the Gaussian

or in the Cholesky process, then it's decisive concerning the operation count

that we have a small bandwidth or that we have a small hull, a small profile.

If we look at the Cholesky method we know if the overall dimension is capital M, cross capital M,

and we have a bandwidth of small m, we need small m squared times m operations.

And if you remember the simple situation of the five point stencil on the square,

then if we take a row wise or a column wise numbering then basically the small m is the square root of capital M,

so we have already gained one order in complexity only by this simple measure.

But in the next simple step if the domain is say a rectangle,

then it makes a difference whether we take a row wise or a column wise ordering.

And if it's either the domain is even more complicated or our discretization is more complicated

in the sense that we are now in the finite element setting, we have an unstructured mesh,

then of course the general question arises what to do.

How shall we number the degrees of freedom?

How shall we number the nodes in the interior plus eventually those at the boundary

such that we have a minimal or not too large bandwidth, not too large hull or profile.

Okay, I will discuss a few methods in this direction.

Base is basically one method and what is typical is that all these methods are more or less heuristics,

not so easy really to prove something rigorous about it.

So first let us again note where those quantities come from to set up the data structure

either as a band data structure or data structure as an oriented list if we want to store the hull.

We need quantities like the bandwidth or more precise we need something like what we have called

the row wise left handed bandwidth and this correspondingly related to that this quantity FIA

which for the corresponding row denotes the first position where the first non-zero entry appears.

Okay, yeah, of course up to now we said okay, yeah we get this structure by looking at the matrix

but of course it is not a good idea to build up the matrix, store it in a two dimensional entity

and then extract another storage possibility out of that.

That should be all work in one step and therefore we just have to remind ourselves that

here in the special case where we are with the specific finite elements which we later on will call

Lagrangian elements or finite elements where the degrees of freedom are situated at the nodes of the element.

This applies also to other geometrical shapes not only to triangles and not only to 2D.

We have the situation that we, where is it, it is not written up here.

It is missing here on the transparency unfortunately, sorry for that.

We just, we know that we have neighborhood, that we have possible entries if we look at a row

only for the neighborhoods in this triangle or for the neighborhoods in these elements in this framework I just sketched.

So we just have to, we can define these quantities for example the FIA in terms of the

neighboring elements in the corresponding triangles.

So we only need the geometric information, we don't have to build up the whole matrix to see what is the storage pattern.

We only need this geometrical information to build up these numbers FIA and MIA, they are basically the same.