Re: optimal numbering scheme for FEM over uniform grid

From: Greg Locock (greglocock_at_yahoo.com.au)
Date: 08/03/04 

Date: Tue, 03 Aug 2004 17:48:16 +0000

Qianqian Fang wrote:
> hello
>
> I am estimating the optimal bandwidth for the FEM matrix over an NxNxN
> uniform grid. The band width is related to the numbering scheme.
>
> My questions are:
>
> 1. what is the optimal bandwidth for an NxNxN grid meshed by
> tetrahedron elements in terms of N?
>
> 2. what's the numbering scheme corresponding to this optimal
> bandwidth?
>
> 3. what's the asymptotic form of the optimal bandwidth w.r.t. N?
>
>
> I have read some books on the BW reduction for FEM matrices, but they
> addressed to more general unstructual meshes. I just wondering whether
> there are simple analytical relation which has been discovered for
> this simple uniform grid?
>
> Once I saw some discussion on the complexities of 3D FEM, I remember
> (if correctly) the asymptotic form for the complexity of solving the
> matrix equation by direct method is O(P^2) (P is the total num of
> unknown, in this case, P=N^3). If the matrix is solved by Cholesky
> decomp, the estimated bandwidth should be on the scale of
> sqrt(P)=N^(3/2), how can I get this bandwidth in this NxNxN grid?

You need to define optimum. The minimal maximum bandwidth (measured in
elements, not DOF, which is typically used) you could manage is N^2 (ie
one slice through the structure, parallel to one face), whereas I
suspect the optimum computation time solution (minimal RMS bandwidth)
would have a maximum bandwidth given by 2*N^2 (ie work along the
diagonal). These two cases are typically used to minimise the maximum
memory size, and the total cost of the run, respectively, back when such
things were important.

The total number of operations is the same in each case, N^3, giving a
total solution effort of the order of N^5.

I found when optimising wavefronts that it had more in common with
maze-exploration than FEA. There again before I wrote our WAVEOPT
program we had to renumber elements by hand (and we had to walk uphill
to work and uphill home again).

It is not obvious to me from a geometrical viewpoint how you could get a
max bandwidth as low as N^1.5, given such a regular structure.

Cheers

Greg Lo***

Quantcast