Numerical Methods for MFC CDT
Introduction
This book introduces the concepts needed for numerical modelling with climate applications in mind. These are the notes for the Numerical Methods course for the Mathematics for our Future Climate CDT.
For more detail, the most precise comparator would be (Durran 2010) which covers numerical methods for Geophysics. For high accuracy methods including spectral and finite element approaches the books of (Hesthaven 2017), (Hughes 2012), (Trefethen 1996) and (Boyd 2001) are all important and useful. For high speed flows where discontinuities matter the books of (LeVeque 2002), (LeVeque 1992) and (Toro 2013) are key texts.
An aside on computers
The numerical methods we use and the design of the computers that we run the simulations on are closely linked. Changes in computer design (increases in memory, the move to parallel computing) can change which algorithms are most efficient. Sometimes computer architecture is specifically designed around particular algorithmic problems (such as graphical processing units - GPUs). Therefore it is important to have a loose understanding of how different parts of the algorithm interact with the computer architecture.
Key steps
Ultimately we want the computer to do an arithmetic calculation, which is then repeated many (many!) times. A typical calculation would update a single value on a single point of a grid, where there may be multiple values on each of the many (many!) grid points. A computer will do a single calculation incredibly quickly, in one cycle, typically less than a nanosecond. However, in order to do the calculation the computer needs to know the values of the terms going in to the calculation. These will be stored in computer memory. If they are in cache memory then the values are “close” to the core doing the calculation and will be retrieved quickly (maybe 5-50 cycles). If they are in main memory then they will be retrieved more slowly (maybe 1,000 cycles). Main memory is much larger than cache memory, so only small calculations can use just the cache.
If we want to do extremely large calculations the the data will not fit in main memory of a single core or node. In this case we use parallel computing where the calculation is spread between different parts of a larger computer. In splitting the data this way we introduce artificial boundaries into the calculation, whose values need providing from somewhere. Communicating this data over the network is even slower again, taking maybe 100,000 cycles. The more parallel computing is needed, or the more values used in updating a single grid point, the more the communication cost increases.
Finally, we may want to store data permanently on disk, or read complex data from a large table on disk. This is slower again, taking at least 1,000,000 cycles or more for large amounts of data. Careful choices of which data is stored and how can significantly improve the efficiency of a code.
More precise numbers on the efficiency and latency of computational operations can be found online. However, for numerical methods it is one of many concerns that need balancing. This course covers a range of numerical methods, from simple finite difference methods, more complex finite element methods designed to work on complex domains, and the high accuracy spectral methods. Whilst the low accuracy of finite differences compared to spectral methods may make them seem like a poor choice in theory, their simplicity can make it easier to use them efficiently, as the limited amount of data needed improves cache locality and reduces communication. Most production codes are the result of careful consideration of the trade-offs, and practical measurement of code efficiency.