For reference, to finish this thread and have a record in the archives,
there were two off-list responses that I'm forwarding here:
.............................................
> Does anyone know where the estimates in step-22 came from, or
> alternatively, can anyone point me to a good reference for these type
> of calculations specific to FEM?
Unfortunately, I do not have a proper reference for this.
The part about the bandwidth in step-22 is mainly based on heuristic
arguments. If you order degrees of freedom lexicographically (assume n
degrees of freedom per direction), than one can see that the bandwidth
is n+1 in 2D as DoF (i,j) couples to (i\pm 1,j\pm 1), so the furthest
distance is n+1 on each side to the diagonal. In 3D, the number is
(n+1)^2. Of course, the lexicographic ordering is not optimal for
minimal bandwidth seen over the matrix. Maybe you can find some more
information in the paper by Cuthill and McKee where they present their
reordering algorithm for reduced bandwidth see:
http://dl.acm.org/citation.cfm?id=805928
Fill-in is a different story again. While you would see that
lexicographic orderings produce O(NB) of fill-in by just looking at how
Gaussian elimination works (and as a consequence, also the estimate
O(NB^2) for the computational work, just look at which steps Gaussian
elimination has to do), these approaches are in general inferior to a
reordering that tries to minimize fill-in instead of bandwidth. Most
direct solvers use nowadays some minimum-degree reordering based on
graph theoretical arguments. I guess it does not change the leading
order. I'm sure there is literature on this topic (probably from the
70's or 80's), but I've never gone into details about this and so I
can't really help with literature.
Best,
Martin
................................................................
> > Does anyone know where the estimates in step-22 came from, or
> > alternatively, can anyone point me to a good reference for these type
> > of calculations specific to FEM?
I learned much of this from a FEM textbook I had as an undergraduate
that was written mostly for engineers and was in German. I'm traveling
now so I can look up its authors, but I doubt it would be useful to you
anyway because of the language issue...
> The part about the bandwidth in step-22 is mainly based on heuristic
> arguments. If you order degrees of freedom lexicographically (assume n
> degrees of freedom per direction), than one can see that the bandwidth
> is n+1 in 2D as DoF (i,j) couples to (i\pm 1,j\pm 1), so the furthest
> distance is n+1 on each side to the diagonal. In 3D, the number is
> (n+1)^2. Of course, the lexicographic ordering is not optimal for
> minimal bandwidth seen over the matrix. Maybe you can find some more
> information in the paper by Cuthill and McKee where they present their
> reordering algorithm for reduced bandwidth see:
> http://dl.acm.org/citation.cfm?id=805928
It's actually easy to understand that the situation must be the same
after CMK reordering: the algorithm reorders DoFs one zone at a time
with each DoF in one zone being a neighbor of a DoF in the previous
zone. You can think of this like the shells of an onion. The number of
zones equals the diameter of the connectivity graph. So if you have an n
x n (2d) or n x n x n (3d) mesh, then there are O(n) zones; in 2d, each
zone is a 1-dimensional line through the domain and will therefore have
O(n) DoFs in it; the bandwidth of the matrix will be the distance in
numbering of DoFs in successive zones, so B=O(n) in 2d. In 3d, the zone
is a 2-dimensional sheet with O(n^2) DoFs, so B=O(n^2). I.e., the
estimates are the same as for a lexicographic ordering.
Now you only have to use that n=N^{1/2} in 2d and n=N^{1/3} in 3d.
Cheers
W.
------------------------------------------------------------------------
Wolfgang Bangerth email: [email protected]
www: http://www.math.tamu.edu/~bangerth/
_______________________________________________
dealii mailing list http://poisson.dealii.org/mailman/listinfo/dealii
