×

A distributed and parallel unite and conquer method to solve sequences of non-Hermitian linear systems. (English) Zbl 1422.65063

Summary: Many problems in science and engineering often require to solve a long sequence of large-scale non-Hermitian linear systems with different right-hand sides (RHSs) but a unique operator. Efficiently solving such problems on extreme-scale platforms requires the minimization of global communications, reduction of synchronization and promotion of asynchronous communications. Unite and Conquer GMRES/LS-ERAM (UCGLE) method [the authors, “A distributed and parallel asynchronous unite and conquer method to solve large scale non-Hermitian linear systems”, in: Proceedings of the international conference on high performance computing in Asia-Pacific region. New York, NY: Association for Computing Machinery (ACM). 36–46 (2018: doi:10.1145/3149457.3154481)] is a suitable candidate with the reduction of global communications and the synchronization points of all computing units. It consists of three computing algorithms with asynchronous communications that allow the use of approximated eigenvalues to accelerate the convergence of solving linear systems and to improve fault tolerance. In this paper, we extend both the mathematical model and the implementation of UCGLE method to adapt to solve sequences of linear systems. The eigenvalues obtained in solving previous linear systems by UCGLE can be recycled, improved on the fly and applied to construct a new initial guess vector for subsequent linear systems, which can achieve a continuous acceleration to solve linear systems in sequence. Numerical experiments using different test matrices to solve sequences of linear systems on supercomputer Tianhe-2 indicate a substantial decrease in both computation time and iteration steps when the approximated eigenvalues are recycled to generate the initial guess vectors.

MSC:

