optimal numbering scheme for FEM over uniform grid

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?

  1. what's the numbering scheme corresponding to this optimal bandwidth?

  2. 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?

references or hint would be appreciated.

thank you.

Qianqian

Reply to
Qianqian Fang
Loading thread data ...

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 Locock

Reply to
Greg Locock

PolyTech Forum website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.