Modulus-Based Cascadic Multigrid Method for Quasi-variational Inequality Problems

Abstract

We propose the modulus-based cascadic multigrid (MCMG) method and the modulus-based economical cascadic multigrid method for solving the quasi-variational inequalities problem. The modulus-based matrix splitting iterative method is adopted as a smoother, which can accelerate the convergence of the new methods. We also give the convergence analysis of these methods. Finally, some numerical experiments confirm the theoretical analysis and show that the new methods can achieve high efficiency and lower costs simultaneously.

Keywords

Quasi-variational inequality / Modulus-based cascadic multigrid (MCMG) method / Modulus-based matrix splitting iteration method / Convergence / 65K15 / 65N55

References

[1] BaiZ-Z. Modulus-based matrix splitting iteration methods for linear complementarity problems. Numer. Linear Algebra Appl., 2010, 17(6): 917-933.

[2] BaiZ-Z, EvansDJ. Matrix multisplitting relaxation methods for linear complementarity problems. Int. J. Comput. Math., 1997, 63: 309-326.

[3] BaiZ-Z, ZhangL-L. Modulus-based synchronous two-stage multisplitting iteration methods for linear complementarity problems. Numer. Algorithms, 2013, 62(1): 59-77.

[4] BaiZ-Z, ZhangL-L. Modulus-based synchronous multisplitting iteration methods for linear complementarity problems. Numer. Linear Algebra Appl., 2013, 20(3): 425-439.

[5] BaiZ-Z, ZhangL-L. Modulus-based multigrid methods for linear complementarity problems. Numer. Linear Algebra Appl., 2017, 246. e2105

[6] Blum, H., Braess, D., Suttmeier, F.: A cascadic multigrid algorithm for variational inequalities. Comput. Vis. Sci. 7(3/4), 153–157 (2004). https://doi.org/10.1007/s00791-004-0134-3

[7] BornemannFA, DeuflhardP. The cascadic multigrid method for elliptic problems. Numer. Math., 1996, 75(2): 135-152.

[8] Bornemann, F.A., Krause, R.: Classical and cascades multigrid-methodogical comparison. In: Bjorstad, P., Esped-AI, M., Keys, D. (eds.) Proceedings of the 9th International Conference on Domain Decomposition. Wiley and Sons, Hoboken (1998)

[9] BrandtA, CryerC. Multigrid algorithms for the solution of linear complementarity problems arising from free boundary problems. SIAM J. Sci. Stat. Comput., 2006, 4(4): 655-684.

[10] ChenC-M, HuH-L, XieZ-Q, LiC-L. Analysis of extrapolation cascadic multigrid method (EXCMG). Sci. China, 2008, 51(8): 1349-1360.

[11] Chen, C.-M., Hu, H.-L., Xie, Z.-Q., Li, C.-L.: $L^2$-error of extrapolation cascadic multigrid (EXCMG). Acta Math. Sci. 29(3), 539–551 (2009). https://doi.org/10.1016/S0252-9602(09)60052-7

[12] ChenC-M , XieZ-Q, LiC-L, HuH-L. Study of a new extrapolation multigrid method. J. Nat. Sci. Hunan Norm. Univer., 2007, 30(2): 1-5

[13] ChenJ-L, ChenX-HSpecial Matrix, 2001, Beijing. Tsinghua University Press.

[14] CottleR, PangJ-S, StoneRThe Linear Complementarity Problem, 2009, Philadelphia. Society for Industrial and Applied Mathematics.

[15] FerrisM, PangJ-S. Engineering and economic applications of complementarity problems. SIAM Rev., 1997, 394669.

[16] GlowinskR, LionsJ, TremolieersRNumerieal Analysis of Variational Inequalities, 2011, Amsterdam. Elsevier Science.

[17] HongJ-T, LiC-L. Modulus-based matrix splitting iteration methods for a class of implicit complementarity problems. Numer. Linear Algebra Appl., 2016, 23(4): 629-641.

[18] Li, C.-L.: Some new methods for variational inequalities and complementarity problems. PhD Thesis, Hunan University, Changsha (2004)

[19] LiC-L, HongJ-T. Modulus-based synchronous multisplitting iteration methods for an implicit complementarity problem. East Asian J. Appl. Math., 2017, 7(2): 363-375.

