Numerical investigation of ensemble methods with block iterative solvers for evolution problems

Lili Ju; Wei Leng; Zhu Wang; Shuai Yuan

doi:10.3934/dcdsb.2020132

Article Contents

2020, Volume 25, Issue 12: 4905-4923. Doi: 10.3934/dcdsb.2020132

This issue Previous Article A game-theoretic framework for autonomous vehicles velocity control: Bridging microscopic differential games and macroscopic mean field games Next Article Corrigendum on “H. Li and M. Ma, global dynamics of a virus infection model with repulsive effect, Discrete and Continuous Dynamical Systems, Series B, 24(9) 4783-4797, 2019”

Numerical investigation of ensemble methods with block iterative solvers for evolution problems

1.
Department of Mathematics, University of South Carolina, Columbia, SC 29208
2.
State Key Laboratory of Scientific and Engineering Computing, Chinese Academy of Sciences, Beijing 100190, China

^* Corresponding author: Zhu Wang
^* Corresponding author: Zhu Wang

Received: November 2019

Revised: January 2020

Early access: April 2020

Published: December 2020

The first author's research was partially supported by U.S. National Science Foundation under grant number DMS-1818438 and U.S. Department of Energy under grant numbers DE-SC0016540 and DE-SC0020270. The second author's research was partially supported the National Key Research and Development Program of China under grant number 2016YFB0201304, National Natural Science Foundation of China under grant numbers 91430215, 91530323, 11501553 and 11771440, State Key Laboratory of Scientific and Engineering Computing (LSEC), and National Center for Mathematics and Interdisciplinary Sciences of Chinese Academy of Sciences (NCMIS). The third author's research was partially supported by U.S. Department of Energy under grant numbers DE-SC0016540 and DE-SC0020270, U.S. National Science Foundation under grant number DMS-1913073 and Office of the Vice President for Research at the University of South Carolina through an ASPIRE grant.

Abstract / Introduction Full Text(HTML) Figure(5) / Table(7) Related Papers Cited by

Abstract

The ensemble method has been developed for accelerating a sequence of numerical simulations of evolution problems. Its main idea is, by manipulating the time stepping and grouping discrete problems, to make all members in the same group share a common coefficient matrix. Thus, at each time step, instead of solving a sequence of linear systems each of which contains only one right-hand-side vector, the ensemble method simultaneously solves a single linear system with multiple right-hand-side vectors for each group. Such a system could be solved efficiently by using direct linear solvers when the problems are of small scale, as the same LU factorization would work for the entire group members. However, for large-scale problems, iterative linear solvers often have to be used and then this appealing advantage becomes not obvious. In this paper we systematically investigate numerical performance of the ensemble method with block iterative solvers for two typical evolution problems: the heat equation and the incompressible Navier-Stokes equations. In particular, the block conjugate gradient (CG) solver is considered for the former and the block generalized minimal residual (GMRES) solver for the latter. Our numerical results demonstrate the effectiveness and efficiency of the ensemble method when working together with these block iterative solvers.

Keywords:

Mathematics Subject Classification: Primary: 65M60.

Citation:

Full Text(HTML)

Figure 1. Time evolution of the dimension of the search space at different iterations in BFBCG

Download: Full-size image PowerPoint slide

Figure 2. Time evolution of the rank of RHS vectors using the BGMRES-D solver in Problem 2

Download: Full-size image PowerPoint slide

Figure 3. Speed fields at $ t = 60 $ for three problems in the ensemble simulation (left column) and individual simulations (right column) in Problem 3

Download: Full-size image PowerPoint slide

Figure 4. Time evolutions of velocity magnitude for three problems in the ensemble simulation (left column) and individual simulations (right column) in Problem 3

Download: Full-size image PowerPoint slide

Figure 5. Time evolution of the rank of RHS vectors using BGMRES-D solver in Problem 3

Download: Full-size image PowerPoint slide

Table 1. The $ L_2 $ errors at final time: first-order ensemble, $ Q_1 $ elements in Problem 1

