Mixed-precision explicit stabilized Runge-Kutta methods for single- and multi-scale differential equations. (English) Zbl 07540376
Summary: Mixed-precision algorithms combine low- and high-precision computations in order to benefit from the performance gains of reduced-precision without sacrificing accuracy. In this work, we design mixed-precision Runge-Kutta-Chebyshev (RKC) methods, where high precision is used for accuracy, and low precision for stability. Generally speaking, RKC methods are low-order explicit schemes with a stability domain growing quadratically with the number of function evaluations. For this reason, most of the computational effort is spent on stability rather than accuracy purposes. In this paper, we show that a naïve mixed-precision implementation of any Runge-Kutta scheme can harm the convergence order of the method and limit its accuracy, and we introduce a new class of mixed-precision RKC schemes that are instead unaffected by this limiting behavior. We present three mixed-precision schemes: a first- and a second-order RKC method, and a first-order multirate RKC scheme for multiscale problems. These schemes perform only the few function evaluations needed for accuracy (1 or 2 for first- and second-order methods respectively) in high precision, while the rest are performed in low precision. We prove that while these methods are essentially as cheap as their fully low-precision equivalent, they retain the stability and convergence order of their high-precision counterpart. Indeed, numerical experiments confirm that these schemes are as accurate as the corresponding high-precision method.
MSC:
| 65Lxx | Numerical methods for ordinary differential equations |
| 65Fxx | Numerical linear algebra |
| 65Mxx | Numerical methods for partial differential equations, initial value and time-dependent initial-boundary value problems |
Keywords:
explicit stabilized Runge-Kutta methods; mixed-precision computing; rounding errors; reduced precision; floating-point arithmetic; multirate methodsSoftware:
mctoolbox; hypre; PETSc; SyFi; RKC; NumPy; SciPy; M3RK; FEniCS; Python; IMPEX; Libchopping; CholQRReferences:
| [1] | Abdelfattah, A.; Anzt, H.; Boman, E. G.; Carson, E.; Cojean, T.; Dongarra, J.; Fox, A.; Gates, M.; Higham, N. J.; Li, X. S., A survey of numerical linear algebra methods utilizing mixed-precision arithmetic, Int. J. High Perform. Comput. Appl., 35, 344-369 (2021) |
| [2] | Abdulle, A., Fourth order Chebyshev methods with recurrence relation, SIAM J. Sci. Comput., 23, 2041-2054 (2002) · Zbl 1009.65048 |
| [3] | Abdulle, A.; Almuslimani, I.; Vilmart, G., Optimal explicit stabilized integrator of weak order one for stiff and ergodic stochastic differential equations, SIAM J. Uncertain. Quantificat., 6, 937-964 (2018) · Zbl 1392.65013 |
| [4] | Abdulle, A.; Grote, M. J.; Rosilho de Souza, G., Explicit stabilized multirate method for stiff differential equations, Math. Comput. (2022), in press · Zbl 1500.65034 |
| [5] | Abdulle, A.; Li, T., S-ROCK methods for stiff Itô SDEs, Commun. Math. Sci., 6, 845-868 (2008) · Zbl 1162.60330 |
| [6] | Abdulle, A.; Medovikov, A. A., Second order Chebyshev methods based on orthogonal polynomials, Numer. Math., 18, 1-18 (2001) · Zbl 0997.65094 |
| [7] | Abdulle, A.; Rosilho de Souza, G., Explicit stabilized multirate method for stiff stochastic differential equations, SIAM J. Sci. Comput. (2022), in press · Zbl 1491.60115 |
| [8] | Abdulle, A.; Vilmart, G.; Zygalakis, K. C., Weak second order explicit stabilized methods for stiff stochastic differential equations, SIAM J. Sci. Comput., 35, A1792-A1814 (2013) · Zbl 1281.65005 |
| [9] | Ackmann, J.; Düben, P. D.; Palmer, T. N.; Smolarkiewicz, P. K., Mixed-precision for linear solvers in global geophysical flows (2021), arXiv preprint |
| [10] | Agullo, E.; Cappello, F.; Di, S.; Giraud, L.; Liang, X.; Schenkels, N., Exploring variable accuracy storage through lossy compression techniques in numerical linear algebra: a first application to flexible GMRES (2020), Inria Bordeaux Sud-Ouest, Ph.D. thesis |
| [11] | Almuslimani, I., A fully adaptive explicit stabilized integrator for advection-diffusion-reaction problems (2022) |
| [12] | P. Amestoy, O. Boiteau, A. Buttari, M. Gerest, F. Jézéquel, J.Y. l’Excellent, T. Mary, 2021, Mixed precision low rank approximations and their application to block low rank lu factorization. |
| [13] | P. Amestoy, A. Buttari, N.J. Higham, J.Y. l’Excellent, T. Mary, B. Vieuble, 2021, Five-precision GMRES-based iterative refinement. |
| [14] | Balay, S.; Abhyankar, S.; Adams, M.; Brown, J.; Brune, P. R.; Buschelman, K.; Eijkhout, V.; Gropp, W.; Kaushik, D.; Knepley, M. G., PETSc users manual revision 3.8 (2017), Argonne National Laboratory (ANL), Technical Report |
| [15] | Björck, Å.; Paige, C. C., Loss and recapture of orthogonality in the modified Gram-Schmidt algorithm, SIAM J. Matrix Anal. Appl., 13, 176-190 (1992) · Zbl 0747.65026 |
| [16] | Blanchard, P.; Higham, N. J.; Lopez, F.; Mary, T.; Pranesh, S., Mixed precision block fused multiply-add: error analysis and application to GPU tensor cores, SIAM J. Sci. Comput., 42, C124-C141 (2020) · Zbl 1452.65425 |
| [17] | Briggs, W. L.; Henson, V. E.; McCormick, S. F., A Multigrid Tutorial (2000), SIAM · Zbl 0958.65128 |
| [18] | Burnett, B.; Gottlieb, S.; Grant, Z. J.; Heryudono, A., Performance evaluation of mixed-precision Runge-Kutta methods (2021) |
| [19] | Carle, C.; Hochbruck, M.; Sturm, A., On leapfrog-Chebyshev schemes, SIAM J. Numer. Anal., 58, 2404-2433 (2020) · Zbl 1454.65046 |
| [20] | Carson, E.; Higham, N. J., A new analysis of iterative refinement and its application to accurate solution of ill-conditioned sparse linear systems, SIAM J. Sci. Comput., 39, A2834-A2856 (2017) · Zbl 1379.65019 |
| [21] | Carson, E.; Higham, N. J., Accelerating the solution of linear systems by iterative refinement in three precisions, SIAM J. Sci. Comput., 40, A817-A847 (2018) · Zbl 1453.65067 |
| [22] | Connolly, M. P.; Higham, N. J.; Mary, T., Stochastic rounding and its probabilistic backward error analysis (2020), The University of Manchester: The University of Manchester Manchester, Technical Report |
| [23] | Croci, M., Libchopping – a parallel low-precision emulator in C++ and Python (2019) |
| [24] | Croci, M.; Fasi, M.; Higham, N. J.; Mary, T.; Mikaitis, M., Stochastic rounding: implementation, error analysis and applications, R. Soc. Open Sci., 9, Article 211631 pp. (2021) |
| [25] | Croci, M.; Giles, M. B., Effects of round-to-nearest and stochastic rounding in the numerical solution of the heat equation in low precision (2020), Technical Report |
| [26] | Das, D.; Mellempudi, N.; Mudigere, D.; Kalamkar, D.; Avancha, S.; Banerjee, K.; Sridharan, S.; Vaidyanathan, K.; Kaul, B.; Georganas, E., Mixed precision training of convolutional neural networks using integer operations (2018), arXiv preprint |
| [27] | Dembo, R. S.; Eisenstat, S. C.; Steihaug, T., Inexact Newton methods, SIAM J. Numer. Anal., 19, 400-408 (1982) · Zbl 0478.65030 |
| [28] | Düben, P. D.; Subramanian, A.; Dawson, A.; Palmer, T., A study of reduced numerical precision to make superparameterization more competitive using a hardware emulator in the OpenIFS model, J. Adv. Model. Earth Syst., 9, 566-584 (2017) |
| [29] | Dumont, T.; Duarte, M.; Descombes, S.; Dronne, M. A.; Massot, M.; Louvet, V., Simulation of human ischemic stroke in realistic 3D geometry, Commun. Nonlinear Sci. Numer. Simul., 18, 1539-1557 (2013) · Zbl 1322.92019 |
| [30] | Falgout, R. D.; Yang, U. M., Hypre: a library of high performance preconditioners, (International Conference on Computational Science (2002), Springer), 632-641 · Zbl 1056.65046 |
| [31] | Grant, Z. J., Perturbed Runge-Kutta methods for mixed precision applications (2020) |
| [32] | Gratton, S.; Simon, E.; Titley-Peloquin, D.; Toint, P., Exploiting variable precision in GMRES (2019), arXiv preprint |
| [33] | Griewank, A.; Walther, A., Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation (2008), SIAM · Zbl 1159.65026 |
| [34] | Grote, M. J.; Michel, S.; Sauter, S. A., Stabilized leapfrog based local time-stepping method for the wave equation, Math. Comput., 90, 2603-2643 (2021) · Zbl 1493.65151 |
| [35] | Hairer, E.; McLachlan, R. I.; Razakarivony, A., Achieving Brouwer’s law with implicit Runge-Kutta methods, BIT Numer. Math., 48, 231-243 (2008) · Zbl 1148.65058 |
| [36] | Hairer, E.; Nörsett, S. P.; Wanner, G., Solving Ordinary Differential Equations I, Springer Series in Computational Mathematics, vol. 8 (2008), Springer-Verlag: Springer-Verlag Berlin |
| [37] | Hairer, E.; Wanner, G., Solving Ordinary Differential Equations II, vol. 14 (1996), Springer-Verlag Berlin Heidelberg · Zbl 0859.65067 |
| [38] | Harris, C. R.; Millman, K. J., Array programming with NumPy, Nature, 585, 357-362 (2020) |
| [39] | Henrici, P., Discrete Variable Methods in Ordinary Differential Equations (1962), John Wiley & Sons, Inc. · Zbl 0112.34901 |
| [40] | Henrici, P., Error Propagation in Difference Methods (1963), John Wiley & Sons, Inc. · Zbl 0171.36104 |
| [41] | Higham, N. J., The accuracy of floating point summation, SIAM J. Sci. Comput., 14, 783-799 (1993) · Zbl 0788.65053 |
| [42] | Higham, N. J., Accuracy and Stability of Numerical Algorithms (2002), SIAM · Zbl 1011.65010 |
| [43] | Higham, N. J.; Mary, T., A new approach to probabilistic rounding error analysis, SIAM J. Sci. Comput., 41, 2815-2835 (2019) · Zbl 07123205 |
| [44] | Higham, N. J.; Pranesh, S., Simulating low precision floating-point arithmetic, SIAM J. Sci. Comput., 41, C585-C602 (2019) · Zbl 07124603 |
| [45] | Higham, N. J.; Pranesh, S.; Zounon, M., Squeezing a matrix into half precision, with an application to solving linear systems, SIAM J. Sci. Comput., 41, A2536-A2551 (2019) · Zbl 1420.65017 |
| [46] | Klöwer, M.; Düben, P.; Palmer, T., Number formats, error mitigation, and scope for 16-bit arithmetics in weather and climate modeling analyzed with a shallow water model, J. Adv. Model. Earth Syst., 12, Article e2020MS002246 pp. (2020) |
| [47] | Klöwer, M.; Hatfield, S.; Croci, M.; Düben, P. D.; Palmer, T. N., Fluid simulations accelerated with 16 bits: approaching 4x speedup on A64FX by squeezing ShallowWaters.jl into Float16, J. Adv. Model. Earth Syst., 14, Article e2021MS002684 pp. (2022) |
| [48] | Lange, M.; Rump, S. M., Error estimates for the summation of real numbers with application to floating-point summation, BIT Numer. Math., 57, 927-941 (2017) · Zbl 1380.65083 |
| [49] | Lebedev, V. I., How to solve stiff systems of differential equations by explicit methods, (Numer. Methods Appl. (1994), CRC: CRC Boca Raton, FL), 45-80 · Zbl 0851.65052 |
| [50] | Lebedev, V. I.; Medovikov, A. A., Explicit methods of second order for the solution of stiff systems of ODEs, Russ. Acad. Sci. (1994) |
| [51] | Lindberg, B., IMPEX: a program package for solution of systems of stiff differential equations (1972), Dept. of Information Processing, Royal Inst. of Tech.: Dept. of Information Processing, Royal Inst. of Tech. Stockholm, Technical Report |
| [52] | Logg, A.; Mardal, K. A.; Wells, G., Automated Solution of Differential Equations by the Finite Element Method: The FEniCS Book, vol. 84 (2012), Springer Science & Business Media · Zbl 1247.65105 |
| [53] | Lopez, F.; Mary, T., Mixed precision LU factorization on GPU tensor cores: reducing data movement and memory footprint (2020), The University of Manchester, Technical Report |
| [54] | McCormick, S. F.; Benzaken, J.; Tamstorf, R., Algebraic error analysis for mixed-precision multigrid solvers, SIAM J. Sci. Comput., S392-S419 (2021) · Zbl 07418113 |
| [55] | Medovikov, A. A., High order explicit methods for parabolic equations, BIT Numer. Math., 38, 372-390 (1998) · Zbl 0909.65060 |
| [56] | Mellempudi, N.; Srinivasan, S.; Das, D.; Kaul, B., Mixed precision training with 8-bit floating point (2019), arXiv preprint |
| [57] | Meurant, G.; Strakoš, Z., The Lanczos and conjugate gradient algorithms in finite precision arithmetic, Acta Numer., 15, 471-542 (2006) · Zbl 1113.65032 |
| [58] | Meyer, C. D.; Balsara, D. S.; Aslam, T. D., A stabilized Runge-Kutta-Legendre method for explicit super-time-stepping of parabolic and mixed equations, J. Comput. Phys., 257, 594-626 (2014) · Zbl 1349.65520 |
| [59] | Micikevicius, P.; Narang, S.; Alben, J.; Diamos, G.; Elsen, E.; Garcia, D.; Ginsburg, B.; Houston, M.; Kuchaiev, O.; Venkatesh, G., Mixed precision training (2017), arXiv preprint |
| [60] | Paxton, E. A.; Chantry, M.; Klöwer, M.; Saffin, L.; Palmer, T., Climate modelling in low-precision: effects of both deterministic & stochastic rounding (2021), arXiv preprint |
| [61] | Rosilho de Souza, G., Application of stabilized explicit Runge-Kutta methods to the incompressible Navier-Stokes equations by means of a projection method and a differential algebraic approach (2014), EPFL, Master’s thesis |
| [62] | Sommeijer, B. P.; Shampine, L.; Verwer, J. G., RKC: an explicit solver for parabolic PDEs, J. Comput. Appl. Math., 88, 315-326 (1998) · Zbl 0910.65067 |
| [63] | Tamstorf, R.; Benzaken, J.; McCormick, S. F., Discretization-error-accurate mixed-precision multigrid solvers, SIAM J. Sci. Comput., S420-S447 (2021) · Zbl 07418114 |
| [64] | Tang, X.; Xiao, A., Improved Runge-Kutta-Chebyshev methods, Math. Comput. Simul., 174, 59-75 (2020) · Zbl 1453.65168 |
| [65] | Tisseur, F., Newton’s method in floating point arithmetic and iterative refinement of generalized eigenvalue problems, SIAM J. Matrix Anal. Appl., 22, 1038-1057 (2001) · Zbl 0982.65040 |
| [66] | Van der Houwen, P. J.; Sommeijer, B. P., On the internal stability of explicit, m-stage Runge-Kutta methods for large m-values, Z. Angew. Math. Mech., 60, 479-485 (1980) · Zbl 0455.65052 |
| [67] | Váňa, F.; Düben, P.; Lang, S.; Palmer, T.; Leutbecher, M.; Salmond, D.; Carver, G., Single precision in weather forecasting models: an evaluation with the IFS, Mon. Weather Rev., 145, 495-502 (2017) |
| [68] | Verwer, J. G., An implementation of a class of stabilized explicit methods for the time integration of parabolic equations, ACM Trans. Math. Softw., 6, 188-205 (1980) · Zbl 0431.65069 |
| [69] | Verwer, J. G., A note on a Runge-Kutta-Chebyshev method, Z. Angew. Math. Mech., 62, 561-563 (1982) · Zbl 0531.65040 |
| [70] | Verwer, J. G., Explicit Runge-Kutta methods for parabolic partial differential equations, Appl. Numer. Math., 22, 359-379 (1996) · Zbl 0868.65064 |
| [71] | Verwer, J. G.; Hundsdorfer, W. H.; Sommeijer, B. P., Convergence properties of the Runge-Kutta-Chebyshev method, Numer. Math., 57, 157-178 (1990) · Zbl 0697.65072 |
| [72] | Verwer, J. G.; Sommeijer, B. P., An implicit-explicit Runge-Kutta-Chebyshev scheme for diffusion-reaction equations, SIAM J. Sci. Comput., 25, 1824-1835 (2004) · Zbl 1061.65090 |
| [73] | Virtanen, P.; Gommers, R.; Oliphant, T. E.; Haberland, M., SciPy 1.0: fundamental algorithms for scientific computing in Python, Nat. Methods, 17, 261-272 (2020) |
| [74] | Yamazaki, I.; Tomov, S.; Dongarra, J., Mixed-precision Cholesky QR factorization and its case studies on multicore CPU with multiple GPUs, SIAM J. Sci. Comput., 37, C307-C330 (2015) · Zbl 1320.65046 |
| [75] | Yang, L. M.; Fox, A.; Sanders, G., Rounding error analysis of mixed precision block householder QR algorithms, SIAM J. Sci. Comput., 43, A1723-A1753 (2021) · Zbl 1512.65066 |
| [76] | Zheng, Z.; Petzold, L. R., Runge-Kutta-Chebyshev projection method, J. Comput. Phys., 219, 976-991 (2006) · Zbl 1103.76048 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
