AMCS 343 Fast Solvers for Large Systems of Equations

Solving systems of algebraic equations is a core task in the numerics of partial differential equations (PDE). After discretising the PDE with a grid method like finite volumes, finite elements or finite differences, we finally obtain a system of algebraic equations, which is typically sparse and very large. The largest systems currently solved contain up to 1012 unknowns. To solve such large sparse systems, specialised algorithms are necessary. Since these algorithms are in the core of a lot of simulation programs and all other parts are usually O(n), they are setting the final complexity of a simulation.

We introduce linear iterative methods and discuss their properties inparticular w.r.t. convergence and complexity issues. We then develop multi-grid methods and discuss their main properties. Issues of convergence and complexity are discussed in detail. We further analyse robustness for singularaly perturbed problems and generalise multi-grid methods to solving systems of PDE. We introduce multi-grid methods for non-linear and heterogenous problems and introduce Algebraic Multigrid Methods (AMG).