Efficient computation of shifted linear systems of equations with application to PDEs

[摘要] ENGLISH ABSTRACT: In several numerical approaches to PDEs shifted linear systems of the form (zI - A)x = b, need to be solved for several values of the complex scalar z. Often, these linear systemsare large and sparse. This thesis investigates efficient numerical methods for these systemsthat arise from a contour integral approximation to PDEs and compares these methodswith direct solvers.In the first part, we present three model PDEs and discuss numerical approaches to solvethem. We use the first problem to demonstrate computations with a dense matrix, thesecond problem to demonstrate computations with a sparse symmetric matrix and thethird problem for a sparse but nonsymmetric matrix. To solve the model PDEs numericallywe apply two space discrerization methods, namely the finite difference method and theChebyshev collocation method. The contour integral method mentioned above is used tointegrate with respect to the time variable.In the second part, we study a Hessenberg reduction method for solving shifted linearsystems with a dense matrix and present numerical comparison of it with the built-indirect linear system solver in SciPy. Since both are direct methods, in the absence ofroundoff errors, they give the same result. However, we find that the Hessenberg reductionmethod is more efficient in CPU-time than the direct solver. As application we solve aone-dimensional version of the heat equation.In the third part, we present efficient techniques for solving shifted systems with a sparsematrix by Krylov subspace methods. Because of their shift-invariance property, the Krylovmethods allow one to obtain approximate solutions for all values of the parameter, by generating a single approximation space. Krylov methods applied to the linear systems aregenerally slowly convergent and hence preconditioning is necessary to improve the convergence.The use of shift-invert preconditioning is discussed and numerical comparisons witha direct sparse solver are presented. As an application we solve a two-dimensional versionof the heat equation with and without a convection term. Our numerical experimentsshow that the preconditioned Krylov methods are efficient in both computational time andmemory space as compared to the direct sparse solver.

[发布机构] Stellenbosch University