Multigrid principles

John Millar, John C. Bancroft

Multigrid methods are used to numerically solve discrete differential equations. The method is far faster than any other direct or iterative solving method (O(N) vs. O(N3)). Multigrid methods work by decomposing a problem into separate length scales, and using an iterative solver method that optimizes error reduction for that length scale, rather than globally. For multigrid to work, several sub-routines must be developed to pass the data from coarse grid to fine grid (interpolation), from fine grid to coarse grid (restriction), and correction of the error at each grid interval (smoothing). While used frequently in areas such as fluid dynamics, it has not yet been seen frequently in literature concerning seismic inversion or modelling. The approach used here is to develop the basic ideas that form the basis of multigrid applications.