Graph Products for Ordering and Domain Decomposition
A number of algorithms based on domain decomposition methods have been proposed for the solution of the partial differential equations arising in solid and fluid mechanics problems, among others. These methods are generally spurred by the advent of parall
- PDF / 1,691,252 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 32 Downloads / 259 Views
Graph Products for Ordering and Domain Decomposition
6.1
Introduction
A number of algorithms based on domain decomposition methods have been proposed for the solution of the partial differential equations arising in solid and fluid mechanics problems, among others. These methods are generally spurred by the advent of parallel processors and are motivated by the fact that domain decomposition provides a natural route to parallelism. Given a number of available processors q, an arbitrary finite element model (FEM) is decomposed into q subdomains where formation of element matrices, assembly of global matrices, partial factorisation of the stiffness matrix and state determination or evaluation of generalised stresses can be carried out independently of similar computations for the other subdomains and hence can be performed in parallel. While the subdomains are processed in a parallel architecture, the time to complete a task will be the time to compute the longest subtask. An algorithm for domain decomposition will be efficient if it yields subdomains that require an equal amount of execution time. In other words, the algorithm has to achieve a load balance among the processors. In general, this will be particularly ensured if each subdomain contains an equal number of elements or equal total number of degrees of freedom. In the previous chapter ordering and graph partitioning were performed using special canonical forms. In this chapter, the properties of graph products are utilised for efficient ordering and decomposition. Here, an efficient analytical method is presented for calculating the eigenvalues of space structures and finite element meshes (FEMs) with regular topologies. In this method, the graph model of a FEM is considered as the Cartesian product of its generators. The eigenvalues of the Laplacian matrix for this graph model is then easily calculated using the eigenvalues of their generators [1, 2]. An exceptionally fast method is also proposed for computing the second eigenvalue and eigenvector v2 of the Laplacian of the graph model. The entries of v2 are then ordered and accordingly the graph is partitioned, and the corresponding finite element mesh is bisected. This vector is A. Kaveh, Optimal Analysis of Structures by Concepts of Symmetry and Regularity, DOI 10.1007/978-3-7091-1565-7_6, © Springer-Verlag Wien 2013
131
132
6 Graph Products for Ordering and Domain Decomposition
Fig. 6.1 A FE mesh and its skeleton graph. (a) A simple finite element mesh. (b) The skeleton graph of the FE mesh
a
b
also employed for the nodal numbering to reduce the profile of the stiffness matrices. The idea study is extended to other graph products and an efficient approximate method is presented. Examples are included to illustrate the efficiency of the method. It should be noted that in this chapter, the two words ‘generator’ and ‘regular’ are used in their literal senses and their meaning should not be taken identical to those employed in topology and graph theory. Here, the geometry of the models need not
Data Loading...
