Interweaving PFASST and parallel multigrid. (English) Zbl 1325.65193
Summary: The parallel full approximation scheme in space and time (PFASST) introduced by M. Emmett and M. L. Minion [Commun. Appl. Math. Comput. Sci. 7, No. 1, 105–132 (2012; Zbl 1248.65106)] is an iterative strategy for the temporal parallelization of ODEs and discretized PDEs. As the name suggests, PFASST is similar in spirit to a space-time full approximation scheme multigrid method performed over multiple time steps in parallel. However, since the original focus of PFASST was on the performance of the method in terms of time parallelism, the solution of any spatial system arising from the use of implicit or semi-implicit temporal methods within PFASST have simply been assumed to be solved to some desired accuracy completely at each substep and each iteration by some unspecified procedure. It hence is natural to investigate how iterative solvers in the spatial dimensions can be interwoven with the PFASST iterations and whether this strategy leads to a more efficient overall approach. This paper presents an initial investigation on the relative performance of different strategies for coupling PFASST iterations with multigrid methods for the implicit treatment of diffusion terms in PDEs. In particular, we compare full accuracy multigrid solves at each substep with a small fixed number of multigrid V-cycles. This reduces the cost of each PFASST iteration at the possible expense of a corresponding increase in the number of PFASST iterations needed for convergence. Parallel efficiency of the resulting methods is explored through numerical examples.
MSC:
| 65Y05 | Parallel numerical computation |
| 65N55 | Multigrid methods; domain decomposition for boundary value problems involving PDEs |
| 65N40 | Method of lines for boundary value problems involving PDEs |
| 65N06 | Finite difference methods for boundary value problems involving PDEs |
Citations:
Zbl 1248.65106References:
| [1] | P. Amodio and L. Brugnano, {\it Parallel solution in time of ODEs: Some achievements and perspectives}, Appl. Numer. Math., 59 (2009), pp. 424-435. · Zbl 1166.65349 |
| [2] | K. Böhmer, P. Hemker, and H. J. Stetter, {\it The defect correction approach}, in Defect Correction Methods. Theory and Applications, K. Böhmer and H. J. Stetter, eds., Springer-Verlag, Berlin, 1984, pp. 1-32. · Zbl 0551.65034 |
| [3] | M. Bolten, {\it Evaluation of a multigrid solver for {\it 3}-level Toeplitz and circulant matrices on Blue Gene/Q}, in Proceedings of NIC Symposium 2014, K. Binder, G. Münster, and M. Kremer, eds., John von Neumann Institute for Computing, 2014, pp. 345-352. |
| [4] | A. Bourlioux, A. T. Layton, and M. L. Minion, {\it High-order multi-implicit spectral deferred correction methods for problems of reactive flow}, J. Comput. Phys., 189 (2003), pp. 651-675. · Zbl 1061.76053 |
| [5] | E. L. Bouzarth and M. L. Minion, {\it A multirate time integrator for regularized Stokeslets}, J. Comput. Phys., 229 (2010), pp. 4208-4224. · Zbl 1334.76097 |
| [6] | W. L. Briggs, V. E. Henson, and S. F. McCormick, {\it A Multigrid Tutorial}, SIAM, Philadelphia, 2000. · Zbl 0958.65128 |
| [7] | K. Burrage, {\it Parallel methods for ODEs}, Adv. Comput. Math., 7 (1997), pp. 1-3. · Zbl 0900.65210 |
| [8] | Th. Dickopf, M. J. Gander, L. Halpern, R. Krause, and L. F. Pavarino, eds., {\it Domain Decomposition Methods in Science and Engineering} XXII, Lect. Notes Comput. Sci. Eng. 104, Springer International Publishing, Switzerland, 2015. |
| [9] | A. Dutt, L. Greengard, and V. Rokhlin, {\it Spectral deferred correction methods for ordinary differential equations}, BIT, 40 (2000), pp. 241-266. · Zbl 0959.65084 |
| [10] | M. Emmett and M. L. Minion, {\it Toward an efficient parallel in time method for partial differential equations}, Comm. Appl. Math. Comput. Sci., 7 (2012), pp. 105-132. · Zbl 1248.65106 |
| [11] | M. Emmett and M. L. Minion, {\it Efficient implementation of a multi-level parallel in time algorithm}, in Domain Decomposition Methods in Science and Engineering XXI, Lect. Notes Comput. Sci. Eng. 98, Springer, Berlin, 2014, pp. 359-366. · Zbl 1382.65194 |
| [12] | R. D. Falgout, S. Friedhoff, Tz. V. Kolev, S. P. MacLachlan, and J. B. Schroder, {\it Parallel time integration with multigrid}, SIAM J. Sci. Comput., 36 (2014), pp. C635-C661. · Zbl 1310.65115 |
| [13] | S. Friedhoff, R. D. Falgout, T. V. Kolev, S. MacLachlan, and J. B. Schroder, {\it A multigrid-in-time algorithm for solving evolution equations in parallel}, presented at 16th Copper Mountain Conference on Multigrid Methods, Copper Mountain, CO, 2013. · Zbl 1310.65115 |
| [14] | M. J. Gander and A. M. Stuart, {\it Space-time continuous analysis of waveform relaxation for the heat equation}, SIAM J. Sci. Comput., 19 (1998), pp. 2014-2031. · Zbl 0911.65082 |
| [15] | A. Geist, {\it Paving the roadmap to exascale}, SciDAC Rev., 16 (2010), pp. 53-59. |
| [16] | W. Hackbusch, {\it Parabolic multi-grid methods}, in Proceedings of Computing Methods in Applied Sciences and Engineering VI, 1984, pp. 189-197. · Zbl 0565.65062 |
| [17] | T. Hagstrom and R. Zhou, {\it On the spectral deferred correction of splitting methods for initial value problems}, Commun. Appl. Math. Comput. Sci., 1 (2006), pp. 169-205. · Zbl 1105.65076 |
| [18] | G. Horton and R. Knirsch, {\it A time-parallel multigrid-extrapolation method for parabolic partial differential equations}, Parallel Computing, 18 (1992), pp. 21-29. · Zbl 0746.65073 |
| [19] | G. Horton and S. Vandewalle, {\it A space-time multigrid method for parabolic partial differential equations}, SIAM J. Sci. Comput., 16 (1995), pp. 848-864. · Zbl 0828.65105 |
| [20] | J. Huang, J. Jia, and M. Minion, {\it Accelerating the convergence of spectral deferred correction methods}, J. Comput. Phys., 214 (2006), pp. 633-656. · Zbl 1094.65066 |
| [21] | A. T. Layton and M. L. Minion, {\it Conservative multi-implicit spectral deferred correction methods for reacting gas dynamics}, J. Comput. Phys., 194 (2004), pp. 697-715. · Zbl 1100.76048 |
| [22] | A. T. Layton and M. L. Minion, {\it Implications of the choice of quadrature nodes for Picard integral deferred corrections methods for ordinary differential equations}, BIT, 45 (2005), pp. 341-373. · Zbl 1078.65552 |
| [23] | J.-L. Lions, Y. Maday, and G. Turinici, {\it A “parareal” in time discretization of PDE’s}, C. R. Acad. Sci. Ser. I Math., 332 (2001), pp. 661-668. · Zbl 0984.65085 |
| [24] | M. L. Minion, {\it Semi-implicit spectral deferred correction methods for ordinary differential equations}, Commun. Math. Sci., 1 (2003), pp. 471-500. · Zbl 1088.65556 |
| [25] | M. L. Minion, {\it A hybrid parareal spectral deferred corrections method}, Commun. Appl. Math. Comput. Sci., 5 (2010), pp. 265-301. · Zbl 1208.65101 |
| [26] | M. L. Minion and S. A. Williams, {\it Parareal and spectral deferred corrections}, in AIP Conf. Proc. 1048, American Institute of Physics, College Park, MD, 2008. |
| [27] | J. Nievergelt, {\it Parallel methods for integrating ordinary differential equations}, Commun. ACM, 7 (1964), pp. 731-733. · Zbl 0134.32804 |
| [28] | V. Pereyra, {\it On improving an approximate solution of a functional equation by deferred corrections}, Numer. Math., 8 (1966), pp. 376-391. · Zbl 0173.18103 |
| [29] | D. Ruprecht, R. Speck, M. Emmett, M. Bolten, and R. Krause, {\it Poster: Extreme-scale space-time parallelism}, in Proceedings of the 2013 Conference on High Performance Computing Networking, Storage and Analysis Companion, 2013. |
| [30] | R. Speck, D. Ruprecht, M. Emmett, M. Bolten, and R. Krause, {\it A space-time parallel solver for the three-dimensional heat equation}, in Parallel Computing: Accelerating Computational Science and Engineering (CSE), Adv. Parallel Comput. 25, IOS Press, Amsterdam, 2014, pp. 263-272. |
| [31] | R. Speck, D. Ruprecht, M. Emmett, M. Minion, M. Bolten, and R. Krause, {\it A multi-level spectral deferred correction method}, BIT (2014), pp. 1-25. · Zbl 1326.65138 |
| [32] | R. Speck, D. Ruprecht, R. Krause, M. Emmett, M. Minion, M. Winkel, and P. Gibbon, {\it A massively space-time parallel N-body solver}, in Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, Los Alamitos, CA, IEEE Computer Society Press, 2012, pp. 92:1-92:11. · Zbl 1443.76185 |
| [33] | H. J. Stetter, {\it Economical global error estimation}, in Stiff Differential Systems, R. A. Willoughby, ed., Plenum Press, New York, 1974, pp. 245-258. |
| [34] | S. Vandewalle and G. Horton, {\it Fourier mode analysis of the multigrid waveform relaxation and time-parallel multigrid methods}, Computing, 54 (1995), pp. 317-330. · Zbl 0826.65087 |
| [35] | M. Weiser, {\it Faster SDC Convergence on Non-Equidistant Grids with DIRK Sweeps}. \newblock ZIB Report 13-30, 2013. · Zbl 1332.65103 |
| [36] | P. E. Zadunaisky, {\it A method for the estimation of errors propagated in the numerical solution of a system of ordinary differential equations}, in The Theory of Orbits in the Solar System and in Stellar Systems, Vol. 25, Academic Press, London, 1966. |
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.
