Browse Prior Art Database

Optimal Iterative Refinement Methods

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

Publishing Venue

Software Patent Institute

Related People

Olof Widlund: AUTHOR [+3]

Abstract

We consider the solution of the linear systems of algebraic equations which arise from elliptic finite element problems defused on composite meshes. Such problems can systematically be built up by introducing a basic finite element approximation on the entire region and then repeatedly selecting subregions, and subregions of subregions, where the finite element model is further refined in order to gain higher accuracy. We consider conjugate gradient algorithms, and other acceleration procedures, where, in each iteration, problems representing finite element models on the original region and the subregions prior to further refinement are solved. We can therefore use solvers for problems with uniform or relatively uniform mesh sizes, while the composite mesh can be strongly graded. In this contribution to the theory, we report on new results recently obtained in joint work with Maksymilian Dryja. We use a basic mathematical frame work recently introduced in a study of a variant of Schwarz' alternating algorithm. We establish that several fast methods can be devised which are optimal in the sense that the number of iterations required to reach a certain tolerance is independent of the mesh size as well as the number of refinement levels. This work is also tech-nically quite closely related to previous work on iterative substructuring methods, which are domain decomposition algorithms using non-overlapping subregions.

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

Page 1 of 15

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Optimal Iterative Refinement Methods

by Olof Widlund

Ultracomputer Note #146 August, 1988 This work was supported in part by the National Science Foundation under Grant NSF-CCR-9703768 and, in part by the U.S. Department of Energy under contract DE-AC02..76ER03077-V at the Courant Mathematics and Computing Laboratory.

* This report was prepared for the proceedings of the Second International Symposium on Domain Decomposi-tion, which was held at UCLA, January 14-16, 1988. Optimal Iterative Refinement Methods

Olof Widlund

Courant Institute of Mathematical Sciences 251 Mercer Street New York, NY 10012

ABSTRACT

We consider the solution of the linear systems of algebraic equations which arise from elliptic finite element problems defused on composite meshes. Such problems can systematically be built up by introducing a basic finite element approximation on the entire region and then repeatedly selecting subregions, and subregions of subregions, where the finite element model is further refined in order to gain higher accuracy. We consider conjugate gradient algorithms, and other acceleration procedures, where, in each iteration, problems representing finite element models on the original region and the subregions prior to further refinement are solved. We can therefore use solvers for problems with uniform or relatively uniform mesh sizes, while the composite mesh can be strongly graded. In this contribution to the theory, we report on new results recently obtained in joint work with Maksymilian Dryja. We use a basic mathematical frame work recently introduced in a study of a variant of Schwarz' alternating algorithm. We establish that several fast methods can be devised which are optimal in the sense that the number of iterations required to reach a certain tolerance is independent of the mesh size as well as the number of refinement levels. This work is also tech-nically quite closely related to previous work on iterative substructuring methods, which are domain decomposition algorithms using non-overlapping subregions.

1. Introduction.

In this paper, we consider the solution of the large linear systems of algebraic equations which arise when working with elliptic finite element approximations on composite meshes. 1n this contribution to the theory, we report on new results recently obtained in joint work with Maksymilian Dryja. Finite element models on composite meshes can systematically be built up inside a frame work of conforming finite elements; cf. Ciarlet [3]. We do so to be able to use a number of technical tools which are available primarily in the conforming case. We begin by introducing a basic finite element approximation on the entire region and we then repeatedly select subregions, and subregions of subregions, where the finite element model is further refined. We solve the resulting linear system by using an iterative method such as the conjugate

New York...