A Lagrange multiplier based divide and conquer finite element algorithm

Computing Systems in EngineeringVol. 2, No. 2/3, pp. 149-156, 1991

0956-0521/91 $3.00+ 0.00 PergamonPress pie

Printed in Great Britain.

A LAGRANGE MULTIPLIER BASED DIVIDE A N D CONQUER FINITE ELEMENT ALGORITHM C. FARI-IAT Department of Aerospace Engineering Sciences and Center for Space Structures and Controls, University of Colorado at Boulder, Boulder, CO 80309-0429, U.S.A.

(Received 7 December 1990) Abstract--A novel domain decomposition method based on a hybrid variational principle is presented. Prior to any computation, a given finite element mesh is torn into a set of totally disconnected submeshes. First, an incomplete solution is computed in each subdomain. Next, the compatibility of the displacement field at the interface nodes is enforced via discrete, polynomial and/or piecewise polynomial Lagrange multipliers. In the static case, each floating subdomain induces a local singularity that is resolved very efficiently. The interface problem associated with this domain decomposition method is, in general, indefinite and of variable size. A dedicated conjugate projected gradient algorithm is developed for solving the latter problem when it is not feasible to explicitly assemble the interface operator. When implemented on local memory multiprocessors, the proposed methodology requires less interprocessor communication than the classical method of substructuring. It is also suitable for parallel/vector computers with shared memory and compares favorably with factorization based parallel direct methods.

2. DOMAIN DECOMPOSITION VIA LAGRANGE

1. INTRODUCTION

MULTIPLIERS

In this paper, we present a subdomain based parallel The variational form of the three-dimensional finite element method that is a departure from the boundary-value problem to be solved is as follows. classical method of substructures. It is based on a G i v e n f a n d h, find the displacement function u which hybrid variational principle and blends direct and is a stationary point of the energy functional iterative numerical schemes. Its unique feature is that it requires less interprocessor communication than J(v)=½a(v,v)-(v,f)-(v,h)r (1) conventional domain decomposition algorithms, while it still offers the same amount of parallelism. In where many cases, it also performs fewer operations than other solution techniques which makes it interesting even as a serial algorithm. In Sec. 2, we derive a a(v, w) = fn v(i'J)c#ktW(k'Odf~ computational algorithm from a hybrid variational principle where the inter-subdomain continuity constraint is removed via the introduction of discrete, (v,f) = fa vif d[l polynomial, and piecewise polynomial Lagrange multipliers. An arbitrary mesh partition typically contains a set of floating subdomains which induce (v, h)r = vihi dfL local singularities. The handling of these singularities is treated in Sec. 3. A parallel preconditioned conjugate projected gradient algorithm is developed In the above, the indices i,j, k take the values 1-3, in Sec. 4 for the solution of the interface problem vtij~ = (vij + vj,i)/2 and vij denote the partial derivative which couples local zero energy modes and the of the ith component of v with respect to the j t h Lagrange multipliers. Section 5 emphasizes the spatial variable, Cokt are the elastic coefficients, parallel characteristics of the proposed method and denotes the volume of the elastostatic body, F its contrasts it with conventional Schur methods. piecewise smooth boundary, and F h the piece of F Section 6 illustrates the method with the parallel where the tractions hi are prescribed. solution of structural examples on the iPSC/2 and If ~ is subdivided into N s regions {f~p} ; : ~ (Fig. 1), CRAY-2 muitiprocessors. Finally, Sec. 7 concludes solving the above elastostatic problem is equivalent this paper. to finding the displacement functions {up}~: ~' which

frh

149

150

C. FARHAT

IIII

I

Ill

I

IIIIIllll

I

lllllltll

'

IIIIIIIII IIIIIIlll

III

IIIII

,

llllJiili

/lllll

for any admissible tvpjp=l ~.. ~p=u. and {#k}k=l. k=, Among all p=Ns which satisfy the continuity admissible sets {vp}p=~ conditions (3), the set {up}~==~, minimizes the sum of the energy functionals Jp defined respectively on f~p. Therefore, {up}~2 ~, are the restriction of the solution p=N~ . u of the non-partitioned problem (1) to {f~p}p=, Indeed, Eqs (4) and (5) correspond to a hybrid variational principle where the inter-subdomain continuity constraints (3) are removed by the introduction of Lagrange multiplies) p=Ns are If now the displacement fields {up}p=l expressed by suitable shape functions as

L~

"

~"

i[i[[[[iiiL y

up=Nup

Fig. 1. Decomposition in N~ subdomains. are stationary points of the energy functionals

Jp(v,) = ½a(Vp. Vp)n, - (vp.f)n, - (vp. h)r,

(2)

p = l . 2 . . . . . NS

(6)

and the continuity equations are enforced for the discrete problem at each degree of freedom on FI, a standard Galerkin procedure transforms the hybrid variational principle (4) and (5) in the following algebraic system:

where KpUp = fe a(Vp, Wp)tl p = f f t YP(i'/)CijklWP(k'O df~ p

B pT

p = Ns

Bpup = 0 p = 1.2.3 . . . . . Ns

(7)

p=l

(vn.f)o¢ = fn e v,,f~dt'l (v,,h)r=~r

v,,h, d r

p = l , 2 . . . . . Ns

and which satisfy on the interface boundary Fn the continuity constraints p=Ns,q=N s up = Uq

on F, =

U

{fl.,,fqflq}'

(3)

p=l,q=l

Solving the N~ above variational problems (2) with the subsidiary continuity conditions (3) is equivalent to finding the saddle point of the Lagrangian

where Kp, Up, and fp are, respectively, the stiffness matrix, the displacement vector, and the prescribed force vector associated with the finite element discretization of f~p. Bp is a connectivity boolean matrix: it prescribes which degrees of freedom in f~p lie on F~. In particular when operating on a matrix or vector quantity, Br does not involve any floating point operation; it simply extracts the interface components of that matrix or vector quantity. The vector of Lagrange multipliers 2 represents the interaction forces between the subdomains {~p }~= ~ along their interface F I. If every subdomain has enough boundary conditions to eliminate its rigid body motions, the above equations of equilibrium can be transformed into

p=Ns

J*(vl. v2 . . . . . VN~.ltl. #2 . . . . . I~,) = ~ Jp(vp)

p=Ns

p=l

FI~=

p ~ Ns, q = N s

+

~.

(vp -- Vq. I~pq)r, (4)

p=l,q=l

where

Z p=l

BpKplfp

Up= KT~ (fp - B~2) p = l . 2 . . . . . N s

(8)

where (' (Up -- Uq, I,lpq)Fl = ~ FI ~.£pq(Vp -- Vq)

dF

FI =

that is, finding the displacement fields {Up}p=l p =Ns and the Lagrange multipliers 2pq which satisfy J*(ul,

u2 . . . . .

UNs, ~1 . . . . .

~2 . . . . .

~t)