Bisection for parallel computing using Ritz and Fiedler vectors

Summary. In this article, an efficient algorithm is developed for the decomposition of large-scale finite element models. A weighted incidence graph with N nodes is used to transform the connectivity properties of finite element meshes into those of graphs. A graph G₀ constructed in this manner is then reduced to a graph G_n of desired size by a sequence of contractions G₀ G₁ G₂ G_n. For G₀, two pseudoperipheral nodes s₀ and t₀ are selected and two shortest route trees are expanded from these nodes. For each starting node, a vector is constructed with N entries, each entry being the shortest distance of a node n_i of G₀ from the corresponding starting node. Hence two vectors v₁ and v₂ are formed as Ritz vectors for G₀. A similar process is repeated for G_i (i=1,2,,n), and the sizes of the vectors obtained are then extended to N. A Ritz matrix consisting of 2(n+1) normalized Ritz vectors each having N entries is constructed. This matrix is then used in the formation of an eigenvalue problem. The first eigenvector is calculated, and an approximate Fiedler vector is constructed for the bisection of G₀. The performance of the method is illustrated by some practical examples.