Research on the application of multigrid method in the past 60 years

The multigrid method has the property of fast convergence, computational simplicity and robustness, therefore, it has been applied in various problems. We analyze the researches on the application of the multigrid method, and find that this method: (1) could be applied in many branches of physics; (2) mainly focuses on the problem of tomography in the field of image processing; (3) is generally applied in the problem of geological exploration in the field of geology; (4) has not been widely used yet in the field of finance.

Illustrations explain the paper; they do not show study data.

AI-generated illustration

↗ Enlarge

Multigrid Hierarchy ConceptClose ×

AI-generated conceptual illustration (A sequence of nested mathematical grids on a 2D plane). It explains the idea and does not show study data.

Open full-size image ↗

Introduction

Multigrid method is a one of the numerical methods for solving equations. It was first proposed by Fedorenko in 1961 to solve a poisson equation [1] . Because it has the characteristics of rapid convergence, low computational complexity and good stability, many scientists have applied this method to various problems in the field of physics, medicine, computer science and finance etc. . In order to learn the application of multigrid method more clearly and provide direction for further study in the future, this paper intends analyze the relevant researches on the application of multigrid method in field of physics, image processing, geology and finance.

Basic principle of multigrid method

The problem to be solved by the multigrid method usually can be transformed into a minimization problem of cost functional min ( ) u Ju , that is, a problem of finding the solution u which makes the cost functional minimum. Before the implementation of the multigrid method, the domain  of u is divided into a sequence of grid levels: 01 ,, K    , where K  denotes the finest mesh hierarchy, 0  denotes the coarsest one. The symbols in the following with the subscript k indicate that they are under the grid level k.

Additionally, the relationship of the step sizes between adjacent grid levels is that the step size of the coarser is twice that of the finer grid. Next, the multigrid algorithm is stated in detail as follows:

1) Initialization. Let 0 k u be an initial approximation at resolution k. If k=0, solve and return.

2) Pre-optimization. Apply 1  iterations of an optimization algorithm () k  to the problem at resolution k.

