Abstract of Doctoral Dissertation

Ivan Dimov Lirkov

The doctoral dissertation "Circulant block factorization of elliptic problems of second order" (scientific advisor Dr. Svetozar Margenov - Bulgarian Academy of Sciences) is devoted to the problem of development and study of the convergence of the preconditioners based on circulant approximation of a given matrix applied to various partial differential equations. The main results in the thesis are structured in four chapters. The considered methods and algorithms are presented and grounded in the first three chapters where the theoretical analysis of convergence and the theoretical estimates are proved. The parallel efficiency of the algorithms is studied in the fourth chapter and estimations of speed-up and parallel efficiency are obtained. Numerical results for several model large-scale problems are also presented.

Chapter 1:

The use of circulant preconditioners for the solution of elliptic problems is analysed. Finite element method is applied and spline elements are used in the discretization. It is proven that circulant preconditioners can be constructed such that the relative condition number of the preconditioned system can be reduced from $\kappa=O(N)$ to $\kappa\le 60\sqrt{N}$ where N is size of the discrete problem.

Chapter 2:

New circulant block-factorization (CBF) preconditioners are introduced and studied. The general approach is first formulated for the case of block tridiagonal sparse matrices. Then estimates of the relative condition number for a model Dirichlet boundary value problem are derived in the form $\kappa\le 4\sqrt{N}$ . In the case of y-periodic problems the CBF preconditioner is shown to give an optimal convergence rate. Finally, using a proper embedding of the original Dirichlet boundary value problem to a y-periodic one, a preconditioner of optimal convergence rate for the general case is obtained. An application of the CBF preconditioners for a Dirichlet boundary value problem in L-shaped domain is studied. Various numerical tests that demonstrate the features of the CBF preconditioners are presented.

Chapter 3:

An estimate of the relative condition number for a model anisotropic Dirichlet boundary value problem is derived. This is one of the important benchmark problems for the robustness of the iterative methods. Here we consider problems with a fixed direction of dominating anisotropy and derive an exact relative condition number estimate $\kappa<\sqrt{2}\left(\sqrt{N}+2\right)$ . Various numerical tests demonstrating the behavior of the CBF preconditioners for anisotropic problems are presented.

Chapter 4:

This chapter contains results for parallel properties of the proposed in the previous chapters algorithms and their implementation on different parallel architectures. The parallel numerical solution of large scale elliptic boundary value problems is discussed. We analyze the parallel complexity of the circulant preconditioners when solving elliptic problems by preconditioned conjugate gradient method. Estimations for speed-up and parallel efficiency for different models of computer architecture are obtained. The efficiency of considered algorithm on various parallel architecture models is compared. Numerical experiments for a large number test problems are described and their results analyzed.