Rapid Solution of Finite Element Equations on Locally Refined Grids by Multi-Level Methods

摘要

This thesis is concerned with the use of multi-level methods to solve the linear systems arising from finite element discretizations of elliptic equations. In all, three multi-level methods are considered. The first of these is applicable only to quasi-uniform grids, but is simpler than other algorithms considered in previous theoretical work. The other two algorithms are applicable to both quasi-uniform grids, and locally refined grids, those grids on which the size of the largest and smallest elements many differ by an arbitrarily large factor. All three algorithms are asymptotically optimal, producing good solutions in O(N) operations on a finite element grid with N elements. These asymptotically optimal complexity bounds for the last two algorithms are the first such bounds for multi-level methods on locally refined grids. One of these algorithms achieves this O(N) complexity bound under weaker than expected conditions on the dimensions of the finite element spaces used by the algorithm.