×

zbMATH — the first resource for mathematics

Black-box learning of multigrid parameters. (English) Zbl 1440.65265
Summary: This paper studies the optimality of the restriction and prolongation operators in the geometric multigrid method (GMG). GMG is used in solving discretized partial differential equation (PDE) and it relies greatly on the restriction and prolongation operators. Many methods to find these operators were proposed, but most of them have limited optimality proofs. To study their optimality we introduce stochastic convergence functional, which estimates the spectral radius of the iteration matrix for given GMG parameters. We implement the GMG method in a modern machine learning framework that can automatically compute the gradients of the introduced convergence functional with respect to restriction and prolongation operators. Therefore, we can minimize the proposed functional starting from some initial parameters and get better ones after some iterations of stochastic gradient descent. To illustrate the performance of the proposed approach, we carry out experiments on the discretized Poisson equation, Helmholtz equation and singularly perturbed convection-diffusion equation and demonstrate that proposed approach gives operators, which lead to faster convergence.

MSC:
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65N06 Finite difference methods for boundary value problems involving PDEs
65K10 Numerical optimization and variational techniques
68T05 Learning and adaptive systems in artificial intelligence
62L20 Stochastic approximation
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Hackbusch, W., Multi-grid Methods and Applications, Vol. 4 (2013), Springer Science & Business Media
[2] Briggs, W. L.; Henson, V. E.; McCormick, S. F., A Multigrid Tutorial (2000), SIAM · Zbl 0958.65128
[3] Nesterov, Y.; Protasov, V. Y., Optimizing the spectral radius, SIAM J. Matrix Anal. Appl., 34, 3, 999-1013 (2013) · Zbl 1282.15029
[4] Kozyakin, V., On accuracy of approximation of the spectral radius by the Gelfand formula, Linear Algebra Appl., 431, 11, 2134-2141 (2009) · Zbl 1177.15012
[5] D. Maclaurin, D. Duvenaud, R.P. Adams, Autograd: Effortless gradients in numpy, in: ICML 2015 AutoML Workshop, 2015.
[6] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, et al. TensorFlow: A system for large-scale machine learning, in: OSDI, vol. 16, 2016, pp. 265-283.
[7] Theano Development Team, V., Theano: A Python framework for fast computation of mathematical expressions (2016), arXiv e-prints http://abs/1605.02688
[8] Paszke, A.; Gross, S.; Chintala, S.; Chanan, G.; Yang, E.; DeVito, Z.; Lin, Z.; Desmaison, A.; Antiga, L.; Lerer, A., Automatic differentiation in pytorch (2017)
[9] Baydin, A. G.; Pearlmutter, B. A.; Radul, A. A.; Siskind, J. M., Automatic differentiation in machine learning: a survey, J. Mach. Learn. Res., 18, 153 (2018) · Zbl 06982909
[10] Watson, L. T.; Haftka, R. T., Modern homotopy methods in optimization, Comput. Methods Appl. Mech. Engrg., 74, 3, 289-305 (1989) · Zbl 0693.65046
[11] Trottenberg, U.; Oosterlee, C. W.; Schuller, A., Multigrid (2000), Academic press
[12] Ruge, J. W.; Stüben, K., Algebraic multigrid, Multigrid Methods, 3, 13, 73-130 (1987)
[13] W.N. Bell, L.N. Olson, J.B. Schroder, PyAMG: Algebraic multigrid solvers in Python v3.0, 2015, https://github.com/pyamg/pyamg. Release 3.2.
[14] Olshanskii, M. A.; Tyrtyshnikov, E. E., Iterative Methods for Linear Systems: Theory and Applications (2014), SIAM · Zbl 1320.65050
[15] Nesterov, Y., Smoothing technique and its applications in semidefinite optimization, Math. Program., 110, 2, 245-259 (2007) · Zbl 1126.90058
[16] Avron, H.; Toledo, S., Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix, J. ACM, 58, 2, 8 (2011) · Zbl 1327.68331
[17] Hutchinson, M. F., A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines, Comm. Statist. Simulation Comput., 19, 2, 433-450 (1990) · Zbl 0718.62058
[18] Baur, W.; Strassen, V., The complexity of partial derivatives, Theor. Comput. Sci., 22, 3, 317-330 (1983) · Zbl 0498.68028
[19] Yserentant, H., Old and new convergence proofs for multigrid methods, Acta Numer., 2, 285-326 (1993) · Zbl 0788.65108
[20] Hemker, P., On the order of prolongations and restrictions in multigrid procedures, J. Comput. Appl. Math., 32, 3, 423-429 (1990) · Zbl 0717.65098
[21] Xu, J., The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids, Computing, 56, 3, 215-235 (1996) · Zbl 0857.65129
[22] De Zeeuw, P. M., Matrix-dependent prolongations and restrictions in a blackbox multigrid solver, J. Comput. Appl. Math., 33, 1, 1-27 (1990) · Zbl 0717.65099
[23] Dendy, J., Black box multigrid, J. Comput. Phys., 48, 3, 366-386 (1982) · Zbl 0495.65047
[24] Stüben, K., A review of algebraic multigrid, J. Comput. Appl. Math., 128, 1, 281-309 (2001) · Zbl 0979.65111
[25] Brezina, M.; Falgout, R.; MacLachlan, S.; Manteuffel, T.; McCormick, S.; Ruge, J., Adaptive algebraic multigrid, SIAM J. Sci. Comput., 27, 4, 1261-1286 (2006) · Zbl 1100.65025
[26] Brezina, M.; Falgout, R.; MacLachlan, S.; Manteuffel, T.; McCormick, S.; Ruge, J., Adaptive smoothed aggregation \(( \alpha\) SA), SIAM J. Sci. Comput., 25, 6, 1896-1920 (2004) · Zbl 1061.65135
[27] Olson, L. N.; Schroder, J. B.; Tuminaro, R. S., A general interpolation strategy for algebraic multigrid using energy minimization, SIAM J. Sci. Comput., 33, 2, 966-991 (2011) · Zbl 1233.65096
[28] Brandt, A.; Brannick, J.; Kahl, K.; Livshits, I., Bootstrap AMG, SIAM J. Sci. Comput., 33, 2, 612-632 (2011) · Zbl 1227.65120
[29] Oosterlee, C. W.; Wienands, R., A genetic search for optimal multigrid components within a Fourier analysis setting, SIAM J. Sci. Comput., 24, 3, 924-944 (2003) · Zbl 1035.65151
[30] Stolk, C. C.; Ahmed, M.; Bhowmik, S. K., A multigrid method for the Helmholtz equation with optimized coarse grid corrections, SIAM J. Sci. Comput., 36, 6, A2819-A2841 (2014) · Zbl 1310.65157
[31] Livshits, I., A scalable multigrid method for solving indefinite Helmholtz equations with constant wave numbers, Numer. Linear Algebra Appl., 21, 2, 177-193 (2014) · Zbl 1340.65299
[32] Khelifi, S. C.; Méchitoua, N.; Hülsemann, F.; Magoulès, F., A hybrid multigrid method for convection-diffusion problems, J. Comput. Appl. Math., 259, 711-719 (2014) · Zbl 1314.65156
[33] Dai, R.; Wang, Y.; Zhang, J., Fast and high accuracy multiscale multigrid method with multiple coarse grid updating strategy for the 3D convection-diffusion equation, Comput. Math. Appl., 66, 4, 542-559 (2013) · Zbl 1360.65259
[34] Grasedyck, L.; Wang, L.; Xu, J., A nearly optimal multigrid method for general unstructured grids, Numer. Math., 134, 3, 637-666 (2016) · Zbl 1356.65241
[35] Mengi, E.; Yildirim, E. A.; Kiliç, M., Numerical optimization of eigenvalues of Hermitian matrix functions, SIAM J. Matrix Anal. Appl., 35, 2, 699-724 (2014) · Zbl 1307.65043
[36] Kressner, D.; Vandereycken, B., Subspace methods for computing the pseudospectral abscissa and the stability radius, SIAM J. Matrix Anal. Appl., 35, 1, 292-313 (2014) · Zbl 1306.65187
[37] Greenfeld, D.; Galun, M.; Basri, R.; Yavneh, I.; Kimmel, R., Learning to optimize multigrid PDE solvers, (International Conference on Machine Learning (2019)), 2415-2423
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.