Improving the finite element ordering for the frontal solver
Keywords:
reordering, frontal solver, greedy method, wave method, Tabu SearchAbstract
We present the structure of greedy methods used for reordering the nodes or the finite elements of a mesh and we propose two improvements that can be easily implemented in existing software. We investigate a wave reordering method which adapts the reordering strategy during the reordering process. Then, we propose an adaptation of the Tabu Search optimization technique for finite element reordering. The results show the efficiency of the improvements The wave reordering method and the Tabu Search provide very good solutions offering a motivation to carry on research for optimizing their computing time.
Downloads
References
[AAR 97] AARTS E., LENSTRA J. K., Local search in combinatorial optimization, John
Wiley and Sons, 1997, Series in Discrete Mathematics and Optimization.
[ARM 84] ARMSTRONG B. A., "A Hybrid Algorithm for Reducing Matrix Bandwidth", Int.
J. for Num. Meth. in Eng., vol. 20, 1984, p. 1929-1940.
[ARM 85] ARMSTRONG B. A., "Near-Minimal Matrix Profiles and Wavefronts for Testing
Nodal Resequencing Algorithms", Int. J.for Num. Meth. in Eng., vol. 21, 1985, p. 1785-
[BER 70] BERGE C., Graphes et Hypergraphes, Dunod, 1970.
[CUT 69] CUTHILL E., MCKEE J., "Reducing the bandwidth of sparse symmetric matrices",
Proc. 24th National Conference of the Association for Computing Machinery, 1969, p. 157-
, New Jersey.
[DUF 89] DUFF I. S., REID J. K., SCOTT J. A., ''The Use of Profile Reduction Algorithms
with a Frontal Code", Int. J.for Num. Meth. in Eng., vol. 28, 1989, p. 2555-2568.
[ESC 92] ESCAIG Y., "Decomposition de domaines multiniveaux et traitement distribue pour
la resolution de problemes de grande tailles", PhD thesis, Universite de Technologie de
Compiegne, 1992.
[EVE 79] EVERS TINE G. C., "A Comparison of Three Resequencing Algorithms for theReduction
of Matrix Profile and Wavefront", Int. J. for Num. Meth. in Eng., vol. 14, 1979,
p. 837-853.
[GIB 76] GIBBS N. E., JR W. P., STOCKMEYER P. K., "An Algorithm for Reducing the
Bandwidth and the Profile of a Sparse Matrix", SIAM J. Numer. Anal., vol. 13, num. 2,
, p. 236-250.
[GLO 98] GLOVER F., LAGUNA M., Tabu Search, Kluwer Academic Publishers, 1998.
[IR.O 70] IRONS B. M., "A Frontal Solution Program for Finite Element Analysis", Int. J.for
Num. Meth. in Eng., vol. 2, 1970, p. 5-32.
[KUM 97] KUMFERT G., POTHEN A., ''Two Improved Algorithms for Envelope and Wavefront
Reduction", BIT nordisk tidskrift for informationsbehandling, vol. 37, 1997, p. 559-
[NEG 97] NEGRE S., BOUFFLET J.P., CARLIER J ., "Reordering finite elements for the frontal
method", Second Metaheuristics International Conference, MIC'97, July 1997, Sophia
Antipolis, France.
[RAZ 80] RAZZAQUE A., "Automatic Reduction of Frontwidth for Finite Element Analysis",
Int. J.for Num. Meth. in Eng., vol. 15, 1980, p. 1315-1324.
[REI 99] REID J. K., SCOTT J ., "Ordering Symmetric Sparse Matrices for Small Profile and
Wavefront", Int. J.for Num. Meth. in Eng., vol. 45, 1999, p. 1737-1755.
[SCO 99] SCOTT J., "On Ordering Elements for a Frontal Solver", Commun. Numer. Meth.
Engng., vol. 15, 1999, p. 309-323.
[SLO 83] SLOANS. W., "Automatic Element Reordering for Finite Element Analysis with
Frontal Solution Schemes", Int. J.for Num. Meth. in Eng., vol. 19, 1983, p. 1153-1181.
[SLO 86] SLOANS. W., "An Algorithm for Profile and Wavefront Reduction of Sparse Matrices",
Int. J. for Num. Meth. in Eng., vol. 23, 1986, p. 239-251.
