No label defined (Q4936901)

One of the most important tasks in scientific computing is to solve systems of linear equations \[ Ax=b, \quad A\in \mathbb{C}^{N\times N}, \quad b\in \mathbb{C}^N. \tag{1} \] Such systems arise in many areas of science and engineering, often from discretizations of continuous problems. The coefficient matrix \(A\) typically has a special structure, and often most of its entries are zero. Such a matrix is called sparse. Originally, direct methods, in particular Gaussian elimination, have been used for solving (1). These methods are based on a factorization of \(A\). Since this requires \({\mathcal O}(N^3)\) floating point operations (flops), direct methods are only feasible if \(N\) is small. Furthermore, in many cases direct method can only partially take advantage of sparsity. The factorization of \(A\) might even lead to fill-in, which means that the computed factors have more nonzero entries than \(A\) itself. Hence, for large \(N\) direct methods ``are prohibitive both in terms of storage requirements and computing time''. To overcome the \({\mathcal O}(N^3)\) bottleneck and to exploit sparsity, dozens of iterative solution methods have been developed in the last two decades. Many of these methods are based on polynomials in \(A\), and are therefore called polynomial iterative methods (PIMs). These methods are the topic of this thesis. One of the main characteristics of PIMs is that for each step only a few matrix-vector products are required. The computational effort therefore potentially is \({\mathcal O}(N^2)\) flops, even \({\mathcal O}(N)\) if \(A\) has very few nonzero entries. Because the solution of very large sparse linear systems is of growing importance in a variety of applications, PIMs have been gaining more and more attention and popularity in recent years.