Parallel Algorithms for Separation of Variables and Sparse Matrices Factorization

Gergana Bencheva Ph.D. M.Sc.

Dec. 20, 2004, 2:30 p.m. HF 136

The appearance of parallel architectures and the recent progress in computational technologies has inspired quite a lot of interest in development of efficient parallel algorithms for solution of problems in almost all nowadays scientific areas. Presented dissertation is devoted to construction and analysis of parallel methods. Subject of investigations in the thesis are numerical methods for solution of large systems of linear algebraic equations obtained after discretization of a second order elliptic boundary value problems. Two approximation approaches are considered: a) by finite differences with five-point stencil for a separable problem; b) by rotated bilinear nonconforming finite elements (NFE) for a problem in a general form. The main results, obtained in the thesis, are constructive. They are presented in three chapters. A theoretical and experimental comparative analysis of five separable solvers is made in the first part. Namely, the attention is focused on the standard (SV) and the fast (FASV) algorithm for separation of variables as well as on the standard (SM) and two variants (GMF and GMS) of the generalized marching algorithm. The proposed original modification GMS of GMF simplifies the structure of the generalized marching algorithm and has advantages with respect to parallel implementation. An almost optimal separable preconditioner for anisotropic elliptic boundary value problems discretized by rotated bilinear NFE is proposed and investigated theoretically and experimentally. A characterization of the anisotropy coefficient influence on the efficiency of the preconditioner is obtained. The second part deals with parallel direct solvers. New parallel implementations of the algorithms FASV, GMF and GMS are proposed and a theoretical comparative analysis of their properties is derived. The third part is devoted to parallel iterative methods. A new parallel preconditioner for anisotropic elliptic boundary value problems, discretized by rotated bilinear NFE is proposed. The modified incomplete Cholesky factorization is applied to a locally constructed approximation of the stiffness matrix. Uniform estimates for the condition number are obtained with respect to the problem size and coefficient jumps. A characterization for the parallel efficiency of the constructed direct and iterative solvers is obtained for classes of distributed memory parallel computing systems. An experimental comparative analysis of the behaviour of each of the proposed parallel solvers on distributed systems with different characteristics is made.