65F10 Iterative numerical methods for linear systems
62F15 Bayesian inference
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Abdel-Rehim, A.M., Morgan, R.B., Wilcox, W.: Improved seed methods for symmetric positive definite linear equations with multiple right-hand sides. Numer. Linear Algebra Appl. 21(3), 453-471 (2014) · Zbl 1340.65041
[2] Arnoldi, W.E.: The principle of minimized iterations in the solution of the matrix eigenvalue problem. Q. Appl. Math. 9(1), 17-29 (1951) · Zbl 0042.12801
[3] Baker, A.H., Dennis, J.M., Jessup, E.R.: On improving linear solver performance: a block variant of gmres. SIAM J. Sci. Comput. 27(5), 1608-1626 (2006) · Zbl 1099.65029
[4] Bellavia, S., Morini, B.: A globally convergent Newton-GMRES subspace method for systems of nonlinear equations. SIAM J. Sci. Comput. 23(3), 940-960 (2001) · Zbl 0998.65053
[5] Benner, P., Feng, L.: Recycling Krylov subspaces for solving linear systems with successively changing right-hand sides arising in model reduction. In: Model Reduction for Circuit Simulation, pp. 125-140. Springer, Berlin (2011)
[6] Brown, P.N., Saad, Y.: Hybrid Krylov methods for nonlinear systems of equations. SIAM J. Sci. Stat. Comput. 11(3), 450-481 (1990) · Zbl 0708.65049
[7] Calvetti, D., Reichel, L.: Application of a block modified Chebyshev algorithm to the iterative solution of symmetric linear systems with multiple right hand side vectors. Numer. Math. 68(1), 3-16 (1994) · Zbl 0808.65024
[8] Craig, R.R., Hale, A.L.: Block-Krylov component synthesis method for structural model reduction. J. Guid. Control Dyn. 11(6), 562-570 (1988) · Zbl 0671.73061
[9] Dongarra, J., Hittinger, J., Bell, J., Chacon, L., Falgout, R., Heroux, M., Hovland, P., Ng, E., Webster, C., Wild, S.: Applied mathematics research for exascale computing. Tech. rep., Lawrence Livermore National Laboratory (LLNL), Livermore (2014)
[10] Emad, N., Petiton, S.: Unite and conquer approach for high scale numerical computing. J. Comput. Sci. 14, 5-14 (2016)
[11] Essai, A., Bergére, G., Petiton, S.G.: Heterogeneous parallel hybrid GMRES/LS-Arnoldi method. In: PPSC (1999)
[12] Flueck, A.J., Chiang, H.D.: Solving the nonlinear power flow equations with an inexact Newton method using GMRES. IEEE Trans. Power Syst. 13(2), 267-273 (1998)
[13] Gu, G.D.: A seed method for solving nonsymmetric linear systems with multiple right-hand sides. Int. J. Comput. Math. 79(3), 307-326 (2002) · Zbl 0995.65031
[14] Gullerud, A.S., Dodds Jr., R.H.: MPI-based implementation of a PCG solver using an EBE architecture and preconditioner for implicit, 3-D finite element analysis. Comput. Struct. 79(5), 553-575 (2001)
[15] Gutknecht, M.H.: Block Krylov space methods for linear systems with multiple right-hand sides: an introduction (2006)
[16] He, H., Bergère, G., Petiton, S.: A hybrid GMRES/LS-Arnoldi method to accelerate the parallel solution of linear systems. Comput. Math. Appl. 51(11), 1647-1662 (2006) · Zbl 1146.65314
[17] Jolivet, P., Tournier, P.H.: Block iterative methods and recycling for improved scalability of linear solvers. In: SC16-International Conference for High Performance Computing, Networking, Storage and Analysis (2016)
[18] Kershaw, D.S.: The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations. J. Comput. Phys. 26(1), 43-65 (1978) · Zbl 0367.65018
[19] Kilmer, M.E., De Sturler, E.: Recycling subspace information for diffuse optical tomography. SIAM J. Sci. Comput. 27(6), 2140-2166 (2006) · Zbl 1103.65036
[20] Knoll, D.A., Keyes, D.E.: Jacobian-free Newton-Krylov methods: a survey of approaches and applications. J. Comput. Phys. 193(2), 357-397 (2004) · Zbl 1036.65045
[21] Papadrakakis, M., Smerou, S.: A new implementation of the Lanczos method in linear problems. Int. J. Numer. Methods Eng. 29(1), 141-159 (1990) · Zbl 0712.73105
[22] Parks, M.L., De Sturler, E., Mackey, G., Johnson, D.D., Maiti, S.: Recycling Krylov subspaces for sequences of linear systems. SIAM J. Sci. Comput. 28(5), 1651-1674 (2006) · Zbl 1123.65022
[23] Saad, Y.: Least squares polynomials in the complex plane and their use for solving nonsymmetric linear systems. SIAM J. Numer. Anal. 24(1), 155-169 (1987) · Zbl 0619.65022
[24] Saad, Y.: On the Lanczos method for solving symmetric linear systems with several right-hand sides. Math. Comput. 48(178), 651-662 (1987) · Zbl 0615.65038
[25] Saad, Y.: Numerical Methods for Large Eigenvalue Problems, Revised edn. SIAM, Philadelphia (2011) · Zbl 1242.65068
[26] Saad, Y., Schultz, M.H.: GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 7(3), 856-869 (1986) · Zbl 0599.65018
[27] Simoncini, V., Gallopoulos, E.: An iterative method for nonsymmetric systems with multiple right-hand sides. SIAM J. Sci. Comput. 16(4), 917-933 (1995) · Zbl 0831.65037
[28] Smith, C.F., Peterson, A.F., Mittra, R.: A conjugate gradient algorithm for the treatment of multiple incident electromagnetic fields. IEEE Trans. Antennas Propag. 37(11), 1490-1493 (1989)
[29] Wu, X.: SMG2S Manual v1.0. Technical report, Maison de la Simulation (2018)
[30] Wu, X., Petiton, S.G.: A distributed and parallel asynchronous unite and conquer method to solve large scale non-Hermitian linear systems. In: Proceedings of the International Conference on High Performance Computing in Asia-Pacific Region. ACM, New York, pp. 36-46 (2018). https://doi.org/10.1145/3149457.3154481
[31] Wu, X., Petiton, S.G., Lu, Y.: A parallel generator of non-Hermitian matrices computed from given spectra. In: International Conference on Vector and Parallel Processing, pp. 215-229. Springer, Berlin (2018)
[32] Ye, Z., Zhu, Z., Phillips, J.R.: Generalized Krylov recycling methods for solution of multiple related linear equation systems in electromagnetic analysis. In: Proceedings of the 45th Annual Design Automation Conference. ACM, pp. 682-687 (2008)
[33] Zhang, Y., Bergere, G., Petiton, S.: Large scale parallel hybrid GMRES method for the linear system on grid system. In: International Symposium on Parallel and Distributed Computing, 2008. ISPDC’08. IEEE, pp. 244-249 (2008)
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.