Efficient algorithms for wave problems

Wave phenomena manifest in nature as electromagnetic waves, acoustic waves, and gravitational waves among others. Their descriptions as partial differential equations in electromagnetics, acoustics, and fluid dynamics are ubiquitous in science and engineering. Having numerical methods to solve these problems efficiently is therefore of great importance and value to domains such as aerospace engineering, geophysics, and civil engineering. Wave problems are characterized by the finite speeds at which waves propagate and present a series of challenges for the numerical methods aimed at solving them. This dissertation is concerned with the development and analysis of numerical algorithms for solving wave problems efficiently using a computer. It contains two parts: The first part is concerned with sparse linear systems which stem from discretizations of such problems. An approximate direct solver is developed, which can be computed and applied in quasilinear complexity. As such, it can also be used as a preconditioner to accelerate the computation of solutions using iterative methods. This direct solver is based on structured Gaussian elimination, using a nested dissection reordering and the compression of dense, intermediate matrices using rank structured matrix formats. We motivate the use of these formats and demonstrate their usefulness in our algorithm. The viability of the method is then verified using a variety of numerical experiments. These confirm the quasilinear complexity and the applicability of the method. The second part focuses on the solution of the shallow water equations using the discontinuous Galerkin method. These equations are used to model tsunamis, storm surges, and weather phenomena. We aim to model large-scale tsunami events, as would be required for the development of an early-warning system. This necessitates the development of a well-balanced numerical scheme, which is efficient, flexible, and robust. We analyze the well-balanced property in the context of discontinuous Galerkin methods and how it can be obtained. Another problem that arises with the shallow water equations is the presence of dry areas. We introduce methods to handle these in a well-balanced, and physically consistent manner. The resulting method is validated using tests in one dimension, as well as simulations on the surface of the Earth. The latter are compared to real-world data obtained from buoys and satellites, which demonstrate the applicability and accuracy of our method