Browse Prior Art Database

ITERATIVE METHODS FOR ELLIPTIIC PROBLEMS ON REGIONS PARTITIONED INTO SUBSTRUCTURES AND THE BIHARMONIC DIRICHLET PROBLEM

IP.com Disclosure Number: IPCOM000128185D
Original Publication Date: 1984-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 14 page(s) / 43K

Publishing Venue

Software Patent Institute

Related People

Olof B. Widlund: AUTHOR [+3]

Abstract

In this paper, we will discuss some special iterative methods for elliptic finite element problems defined on regions regarded a<_; unions ofsubregions. We are interested, in particular, in the design of algorithms for which the interaction between the subproblems, i.e. the discrete elliptic problems on the subregions, is computed with the aid of a conjugate gradient method, while the subproblems themselves are solved by a direct method. This approach differs from the standard one used in industry where direct methods are employed throughout. The partition of elliptic problems into subproblems is a very natural idea that is widely used in practice and which has been discussed in the engineering litera-ture for at least twenty years; see e.g. Prezemieniecki [18,19). Thus the modeling of an entire mechanical system can profitably be organized by discreti-zing the partial differential equations by finite elements on subregions. These tasks and the factorization of the resulting stiffness matrices for the subprob-lems can be assigned to different engineering groups and computer systems or processors with coordination required only at the interfaces between the sub-structures to assure matching of finite element triangulations and solutions. These ideas are particularly attractive for parallel computing and in the case when some of the substructures are identical or previously analyzed as in the case when a simulation is repeated after the redesign or damage of one or a few of the substructures. The final phase, in which the interaction is accounted for, does not lend itself equally well to parallel computing and it also represents a significant fraction of the total computational work even on a sequential computer. Three alternative methods are discussed in this paper and numerical results for a model problem are presented. These algorithms are analyzed in detail in a forth- coming paper by Bj rstad and Widlund [4], in which a complete theory for conform-ing Lagrangian finite element approximations of second order elliptic problems in the plane are given. The development of this theory requires the use of ellip-tic regularity theory for problems on Lipschitz regions; see Grisvard [15], and some apparently new finite element results. We regard the extension of these results to more general elliptic problems as a significant open problem. Earlier work on algorithms of this kind is reported in Concus, Golub and O'Leary [6], who gave numerical results for Poisson's problem on T-shaped regions. For an analysis of this method see BjOrstad and Widlund (4]. Two interesting new pre-conditioners for the same special problem are introduced in the contribution to these proceedings by Golub and Mayers [12]. In their numerical experiments a comparison is made between these algorithms and the one characterized as second best in our previous paper; cf. BjOrstad and Widlund [3]. Methods inspired by Schwarz' alternating method and by control theory are considered in Glowinski, Periaux and Dihn (10]. For a discussion of one of these, see BjOrstad and Widlund [4]. There has also been extensive activity in the Soviet Union in this area. We are not yet well acquainted with this work and are grateful to Yu. Kuznetsov and Maximilian Dryja for drawing our attention to it. After our first series of numerical experiments, we received a preprint of one of Dryja's papers [8],from which we first learned of what we currently regard as the best algorithm. In that paper Dryja analyzes the case of Laplace's equation on L-shaped regions.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

ITERATIVE METHODS FOR ELLIPTIIC PROBLEMS ON REGIONS PARTITIONED INTO SUBSTRUCTURES AND THE BIHARMONIC DIRICHLET PROBLEM

By Olof B. Widlund '`

January 1984

Report 4101 *Prepared for the Proceedings of the Sixth International Conference on Computing Methods in Applied Science and Engineering, held at Versailles, France, December 12-I6, 1988. TERATIVE METHODS FOR ELLIPTIC PROBLEMS ON REGIONS PARTITIONED INTO SUBSTRUCTURES AND THE BIHARMONIC DIRICHLET PROBLEM

Olof B. Widlund Courant Institute of Mathematical Sciences New York University 251 Mercer Street, New York, N.Y. 10012 U.S.A.

A finite element problem can often naturally be partitioned into subproblems which correspond to subregions into which the region has been partitioned or from which it was origi-nally assembled. A class of methods are discussed in which these subproblems are solved by direct methods while the interaction between the subregions is handled by a conjugate gradient algorithm. The mathematical framework for this work is provided by regularity theory for elliptic finite element equations and block-Gaussian elimination. The same tools can be used to provide a reinterpretation of Bjbrstad's work on very fast methods for the biharmonic Dirichlet problem on rectangles and a variant of an algorithm introduced by Glowinski and Pironneau for mixed finite element approxi-mations of the same elliptic problem on general regions. The relationship between substructuring and finite element-capacitance matrix techniques is also briefly explored.

INTRODUCTION

In this paper, we will discuss some special iterative methods for elliptic finite element problems defined on regions regarded a

The partition of elliptic problems into subproblems is a very natural idea that is widely used in practice and which has been discussed in the engineering litera-ture for at least twenty years; see e.g. Prezemieniecki [18,19). Thus the modeling of an entire mechanical system can profitably be organized by discreti-zing the partial differential equations by finite elements on subregions. These tasks and the factorization of the resulting stiffness matrices for the subprob- lems can be assigned to different engineering groups and computer systems or processors with coordination required only at the interfaces between the sub-structures to assure matching of finite element triangulations and solutions. These ideas are particularly attractive for parallel computing and in the case when some of the substructures are identical or previously analyzed as in the case when a simulation is repeated after the redesign or damage of one or a few of the substructures. The final phase, in which the interaction is accounted for, does not lend itself equally well to parallel computing and it also represents a significant fraction of the total computational work even on a sequential computer.

New York University Page 1 Dec 31, 1984

Page 2 of 14

ITERA...