Abstract
Objectives
The Finite Element Tearing and Interconnecting method Dual-Primal (FETI-DP) method is one of the non-overlapping domain decomposition methods, which was published by Farhat and his co-workers in the article [FarhatEtAll-01] in 2001. The domain decomposition methods divide the original domain into several smaller subdomains. The FETI-DP method was developed due to problems with singular subdomain matrices in the original FETI method. The FETI-DP method is the combination of the FETI method and Schur complement method.

The FETI-DP method divide unknowns into two categories – corner unknowns and remaining unknowns. The remaining unknowns are further split into remaining interface unknowns and internal unknowns. The continuity conditions are enforced by Langrange multipliers which are defined on the remaining interface unknowns and also by corner nodes. The corner unknowns ensure the non-singularity of the subdomain matrices. The remaining unknowns are eliminated and the coarse problem is after obtained. The matrix of the coarse problem is symmetric and positive-definitive. Therefore the coarse problem can be solved by the conjugate gradient method. More information about FETI-DP method can be found in the article [FarhatEtAll-01] or in the book [Kruis06] by Kruis.

The selection of the the corner nodes where are corner unknowns defined deserves special attention. A definition of the corner nodes was published in the original article [FarhatEtAll-01] by Farhat. The corner nodes are there defined as

D1: Cross-points - It means the nodes which belonged to more than two subdomains

D2: The set of nodes located at the beginning and end of each edge of each subdomain.

But the definition is not suitable for all possible meshes. If the original domain is divided into two subdomains and the first subdomain is surrounded by the second domain, then there is no cross-points and there is not beginning and the end of any edge. Recently, strong influence of the definition of the corner unknowns on the condition number of the subdomain matrix has been observed in the work [KabelikovaEtAll-09] by Kabelíková et all. The large condition numbers of subdomain matrices significantly deteriorate the convergence of the iterative methods used for the solution of the coarse problem. There is a minimal needed number of corner nodes. In the case of two-dimensional meshes, plane strain and plane stress problems require two different nodes, three nodes are better for plate problems. Therefore, the minimum number of needed nodes is three in the case of two-dimensional meshes. In the case of three-dimensional meshes must be selected three non-collinear nodes. Theoretically can be selected all nodes on the subdomain boundaries, but then the FETI-DP method transforms itself to the Schur complement method.

There is no software known to author which can be use for the selection of corner nodes. This was a motivation for a development of an algorithm for the selection such nodes. The algorithm will be developed with help of the graph theory and several heuristic rules.

References:

[FarhatEtAll-01] Farhat, C. and Lesoinne, M. and LeTallec, P. and Pierson, K. and Rixen, D.: “FETI-DP: A Dual-Primal Unified FETI Method-Part I: Faster Alternative to the Two-Level FETI Method” , International Journal for Numerical Methods in Engineering, vol. 50, pages = 1523 – 1544.

[KabelikovaEtAll-09] Kabelíková, P. and Dostál, Z. and Kozubek, T. and Markopoulos, A.: “Generalized inverse matrix evaluation using graph theory”, In Proceedings of the Modelling 2009, Blaheta, R., Starý J. (ed.),Institute of Geonics AS CR, Ostrava, Czech Republic, 2009.

[Kruis-06] Kruis, J.: “Domain Decomposition Methods for Distributed Computing”, Saxe-Coburg Publications, edition 1st, 2006.

Achievements
There were developed two independent algorithm for selection of the corner nodes. The first algorithm is used for two-dimensional meshes and the second algorithm for three-dimensional meshes. Both algorithm are based on the Graph theory. Therefore there will be defined several necessary terms from the Graph theory. A graph G(V,E) consist of a finite set V of elements called vertices and a finite set E of elements called edges. Nodes of a finite element mesh can be mapped to the set V of graph vertices. Vertices vi and vj are connected by an edge if the appropriate nodes belong to a edge of the finite element. Otherwise, there is no edge between vi and vj. This graph is called nodal graph. The degree dG(v) of vertex v in graph G is the number of edge of G incident with v. A walk in a graph G = (V, E) is a ﬁnite sequence of vertices v0 , v1 , . . . , vk such that (vi−1, vi ), 1 ≤ i ≤ k is an edge in the graph G. The nodes v0 and vk are called end vertices of the walk. A walk is a trail if all its edges are distinct.

In the case of the two-dimensional algorithm, the graph B(V,E) is established form boundary nodes between subdomains. The vertex degree is established for each vertex in the graph. The corner nodes is then defined as

vertices which vertex degree is equal to one

vertices which vertex degree is more than two

The algorithm, which selects corner nodes, based on the vertex degree is called minimal number algorithm. A control of chosen nodes must be done after the selection procedure. The number of corner nodes is controlled. The minimum number of needed nodes is three. If there are no enough nodes from the minimal number algorithm then the another nodes must be selected.

The next control is aimed on the geometrical relation between corner nodes. If the selected nodes are too close each other, the subdomain matrix has usually very large condition number. A distance between corner nodes are controlled . The next condition is a non-collinearity condition. This is necessary in order to avoid several nodes in one line which lead also to large condition number of subdomain matrix.

It is possible to add further corner nodes by an extended algorithm for adding corner nodes. The extended algorithm is based on the restriction of the graph B(V,E) into several subgraphs. The subgraphs Sj (V,E) are defined as the open trail between two corner nodes in the graph B(V,E). The further corner nodes can be added as the centre of such subgraph or the walk can be split into k part and the corner node can be added at the end of such part of the walk.

The several numerical test was done with help of SMP computer Ness and supercomputer HECToR.

The following behaviour of the algorithm was observed. Higher number of corner nodes reduces the number of iterations in the conjugate gradient method and therefore also the computational time is reduced. If an optimal number is reached, the number of iterations still decreases but the total computational time starts to grow because time of condensation of the matrix contains entries related to the corner nodes prevails over time saved by the reduced number of iterations. The tests also showed the ability of the proposed algorithm to select the minimum number of corner nodes in the case of very general domains. The FETI-DP method can be therefore used without manual selection of corner nodes.