Jonas Thies
Centre for Interdisciplinary Mathematics
Department of Mathematics
Uppsala University
Fast algorithms for the solution of linear systems are often based on the idea of
approximating the solution on various spatial scales and combining these `levels'
in an iterative procedure. Such methods are used extensively for the Poisson equation (multigrid)
and the Maxwell equations (fast multipole method), where they ideally yield linear computational complexity
in the number of unknowns.
Presently there is no such algorithm for linear systems involving so-called saddlepoint matrices. Such
matrices arise, for instance, after spatial discretization of the (Navier-)Stokes equations in CFD or in
power network simulations.
As a first step towards a robust multilevel algorithm we present a two-level method that leads to grid independent convergence and preserves the structure of the original system so that it can in principle be applied recursively. We sketch a proof of convergence and demonstrate the method's performance on some highly indefinite matrices from a structured grid Navier-Stokes simulation. Some generalizations of the method to different grids, coordinate systems and equations are discussed.