Domain decomposition and high order discretization of elliptic partial differential equations

Numerical solutions of partial differential equations (PDEs) resulting from problems in both the engineering and natural sciences result in solving large sparse linear systems Au = b. The construction of such linear systems and their solutions using either direct or iterative methods are topics of continuing research. The recent advent of parallel computer architectures has resulted in a search for good parallel algorithms to solve such systems, which in turn has led to a recent burgeoning of research into domain decomposition algorithms. Domain decomposition is a procedure which employs subdivision of the solution domain into smaller regions of convenient size or shape and, although such partitionings have proven to be quite effective on serial computers, they have proven to be even more effective on parallel computers.

Recent work in domain decomposition algorithms has largely been based on second order accurate discretization techniques. This dissertation describes an algorithm for the numerical solution of general two-dimensional linear elliptic partial differential equations with variable coefficients which employs both a high order accurate discretization and a Krylov subspace iterative solver in which a preconditioner is developed using domain decomposition. Most current research into such algorithms has been based on symmetric systems; however, variable PDE coefficients generally result in a nonsymmetric A, and less is known about the use of preconditioned Krylov subspace iterative methods for the solution of nonsymmetric systems.

The use of the high order accurate discretization together with a domain decomposition based preconditioner results in an iterative technique with both high accuracy and rapid convergence. Supporting theory for both the discretization and the preconditioned iterative solver is presented. Numerical results are given on a set of test problems of varying complexity demonstrating the robustness of the algorithm. It is shown that, if only second order accuracy is required, the algorithm becomes an extremely fast direct solver. Parallel performance of the algorithm is illustrated with results from a shared memory multiprocessor.