(

 iterations of an optimization algorithm () k  to the problem at resolution k.

In the steps above, the symbols

 are respectively restriction operator and prolongation operator, which need to be prescribed before the multigrid procedure. Moreover, 1   and 2   correspond to V-cycle and W-cycle multigrid method, which are two most common types of the multigrid method [2] . As the description of the multigrid method above, the sampling points are less on a coarser grid, resulting that the computational complexity is much simpler than that on the fine grid. Consequently, this multigrid strategy allows us to obtain an approximation efficiently comparing with singlegrid methods.

The application of the multigrid method

We take "multigrid" as the keyword to search for literatures on the websites of China National Knowledge Infrastructure, Baidu Academic Search, Google Academic Search and the websites of web of SCI, and then selected the literatures on the application of multigrid method in recent 60 years, and got 62 articles. Based on the selected researches, it can be found that the applications of multigrid are mainly concentrated in the field of physics, geology, image processing and finance. Then these researches are analyzed in this section.

Applications of multigrid method in the field of physics

Since the multigrid method was first proposed by Fedorenko, it has been immediately used to solve the poisson equation in a square region, that is, an equation describing the relationship between potential and charge density [1] . Then, the multigrid method has been widely applied in the branches of physics, such as optics, acoustics, hydrodynamics and thermodynamics [3][4][5][6][7][8][9][10][11][12][13][14][15][16][17][18][19][20][21][22] . Paola F. Antonietti et al. 2008 [4] presented a multigrid algorithm for the solution of the linear systems of equations stemming from the p-version of the Virtual Element discretization of a two-dimensional Poisson problem. Considered the time-dependent two-dimensional spacefractional diffusion equations which could model the anomalous diffusive systems with a V-cycle multigrid method [7] . Computed the ground state solution of Bose-Einstein condensations which belonged to the field of condensed matter physics by a multigrid method [8] . Besides, Sehar Iqbal and Paul Andries Zegeling solved a two-dimensional nonlinear boundary value problem which was strongly related to the well-known Gelfand-Bratu model emerged in nanotechnology, radioactive heat transfer, chemical reaction theory, elasticity theory, etc. [10] C. Nita and her group employed a multigrid scheme to DNS-based optimal control problem [16] . Due to 3D non-LTE radiative transfer problems are computationally demanding, Johan P. Bjørgen and Jorrit Leenaarts [18] implemented a non-linear multigrid and showed that multigrid can be employed in realistic problems with snapshots from 3D radiative magnetohydrodynamics simulation ns as input atmospheres. As a significant model measuring the flow positions and quantities in hydrodynamics, Navier-Stokes equations was tried to be solved by a structured overset grid method [20] . Wang Yajing et al. 2012 [22] attempted to estimate the particle size distribution by a multi-level Tikhonov regularization inversion method.

Applications of multigrid method in the field of image processing

Image processing refers to the technology of computer for images, including the aspects of image compression, enhancement and restoration, matching, description and recognition. In present, the multigrid method has been applied to image reconstruction, optical flow estimation, interpolation of missing image data, image segmentation, tomography, medical diagnosis etc. For instance, Liliana Borcea proposed a nonlinear multigrid approach for imaging the electrical conductivity and permittivity of a heterogeneous and isotropic body with a Neumann-to-Dirichlet map at the boundary [30] . The constructed images by multigrid method not only had a good contrast and the correct geometrical features, but also was stable in the presence of noisy data. Additionally, Samy Wu Fung and Zichao Di 2020 [31] developed a multigrid-based optimization framework to reduce the computational costs of large-scale ptychographic phase retrieval problem. For a waveform imaging described by a hyperbolic wave equation, Mika Takala et al. 2018 [32] presented a rigorous multigrid-based forward approach, The numercal results suggested that it allowed recovering the robust results and the computational procedure can be speeded up. In recent years, the application of multigrid method to the problem of tomography has attracted much attention, and there are many studies about it. Liisa-Ida Sorsa et al. 2020 [33] introduced and evaluates numerically a multigrid solver for non-linear tomographic radar imaging, and the results obtained suggested that the tomographic reconstruction quality could be improved. Cuiping Li et al. 2012 [34] studied the ultrasound tomography imaging in detecting breast cancer by the multigrid tomography technique. Seungseok Oh et al. 2006 [35] applied the a multigrid inversion method to iterative reconstruction for emission and transmission tomography.

Applications of multigrid method in the field of geology

Geology develops with the human demand for mineral resources such as oil, coal, metal and non-metal, as these are the fundamental source for human society. At the same time, as an important tool of resource exploration, seismic waves propagating underground can be measured or calculated by some means to reflect the underground structure, so that the mineral resources can be discovered. Therefore, the problem of geological exploration can often be transformed into a problem governed by wave equation. Due to the advantages of low computational complexity, multigrid method has been widely used in geological investigation and resource exploration [46][47][48][49][50][51][52][53][54] . In, Bhogeswara, R 1991 [47] Realistic had developed a variant of multigrid for the simulation of multiphase and multicomponent fluid flow in oil reservoirs which was computationally intensive, and the results obtained showed that the performance was comparable to current mainframe supercomputers [46] . Klaus Stüben 2003 [48] and his team introduced an algebraic multigrid for ground water flow and oil reservoir. M. Adil Sbai and A. Larabi 2021 [49] focused on a single groundwater flow solve and a pure advective transport solve with algebraic multigrid preconditioning. R.P.Hammersley et al. integrated an algebraic multigrid technique into a parallel reservoir simulation code and found that it performed well when solving for scalar solution to a system of ellipic equations. More recently, Steen Hørsholt et al. 2019 [50] presented a hierarchical multigrid method for oil production optimization of industry-scale the reservoir models. For tracking seismic reflections to identify horizons, Xinming Wu and Sergey Fomel 2018 [51] utilized the multigrid method that globally fit both local slopes and multigrid correlations of seismic traces [70] . Takumi Veda and Michael S. Zhdanov applied a multigrid approach for modeling of Multitransmitter electromagnetic data to speed up the process. Sun Q and Hu Y 2021 [53] employed the geometric multigrid method to borehole electromagnetic sensing and validated its performance as a potential fast solver for practical application.

Applications of multigrid method in the field of finance

The application of multigrid method in the field of finance, unlike the situation in mechanics, geophysics and image processing mentioned above, emerged relatively late. In the 1990s, multigrid techniques started to be used to the related problem of pricing and hedging financial derivatives. For example, Nigel Clarke and Kevin Parrott in 1999 [56] had developed multigrid solvers for pricing American equity options in a stochastic volatility framework [55] . To date, the application of multigrid method in the field of finance is not yet widespread. Only some researches on the typical financial problems were performed by the multigrid method, such as the problems about the option pricing. For instance, Markus Holtz provided a multigrid approach for the fast and accurate computation of American style option prices in the Black-Scholes framework and of their derivatives with respect to the underlying. Presented a multigrid iterative algorithm for solving a system of coupled free boundary problems for pricing American put options with regimeswitching [57] . Dong Han and Justin W. L. Wan proposed multigrid methods for solving the discrete algebraic equations arising from the discretization of the second order Hamilton-Jacobi-Bellman and Hamilton-Jacobi-Bellman-Isaacs equations which could discribe financial problems [58] . Fractional diffusion equations, as a model in computational finance, were solved by two computationally favourable variants of the proposed multigrid method [59] . Aicha Driouch and Hassan Al Moatassime dealt with the task of pricing European basket options in the presence of transaction costs by a nonlinear multigrid method [60,61] . Justin W. L. Wan 2019 [63] tried to solve the discrete partial integro-differential equations arising from pricing European options by using a fast multigrid method [62] . In order to improve the efficiency of the option pricing, Darae Jeong et al. 2013 [2] had approximately solved the two-dimensional Black-Scholes PDE by a multigrid method.

Conclusions

This paper has presented a brief overview of multigrid techniques and their applications to problems in several fundamental fleids including physics, image processing, geology and finance. By analyzing the researches in each fleid comprehensively, we now arrive at the following conclusions: 1. The application of multigrid method in the field of physics originated earliest, resulting that this method was not only applied in many branches of physics, but also deeply investigated and improved for specific physical problems in the process of implementation; 2. In the field of image processing, tomography is a very important problem for its non-invasive characteristics.

The research on the application of multigrid to tomography is a subject of great tremendous interest, and many related research have been made; 3. In the field of geology, multigrid method is mainly applied in the problem of geological exploration; 4. At present, the application of multigrid method in the field of finance is not widely applied yet, and it mainly focuses on several typical problems. Therefore, the multigrid method may have a wider applicability to the problems in the field of finance in the future.

1. Fedorenko RP. A Relaxation Method for Solving Elliptic Difference Equations. Zhurnal Vychislitel'noi Matematiki I Matematicheskoi Fiziki. 1961;1(5):922-927.
2. Jeong D, Li Y, Choi Y, Moon KS, Kim J. An Adaptive Multigrid Technique for Option Pricing under the BlackScholes model. Journal of the Korean Society for Industrial and Applied Mathematics. 2013;17(4):295306.
3. Thompson T, Chen K. A More Robust Multigrid Algorithm for Diffusion Type Registration Models. Journal of Computational and Applied Mathematics. 2019;361(C):502-527.
4. Antonietti PF, Mascotto L, Verani M. A Multigrid Algorithm for the p-version of the Virtual Element Method. ESAIM: Mathematical Modelling and Numerical Analysis. 2018;52(1):337-364.
5. Milyukova OY, Tishkin VF. A Multigrid Method for a Heat Equation with Discontinuous Coefficients with a Special Choice of Grids. Mathematical Models and Computer Simulations. 2016;8(2):118-128.
6. Kothari H, Krause R. A Multigrid Method for a Nitschebased Extended Finite Element Method. arXiv preprint arXiv: 1912. 00496, 2019.
7. Lin XL, Ng MK, Sun HW. A Multigrid Method for Linear Systems Arising from Time-dependent Twodimensional Space-fractional Diffusion Equations. Journal of Computational Physics. 2017;336:69-86.
8. Xie H, Xie M. A Multigrid Method for Ground State Solution of Bose-Einstein Condensates. Communications in Computational Physics. 2016;19(3):648-662.
9. Logutov OG. A Multigrid Methodology for Assimilation of Measurements into Regional Tidal Models. Ocean Dynamics. 2008;58(5):441-460.
10. Iqbal S, Zegeling PA. An Efficient Nonlinear Multigrid Scheme for 2D Boundary Value Problems. Applied Mathematics and Computation. 2020;372:124898.
11. Pan K, He D, Hu H. An Extrapolation Cascadic Multigrid Method Combined with a Fourth-order Compact Scheme for 3D Poisson Equation. Journal of Scientific Computing. 2017;70(3):1180-1203.
12. Zhang J, Cheng Y, Lu W, Briggs E, Ramirez-Cuesta AJ, Bernholc J. Large-scale Phonon Calculations Using the Real-space Multigrid Method. Journal of chemical theory and computation. 2019;15(12):6859-6864.
13. Fabien MS, Knepley MG, Mills RT, Rivière BM. Manycore Parallel Computing for a Hybridizable Discontinuous Galerkin Nested Multigrid Method. SIAM Journal on Scientific Computing. 2019;41(2):C73-C96.
14. Adavani SS, Biros G. Multigrid Algorithms for Inverse Problems with Linear Parabolic PDE Constraints. SIAM Journal on Scientific Computing. 2008;31(1):369-397.
15. Nita C, Vandewalle S, Meyers J. Multigrid Optimization for DNS-based Optimal Control in Turbulent Channel Flows. Journal of Computational Physics. 2018;366:1432.
16. Falgout RD, Manteuffel TA, O'Neill B, Schroder JB. Multigrid Reduction in Time for Nonlinear Parabolic Problems: A Case Study. SIAM Journal on Scientific Computing. 2017;39(5):S298-S322.
17. Bjørgen JP, Leenaarts J. Numerical Non-LTE 3D Radiative Transfer Using a Multigrid Method. Astronomy & Astrophysics. 2017;599:A118.
18. Ohashi K, Hino T, Kobayashi H, Onodera N, Sakamoto N. Development of a structured overset Navier-Stokes solver with a moving grid and full multigrid method. Journal of Marine Science and Technology. 2019;24(3):884-901.
19. Xu F, Huang Q. A Type of Cascadic Multigrid Method for Coupled Semi linear Elliptic Equations. Numerical Algorithms. 2020;83(2):485-510.
20. Wang YJ, Shen J, Zheng G, Liu W, Sun XM. Dynamic Light Scattering Inversion Combined with Tikhonov Regularization and Multigrid Technology. Optics and Precision Engineering. 2012;20(05):963-971.
21. Oh S, Bouman CA, Webb KJ. Multigrid Tomographic Inversion with Variable Resolution Data and Image Spaces. IEEE transactions on image processing. 2006;15(9):2805-2819.
22. Henn S, Witsch K. A Multigrid Approach for Minimizing a Nonlinear Functional for Digital Image Matching. Computing. 2000;64(4):339-348.
23. Abouelatta MA, Ward SA, Sayed AM, Mahmoud K, Lehtonen M, Darwish MM. Fast Corona Discharge Assessment Using FDM integrated With Full Multigrid Method in HVDC Transmission Lines Considering Wind Impact. Ieee Access. 2020;8:225872-225883.
24. Henn S, Witsch K. Iterative Multigrid Regularization Techniques for Image Matching. SIAM Journal on Scientific Computing. 2001;23(4):1077-1093.
25. Oh S, Milstein AB, Bouman CA, Webb K. Multigrid Algorithms for Optimization and Inverse Problems. In Computational Imaging. International Society for Optics and Photonics. 2003;5016:59-70.
26. Han H, Wang Z, Zhang Y. MultiScale Approach for Two-Dimensional Diffeomorphic Image Registration. Multiscale Modeling & Simulation. 2021;19(4):15381572.
27. Borcea L. A Nonlinear Multigrid for Imaging Electrical Conductivity and Permittivity at Low Frequency. Inverse Problems. 2001;17(2):329.
28. Fung SW, Wendy Z. Multigrid Optimization for Largescale Ptychographic Phase Retrieval. SIAM Journal on Imaging Sciences. 2020;13(1):214-233.
29. Takala M, Us D, Pursiainen S. Multigrid-based Inversion for Volumetric Radar Imaging with Asteroid Interior Reconstruction as a Potential Application. IEEE Transactions on Computational Imaging. 2018;4(2):228240.
30. Sorsa LI, Takala M, Eyraud C, Pursiainen S. A Timedomain Multigrid Solver with Higher-order Born approximation for Full-wave Radar Tomography of a Complex-shaped Target. IEEE Transactions on Computational Imaging. 2020;6:579-590.
31. Li C, Stewart A, Duric N. Multi-grid Tomographic Inversion for Breast Ultrasound Imaging. Medical Imaging: Ultrasonic Imaging, Tomography, and Therapy. International Society for Optics and Photonics. 2012;8320:229-237, 83200R.
32. Oh S, Bouman CA, Webb KJ. Multigrid Tomographic Inversion with Variable Resolution Data and Image Spaces. IEEE transactions on image processing. 2006;15(9):2805-2819.
33. Marlevi D, Kohr H, Buurlage JW, Gao B, Batenburg KJ, Colarieti-Tosti M. Multigrid Reconstruction in Tomographic Imaging. IEEE Transactions on Radiation and Plasma Medical Sciences. 2019;4(3):300-310.
34. Ye JC, Bouman CA, Webb KJ, Millane RP. Nonlinear Multigrid Algorithms for Bayesian Optical Diffusion Tomography. IEEE Transactions on Image Processing. 2001;10(6):909-922.
35. Henson VE, Limber MA, McCormick SF, Robinson BT. Multilevel Image Reconstruction with Natural Pixels. SIAM Journal on Scientific Computing. 1996;17(1):193216.
36. Oh S, Milstein AB, Bouman CA, Webb KJ. A General Framework for Nonlinear Multigrid Inversion. IEEE Transactions on image Processing. 2004;14(1):125-140.
37. O'Sullivan JA, Benac J. Alternating Minimization Multigrid Algorithms for Transmission Tomography Computational Imaging II. International Society for Optics and Photonics. 2004;5299:216-221.
38. Mémin E, Pérez P. Dense Estimation and Object-based Segmentation of the Optical Flow with Robust Techniques. IEEE Transactions on Image Processing. 1998;7(5):703-719.
39. Arigovindan M, Suhling M, Hunziker P, Unser M. Multigrid Image Reconstruction from Arbitrarily Spaced Samples. Proceedings. International Conference on Image Processing. IEEE. 2002;3:3-3.
40. Sharon E, Brandt A, Basri R. Fast Multiscale Image Segmentation. Proceedings IEEE Conference on Computer Vision and Pattern Recognition. CVPR 2000 (Cat. No. PR00662). IEEE. 2000;1:70-77.
41. Kimmel R, Yavneh I. An Algebraic Multigrid Approach for Image Analysis. SIAM Journal on Scientific Computing. 2003;24(4):1218-1231.
42. Henn S, Witsch K. A multigrid Approach for Minimizing a Nonlinear Functional for Digital Image Matching. Computing. 2000;64(4):339-348.
43. Bhogeswara R. Simulation of Numerically Intensive Multiphase Flow in Porous Media on Advanced Parallel Computers Using domain Decomposition and Multigrid Methods. Houston University, Texa, United States, 1991.
44. Stüben K, Delaney P, Chmakov S. Algebraic Multigrid (AMG) for Ground Water Flow and Oil Reservoir Simulation. Proceedings of the Conference MODFLOW and More: Understanding through Modeling, 2003, 1719.
45. Hørsholt S, Nick H, Jørgensen JB. A Hierarchical Multigrid Method for Oil Production Optimization. IFAC-Papers OnLine. 2019;52(1):492-497.
46. Wu X, Fomel S. Least-squares Horizons with Local Slopes and Multigrid Correlations. Geophysics. 2018;83(4):IM29-IM40.
47. Ueda T, Zhdanov MS. Fast Numerical Modeling of Multitransmitter Electromagnetic Data Using Multigrid Quasi-linear Approximation. IEEE Transactions on Geoscience and Remote sensing. 2006;44(6):1428-1434.
48. Sun Q, Hu Y. Fast Geometric Multigrid Preconditioned Finite-Difference Frequency-Domain Method for Borehole Electromagnetic Sensing. IEEE Geoscience and Remote Sensing Letters. 2021 Feb 2;19:1-4.
49. Woodward CS. A Newton-Krylov-multigrid Solver for Variably Saturated Flow Problems. WIT Transactions on Ecology and the Environment; 1970, p 24.
50. Clarke N, Parrott K. Multigrid for American Option Pricing with Stochastic Volatility. Applied Mathematical Finance. 1999;6(3):177-195.
51. Nwankwo C, Dai W. Multigrid Iterative Algorithms based on Compact Finite Difference Schemes and Hermite interpolation for Solving Regime Switching American Options. arXiv preprint arXiv 2008; c2020, 00925.
52. Han D, Wan JWL. Multigrid Methods for Second Order Hamilton--Jacobi--Bellman and Hamilton--Jacobi-- Bellman--Isaacs Equations. SIAM Journal on Scientific Computing. 2013;35(5):S323-S344.
53. Driouch A, Al-Moatassime H. Multigrid Method for a Two Dimensional Fully Nonlinear Black-Scholes Equation with a Nonlinear Volatility Function. J. Math. Study. 2020;53(3):247-264.
54. Driouch A, Al-Moatassime H. Multigrid Method for a Fully Nonlinear Black-Scholes Equation. Annals of the University of Craiova-Mathematics and Computer Science Series. 2020;47(1):25-34.
55. Wan JWL. Multigrid Method for Pricing European Options Under the CGMY Process. AIMS Mathematics. 2019;4(6):1745-1767.