Keywords: relational database model, mesh generation, numerical programming.

The numerical algorithms have become quite complex and require dynamic data structures. The general numerical practice is the use of a mixed data structure which is endowed with a representation of an unbalanced geometric search tree. The advanced front (AF) algorithm [1,2,3,4,5] is a well-known and efficient algorithm of the non-structural mesh generation. We present an accelerated version of this algorithm as an example to demonstrate, that a simplified relational database model is an efficient tool for handling dynamic data structures arising from numerical problems. The main advantage of this technique is the simple and uniform data structure and the application of the balanced trees for searching and modification.

The described version of the AF algorithm is based mainly on the works of George and Seveno [2], Möller - Hansbo [3]. However we have completed it with an accelerator step by introducing front levels and an improved backtrack step [3]. The reason of the choice of this algorithm was that it is well-known and its previous implementations are well published [4]. These implementations use mixed data structures and special unbalanced geometric search trees. The Alternating Digital Tree [5], the Quadtree-Octree and the R-tree [6] are the most popular ones.

In the case of data processing the application of the relation database model [7,9], is exclusive nowadays. The direct application of this model to numerical algorithms is quite complex and slow. Hence we have simplified this model by enabling only one ordering on a data table and using integrated data and index tables. We have resolved the problem of the geometric searching by introducing non-uniform search cells. In such a way we could preserve the advantages of the uniform data structure and the balanced search trees without sacrifying the program speed and memory requirement. Our implementation is written in a flexible search tree independent form and was tested with Red-Black tree and B-tree [8,9] realizations.

1

J. Peraire, J. Peiro, L. Formaggia, K. Morgan, and, O. C. Zienkiewicz, "Finite Element Euler Computation in Three Dimensions", Int. J. for Num. Methods in Eng. 26, 2135-2159, 1988. doi:10.1002/nme.1620261002

2

P. L. George and E. Seveno, "The Advancing-Front Mesh Generation Method Revisited", Int. J. for Num. Methods in Eng. 37, 3605-3619, 1994. doi:10.1002/nme.1620372103

3

P. Möller and P. Hansbo, "On Advancing Front Mesh Generation in Tree Dimensions", Int. J. for Num. Methods in Eng., 38, 3551-3569, 1995. doi:10.1002/nme.1620382102

4

J. F. Thomson, B. K. Soni and N. P. Weatherill (ed.), "Handbook of Grid Generation", CRC Press, 1999.

5

J. Bonet and J. Peraire, "An Alternating Digital Tree (ADT) Algorithm for 3D Geometric Searching and Intersection Problems", Int. J. for Num. Methods in Eng., 31, 1-17, 1991. doi:10.1002/nme.1620310102

6

H. Samet, "Application of Spatial Data Structures", Addison-Wesley, Reading, MA, 1990.

7

E. F. Codd, "A Relational Model of Data for Large Shared Data Banks", Communication of the ACM, 13(6), 377-387, 1970. doi:10.1145/362384.362685

8

T. H. Cormen, C. E. Leiserson and R. L. Rivest, "Introduction to Algorithms", The Massachusetts Institute of Technology 1990.

9

H. Garcia-Molina, J.D. Ullman and J. Widom, "Database System Implementation", Prentice Hall, 2000.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £85 +P&P)