[20] Ma, J.: Multigrid method for the second order elliptic variational inequalities. Master’s Thesis, Hunan University, Changsha (2001)

[21] MandelJ. A multilevel iterative method for symmetric, positive definite linear complementarity problems. Appl. Math. Optim., 1984, 11(1): 77-95.

[22] NoorM. Linear quasi-complementarity problem. Utilitas Math., 1985, 27(5): 249-260

[23] NoorM. The quasi-complementarity problem. J. Math. Anal. Appl., 1988, 130(2): 344-353.

[24] NoorM. Fixed point approach for complementarity problems. J. Math. Anal. Appl., 1988, 133(2): 437-448.

[25] Pang, J.-S.: The Implicit Complementarity Problem. Academic Press, San Diego (1981). https://doi.org/10.1016/B978-0-12-468662-5.50022-7

[26] ShiZ-C, XuX-J. Cascadic multigrid method for elliptic problems. East West J. Numer. Math., 1999, 7(3): 199-209

[27] ShiZ-C, XuX-J. A new cascadic multigrid. Sci. China Ser. A-Math., 2001, 44(1): 21-30.

[28] ShiZ-C, XuX-J, HuangY-Q. Economical cascadic multigrid method (ECMG). Sci. China Ser. A-Math., 2007, 50(12): 1765-1780.

[29] SunLi, HuangY-M. A modulus-based multigrid method for image retinex. Appl. Numer. Math., 2021, 164: 199-210.

[30] WangL-H, XuX-JMathematical Foundation of Finite Element Method, 2004, Beijing. Science Press.

[31] WangY, LiC-L. A modulus-based cascadic multigrid method for linear complementarity problem. J. Guilin Univ. Electron. Technol., 2016, 2: 151-153

[32] WangY, LiC-L. A modulus-based cascadic multigrid method for elliptic variational inequality problems. Numer. Algorithms, 2022, 90(4): 1777-1791.

[33] WangY, YinJ-F, DouQ-Y, LiR. Two-step modulus-based matrix splitting iteration methods for a class of implicit complementarity problems. Numer. Math., 2019, 12(3): 867-883.

[34] Yuan, Q.: Implicit complementarity problem. Master’s Thesis. Nanjing University of Aeronautics and Astronautics, Nanjing (2002)

[35] YuanQ, YinH-Y. Minimization deformation of implicit complementarity problem and its stability point. J. Comput. Math., 2009, 31: 11-18

[36] ZengJ-P, MaJ-T. A cascadic multigrid method for a kind of one-dimensional elliptic variational inequality. J. Hunan Univer. (Nat. Sci.), 2001, 5: 1-5

[37] ZhanW-P, ZhouS-Z. Iterative method for a class of quasi-complementary problems. Acta Math. Appl., 2000, 23(4): 551-556

[38] ZhangL-L. A modulus-based multigrid method for nonlinear complementarity problems with application to free boundary problems with nonlinear source terms. Appl. Math. Comput., 2021, 399. 126015

[39] ZhangL-L. On AMSOR smoother in modulus-based multigrid method for linear complementarity problems. Acta Math. Appl. Sin., 2021, 44(1): 93-104.

[40] ZhangL-L, RenZ-R. A modified modulus-based multigrid method for linear complementarity problems arising from free boundary problems. Appl. Numer. Math., 2021, 164: 89-100.

[41] ZhaoJ, VollebregtE, OosterleeC. A full multigrid method for linear complementarity problems arising from elastic normal contact problems. Math. Model. Anal., 2014, 19(2): 216-240.

[42] ZhengN, YinJ-F. Convergence of accelerated modulus-based matrix splitting iteration methods for linear complementarity problem with an $H_+$-matrix. J. Comput. Appl. Math., 2014, 260: 281-293.

[43] Zhou, S.-Z., Zhan, W.-P.: Solutions of a class of Bellman equation discrete problems. Syst. Sci. Math. 22(4), 385–391 (2002)

Funding

Natural Science Foundation of China(12161027)

Guangxi Natural Science Foundation(2020GXNSFAA159143)

Science and Technology Project of Guangxi(AD23023002)

RIGHTS & PERMISSIONS

Shanghai University