($ N_x $, $ N_y $, $ K $)	$ \mathcal{E}_1^N $	Rate	$ \mathcal{E}_{50}^N $	Rate	$ \mathcal{E}_{100}^N $	Rate
(16, 32, 50)	5.8005$ \times 10^{-2} $	–	4.3544$ \times 10^{-2} $	–	4.8908$ \times 10^{-2} $	–
(32, 64,100)	2.9140$ \times 10^{-2} $	0.99	2.1972$ \times 10^{-2} $	0.99	2.4615$ \times 10^{-2} $	0.99
(64,128,200)	1.4629$ \times 10^{-2} $	0.99	1.1061$ \times 10^{-2} $	0.99	1.2371$ \times 10^{-2} $	0.99
(128,256,400)	7.3326$ \times 10^{-3} $	1.00	5.5529$ \times 10^{-3} $	1.00	6.2053$ \times 10^{-3} $	1.00

| Show Table

DownLoad: CSV

Table 2. The $ L_2 $ errors at final time: second-order ensemble, $ Q_2 $ elements in Problem 1

($ N_x $, $ N_y $, $ K $)	$ \mathcal{E}_1^N $	Rate	$ \mathcal{E}_{50}^N $	Rate	$ \mathcal{E}_{100}^N $	Rate
(8, 16, 50)	3.1827$ \times 10^{-3} $	–	2.4799$ \times 10^{-3} $	–	2.7259$ \times 10^{-3} $	–
(16, 32,100)	7.6003$ \times 10^{-4} $	2.07	5.8014$ \times 10^{-4} $	2.10	6.4617$ \times 10^{-4} $	2.08
(32, 64,200)	1.9288$ \times 10^{-4} $	1.98	1.4695$ \times 10^{-4} $	1.98	1.6366$ \times 10^{-4} $	1.98
(64,128,400)	4.9629$ \times 10^{-5} $	1.96	3.7682$ \times 10^{-5} $	1.96	4.2046$ \times 10^{-5} $	1.96

| Show Table

DownLoad: CSV

Table 3. CPU time comparison in Problem 1

Iteration & CPU time	BFBCG	100 CG
Average iteration number per time step	4	4$ \times $ 100
Average execution time per step (seconds)	5.6362$ \times 10^{-1} $	(1.1482$ \times 10^{-2} $) $ \times $ 100
Total CPU time for integration (seconds)	5.658$ \times 10^{2} $	1.464$ \times 10^{3} $

| Show Table

DownLoad: CSV

Table 4. The $ L_2 $ errors at final time: first-order ensemble, $ Q_2/Q_1 $ elements in Problem 2

($ N_x $, $ N_y $, $ K $)	$ \mathcal{E}_1^N $	Rate	$ \mathcal{E}_{20}^N $	Rate	$ \mathcal{E}_{40}^N $	Rate
(128,128, 5)	3.7899$ \times 10^{-3} $	–	3.4660$ \times 10^{-3} $	–	3.6324$ \times 10^{-3} $	–
(128,128, 10)	1.9331$ \times 10^{-3} $	0.97	1.7626$ \times 10^{-3} $	0.98	1.8478$ \times 10^{-3} $	0.98
(128,128, 20)	9.7905$ \times 10^{-4} $	0.98	8.9096$ \times 10^{-4} $	0.98	9.3418$ \times 10^{-4} $	0.98
(128,128, 40)	4.8947$ \times 10^{-4} $	1.00	4.4499$ \times 10^{-4} $	1.00	4.6666$ \times 10^{-4} $	1.00

| Show Table

DownLoad: CSV

Table 5. The $ L_2 $ errors at final time: second-order ensemble, $ Q_2/Q_1 $ elements in Problem 2

($ N_x $, $ N_y $, $ K $)	$ \mathcal{E}_1^N $	Rate	$ \mathcal{E}_{20}^N $	Rate	$ \mathcal{E}_{40}^N $	Rate
(256,256, 5)	1.0597$ \times 10^{-3} $	–	9.5139$ \times 10^{-4} $	–	9.9694$ \times 10^{-4} $	–
(256,256, 10)	2.5992$ \times 10^{-4} $	2.03	2.3215$ \times 10^{-4} $	2.03	2.4328$ \times 10^{-4} $	2.03
(256,256, 20)	6.3997$ \times 10^{-5} $	2.02	5.7010$ \times 10^{-5} $	2.03	5.9748$ \times 10^{-5} $	2.02
(256,256, 40)	1.5905$ \times 10^{-5} $	2.00	1.4112$ \times 10^{-5} $	2.01	1.4796$ \times 10^{-5} $	2.01

| Show Table

DownLoad: CSV

Table 6. CPU time comparison in Problem 2

