|
Organizers |
Comparative Analysis of Marching Algorithms for Separable Elliptic Problems
by
Gergana Iv. Bencheva
Central Laboratory of Parallel Processing, Bulgarian Academy of Sciences
After discretization of separable elliptic boundary value problems on rectangular domains, linear algebraic systems with special block banded structure are obtained. The fast elliptic solvers are highly efficient algorithms for direct solution of such discrete problems, and the so called marching algorithms is one class of them.
Standard marching algorithm (MA) and Generalized marching algorithm (GMA) for 2D problems discretized on a rectangular n×m grid are considered. The related numerical stability and computational complexity are theoretically and experimentally compared. The standard marching algorithm is optimal in sense that its computational cost depends linearly on the dimension of the system, namely the number of arithmetic operations for its implementation is of order NMA=O(nm). Unfortunately MA is unstable and hence is applicable for sufficiently small problems, or more generally for m << n. The GMA is a stabilized version of the MA obtained by limiting the size of the marching steps and using the incomplete solution technique for problems with sparse right-hand sides. The total cost of the resulting algorithm, in the case when m=n, n+1=p(k+1), p, k in Z, is of order NGMA=O(n2 log p + n2). Results of performed numerical experiments confirm the theoretical estimates.
Apart from separable elliptic problems in a single rectangular domain, the development of fast elliptic solvers is strongly motivated by their potential application to the construction of efficient preconditioners for iterative solution of more general problems on more general domains and meshes. In particular, this study is focussed on a further implementation of the considered marching algorithms into the framework of domain decomposition and domain embedding methods.
Date received: January 28, 2000
Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caeb-29.