Iteration & CPU time	BGMRES-D	40 GMRES
average iteration number per time step	5	5$ \times $ 40
average execution time per step (seconds)	19.658	12.032 $ \times $ 40
total CPU time for integration (seconds)	1.965$ \times 10^{3} $	2.103$ \times 10^{4} $

| Show Table

DownLoad: CSV

Table 7. CPU time comparison in Problem 3

Iteration & CPU time	BGMRES-D	40 GMRES
Average iteration number per time step	7	8$ \times $ 40
Average execution time per step (seconds)	4.7894	1.7313 $ \times $ 40
Total CPU time for integration (seconds)	7.106$ \times 10^{4} $	4.836$ \times 10^{5} $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	E. Agullo, L. Giraud and Y.-F. Jing, Block GMRES method with inexact breakdowns and deflated restarting, SIAM Journal on Matrix Analysis and Applications, 35 (2014), 1625-1651. doi: 10.1137/140961912.
[2]	A. H. Baker, J. M. Dennis and E. R. Jessup, On improving linear solver performance: A block variant of GMRES, SIAM Journal on Scientific Computing, 27 (2006), 1608-1626. doi: 10.1137/040608088.
[3]	H. Calandra, S. Gratton, R. Lago, X. Vasseur and L. M. Carvalho, A modified block flexible GMRES method with deflation at each iteration for the solution of non-hermitian linear systems with multiple right-hand sides, SIAM Journal on Scientific Computing, 35 (2013), S345–S367. doi: 10.1137/120883037.
[4]	H. Calandra, S. Gratton, J. Langou, X. Pinel and X. Vasseur, Flexible variants of block restarted GMRES methods with application to geophysics, SIAM Journal on Scientific Computing, 34 (2012), A714–A736. doi: 10.1137/10082364X.
[5]	T. F. Chan and M. K. Ng, Galerkin projection methods for solving multiple linear systems, SIAM Journal on Scientific Computing, 21 (1999), 836-850. doi: 10.1137/S1064827598310227.
[6]	A. T. Chronopoulos and A. B. Kucherov, Block-$s$-step Krylov iterative methods, Numerical Linear Algebra with Applications, 17 (2010), 3-15. doi: 10.1002/nla.643.
[7]	D. Darnell, R. B. Morgan and W. Wilcox, Deflated GMRES for systems with multiple shifts and multiple right-hand sides, Linear Algebra and its Applications, 429 (2008), 2415-2434. doi: 10.1016/j.laa.2008.04.019.
[8]	I. S. Duff, A. M. Erisman and J. K. Reid, Direct Methods for Sparse Matrices, Oxford University Press, 2017. doi: 10.1093/acprof:oso/9780198508380.001.0001.
[9]	H. C. Elman, A. Ramage and D. J. Silvester, IFISS: A computational laboratory for investigating incompressible flow problems, SIAM Review, 56 (2014), 261-273. doi: 10.1137/120891393.
[10]	H. C. Elman, D. J. Silvester and A. J. Wathen, Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics, Oxford University Press, 2005.
[11]	J. A. Fiordilino, A second order ensemble timestepping algorithm for natural convection, SIAM Journal on Numerical Analysis, 56 (2018), 816-837. doi: 10.1137/17M1135104.
[12]	W. D. Gropp, D. K. Kaushik, D. E. Keyes and B. F. Smith, Toward realistic performance bounds for implicit CFD codes, Parallel Computational Fluid Dynamics, (2000), 241–248. doi: 10.1016/B978-044482851-4.50030-X.
[13]	G.-D. Gu and Z.-H. Cao, A block GMRES method augmented with eigenvectors, Applied Mathematics and Computation, 121 (2001), 271-289. doi: 10.1016/S0096-3003(99)00294-5.
[14]	M. Gunzburger, N. Jiang and M. Schneier, An ensemble-proper orthogonal decomposition method for the nonstationary Navier-Stokes equations, SIAM Journal on Numerical Analysis, 55 (2017), 286-304. doi: 10.1137/16M1056444.
[15]	M. Gunzburger, N. Jiang and Z. Wang, A second-order time-stepping scheme for simulating ensembles of parameterized flow problems, Computational Methods in Applied Mathematics, 19 (2019), 681-701. doi: 10.1515/cmam-2017-0051.
[16]	M. Gunzburger, N. Jiang and Z. Wang, An efficient algorithm for simulating ensembles of parameterized flow problems, IMA Journal of Numerical Analysis, 39 (2019), 1180-1205. doi: 10.1093/imanum/dry029.
[17]	M. D. Gunzburger, Finite Element Methods for Viscous Incompressible Flows: A Guide to Theory, Practice, and Algorithms, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1989.
[18]	M. H. Gutknecht, Block Krylov space methods for linear systems with multiple right-hand sides: An introduction, Modern Mathematical Models, Methods and Algorithms for Real World Systems, 420–447.
[19]	H. Ji and Y. H. Li, A breakdown-free block conjugate gradient method, BIT Numerical Mathematics, 57 (2017), 379-403. doi: 10.1007/s10543-016-0631-z.
[20]	N. Jiang, S. Kaya and W. Layton, Analysis of model variance for ensemble based turbulence modeling, Computational Methods in Applied Mathematics, 15 (2015), 173-188. doi: 10.1515/cmam-2014-0029.
[21]	N. Jiang and W. Layton, An algorithm for fast calculation of flow ensembles, International Journal for Uncertainty Quantification, 4 (2014), 273-301. doi: 10.1615/Int.J.UncertaintyQuantification.2014007691.
[22]	N. Jiang and W. Layton, Numerical analysis of two ensemble eddy viscosity numerical regularizations of fluid motion, Numerical Methods for Partial Differential Equations, 31 (2015), 630-651. doi: 10.1002/num.21908.
[23]	Y. Luo and Z. Wang, An ensemble algorithm for numerical solutions to deterministic and random parabolic PDEs, SIAM Journal on Numerical Analysis, 56 (2018), 859-876. doi: 10.1137/17M1131489.
[24]	Y. Luo and Z. Wang, A multilevel Monte Carlo ensemble scheme for solving random parabolic PDEs, SIAM Journal on Scientific Computing, 41 (2019), A622–A642. doi: 10.1137/18M1174635.
[25]	J. McCarthy, Block-conjugate-gradient method, Physical Review D, 40 (1989), 2149. doi: 10.1103/PhysRevD.40.2149.
[26]	M. Mohebujjaman and L. G. Rebholz, An efficient algorithm for computation of MHD flow ensembles, Computational Methods in Applied Mathematics, 17 (2017), 121-137. doi: 10.1515/cmam-2016-0033.
[27]	R. B. Morgan, Restarted block-GMRES with deflation of eigenvalues, Applied Numerical Mathematics, 54 (2005), 222-236. doi: 10.1016/j.apnum.2004.09.028.
[28]	D. P. O'Leary, The block conjugate gradient algorithm and related methods, Linear Algebra and its Applications, 29 (1980), 293-322. doi: 10.1016/0024-3795(80)90247-5.
[29]	D. P. O'Leary, Parallel implementation of the block conjugate gradient algorithm, Parallel Computing, 5 (1987), 127-139. doi: 10.1016/0167-8191(87)90013-5.
[30]	M. L. Parks, E. De Sturler, G. Mackey, D. D. Johnson and S. Maiti, Recycling Krylov subspaces for sequences of linear systems, SIAM Journal on Scientific Computing, 28 (2006), 1651-1674. doi: 10.1137/040607277.
[31]	M. L. Parks, K. M. Soodhalter and D. B. Szyld, A block recycled GMRES method with investigations into aspects of solver performance, preprint, arXiv: 1604.01713.
[32]	V. Puzyrev and J. M. Cela, A review of block Krylov subspace methods for multisource electromagnetic modelling, Geophysical Journal International, 202 (2015), 1241-1252.
[33]	Y. Saad and M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing, 7 (1986), 856-869. doi: 10.1137/0907058.
[34]	Y. Saad, Iterative Methods for Sparse Linear Systems, Second edition, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003. doi: 10.1137/1.9780898718003.
[35]	V. Simoncini and E. Gallopoulos, Convergence properties of block GMRES and matrix polynomials, Linear Algebra and its Applications, 247 (1996), 97-119. doi: 10.1016/0024-3795(95)00093-3.
[36]	V. Simoncini and E. Gallopoulos, A hybrid block GMRES method for nonsymmetric systems with multiple right-hand sides, Journal of Computational and Applied Mathematics, 66 (1996), 457-469. doi: 10.1016/0377-0427(95)00198-0.
[37]	L. N. Trefethen and D. Bau III, Numerical Linear Algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. doi: 10.1137/1.9780898719574.