×

zbMATH — the first resource for mathematics

Inner product free iterative solution and elimination methods for linear systems of a three-by-three block matrix form. (English) Zbl 07246886
Summary: Large scale systems of algebraic equations are frequently solved by iterative solution methods, such as the conjugate gradient method for symmetric or a generalized conjugate gradient or generalized minimum residual method for nonsymmetric linear systems. In practice, to get an acceptable elapsed computing time when solving large scale problems, one shall use parallel computer platforms. However, such methods involve orthogonalization of search vectors which requires computation of many inner products and, hence, needs global communication of data, which will be costly in computer times. In this paper, we propose various inner product free methods, such as the Chebyshev acceleration method. We study the solution of linear systems arising from optimal control problems for PDEs, such as the edge element discretization of the time-periodic eddy current optimal control problem. Following a discretize-then-optimize scheme, the resulting linear system is of a three-by-three block matrix form. Various solution methods based on an approximate Schur complement and inner product free iterative solution methods for this linear system are analyzed and compared with an earlier used method for two-by-two block matrices with square blocks. The convergence properties and implementation details of the proposed methods are analyzed to show their effectiveness and practicality. Both serial and parallel numerical experiments are presented to further investigate the performance of the proposed methods compared with some other existing methods.
MSC:
65F10 Iterative numerical methods for linear systems
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F50 Computational methods for sparse matrices
49M41 PDE constrained optimization (numerical aspects)
Software:
AGMG; Matlab; MinRes; PETSc
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Paige, C. C.; Saunders, M. A., Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12, 4, 617-629 (1975) · Zbl 0319.65025
[2] Saad, Y., A flexible inner-outer preconditioned GMRES algorithm, SIAM J. Sci. Comput., 14, 2, 461-469 (1993) · Zbl 0780.65022
[3] Toselli, A.; Widlund, O., Domain Decomposition Methods: Algorithms and Theory, Vol. 34 (2005), Springer-Verlag: Springer-Verlag Berlin, Springer Ser. Comput. Math. edition
[4] Vassilevski, P., Multilevel Block Factorization Preconditioners (2008), Springer-Verlag: Springer-Verlag New York
[5] Ghysels, P.; Ashby, T. J.; Meerbergen, K.; Vanroose, W., Hiding global communication latency in the GMRES algorithm on massively parallel machines, SIAM J. Sci. Comput., 35, 48-71 (2013) · Zbl 1273.65050
[6] Ghysels, P.; Vanroose, W., Hiding global synchronization latency in the preconditioned conjugate gradient algorithm, Parallel Comput., 40, 224-238 (2014)
[7] Neytcheva, M., Arithmetic and Communication Complexity of Preconditioning Methods (1995), Faculty of Mathematics and Informatics, University of Nijmegen: Faculty of Mathematics and Informatics, University of Nijmegen Nijmegen, The Netherlands, (Ph.D. thesis)
[8] Krendl, W.; Simoncini, V.; Zulehner, W., Stability estimates and structural spectral properties of saddle point problems, Numer. Math., 124, 1, 183-213 (2013) · Zbl 1269.65032
[9] Kolmbauer, M.; Langer, U., A robust preconditioned minres solver for distributed time-periodic eddy current optimal control problems, SIAM J. Sci. Comput., 34, 6, B785-B809 (2012) · Zbl 1258.49059
[10] Kollmann, M.; Kolmbauer, M.; Langer, U.; Wolfmayr, M.; Zulehner, W., A robust finite element solver for a multiharmonic parabolic optimal control problem, Comput. Math. Appl., 65, 3, 469-486 (2013) · Zbl 1319.49043
[11] Langer, U.; Wolfmayr, M., Multiharmonic finite element analysis of a time-periodic parabolic optimal control problem, J. Numer. Math., 21, 4, 265-300 (2013) · Zbl 1284.65078
[12] Liang, Z.-Z.; Axelsson, O.; Neytcheva, M., A robust structured preconditioner for time-harmonic parabolic optimal control problems, Numer. Algorithms, 79, 575-596 (2018) · Zbl 1400.49041
[13] Axelsson, O.; Lukáš, D., Preconditioning methods for eddy-current optimally controlled time-harmonic electromagnetic problems, J. Numer. Math. (2018)
[14] Varga, R., Matrix Iterative Analysis (2000), Springer-Verlag, Berlin Heidelberg, originally published by PRENTICE HALL · Zbl 0998.65505
[15] Bai, Z.-Z.; Golub, G. H.; Ng, M. K., Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM J. Matrix Anal. Appl., 24, 3, 603-626 (2003) · Zbl 1036.65032
[16] Bai, Z.-Z.; Benzi, M.; Chen, F., Modified HSS iteration methods for a class of complex symmetric linear systems, Computing, 87, 3, 93-111 (2010) · Zbl 1210.65074
[17] Bai, Z.-Z.; Benzi, M.; Chen, F., On preconditioned MHSS iteration methods for complex symmetric linear systems, Numer. Algorithms, 56, 2, 297-317 (2011) · Zbl 1209.65037
[18] Bai, Z.-Z.; Benzi, M.; Chen, F.; Wang, Z.-Q., Preconditioned MHSS iteration methods for a class of block two-by-two linear systems with applications to distributed control problems, IMA J. Numer. Anal., 33, 1, 343-369 (2012) · Zbl 1271.65100
[19] Pearson, J. W.; Wathen, A. J., A new approximation of the Schur complement in preconditioners for PDE-constrained optimization, Numer. Linear Algebra Appl., 19, 5, 816-829 (2012) · Zbl 1274.65187
[20] Zheng, Z.; Zhang, G.-F.; Zhu, M.-Z., A note on preconditioners for complex linear systems arising from PDE-constrained optimization problems, Appl. Math. Lett., 61, 114-121 (2016) · Zbl 1346.49047
[21] Axelsson, O.; Liang, Z.-Z., A note on preconditioning methods for time-periodic eddy current optimal control problems, J. Comput. Appl. Math., 352, 262-277 (2018) · Zbl 1410.65093
[22] Axelsson, O.; Farouq, S.; Neytcheva, M., Comparison of preconditioned Krylov subspace iteration methods for PDE-constrained optimization problems: Stokes control, Numer. Algorithms, 74, 1, 19-37 (2017) · Zbl 1365.65167
[23] Axelsson, O.; Kucherov, A., Real valued iterative methods for solving complex symmetric linear systems, Numer. Linear Algebra Appl., 7, 4, 197-218 (2000) · Zbl 1051.65025
[24] Axelsson, O.; Neytcheva, M.; Ahmad, B., A comparison of iterative methods to solve complex valued linear algebraic systems, Numer. Algorithms, 66, 4, 811-841 (2014) · Zbl 1307.65034
[25] Arnold, D. N.; Falk, R. S.; Winther, R., Multigrid in H(div) and H(curl), Numer. Math., 85, 2, 197-217 (2000) · Zbl 0974.65113
[26] Hiptmair, R.; J.-C., Xu, Nodal auxiliary space preconditioning in H(curl) and H(div) spaces, SIAM J. Numer. Anal., 45, 6, 2483-2509 (2007) · Zbl 1153.78006
[27] Y. Notay, AGMG software and documentation; see http://homepages.ulb.ac.be/ ynotay.
[28] Notay, Y., Aggregation-based algebraic multigrid for convection-diffusion equations, SIAM J. Sci. Comput., 34, 4, A2288-A2316 (2012) · Zbl 1250.76139
[29] Napov, A.; Notay, Y., An algebraic multigrid method with guaranteed convergence rate, SIAM J. Sci. Comput., 34, 2, A1079-A1109 (2012) · Zbl 1248.65037
[30] Rodríguez, A. A.; Valli, A., Eddy Current Approximation of Maxwell Equations: Theory, Algorithms and Applications, Vol. 4 (2010), Springer Science & Business Media
[31] Kolmbauer, M., The Multiharmonic Finite Element and Boundary Element Method for Simulation and Control of Eddy Current Problems (2012), Johannes Kepler University: Johannes Kepler University Linz, [Ph.D. thesis]
[32] Nédélec, J.-C., Mixed finite elements in \(\mathbb{R}^3\), Numer. Math., 35, 3, 315-341 (1980) · Zbl 0419.65069
[33] Nédélec, J. C., A new family of mixed finite elements in \(\mathbb{R}^3\), Numer. Math., 50, 1, 57-81 (1986) · Zbl 0625.65107
[34] Axelsson, O.; Vassilevski, P. S., Algebraic multilevel preconditioning methods, II, SIAM J. Numer. Anal., 27, 6, 1569-1590 (1990) · Zbl 0715.65091
[35] Axelsson, O., Iterative Solution Methods (1994), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0795.65014
[36] Liang, Z.-Z.; Axelsson, O.; Zhang, G.-F., Efficient iterative solvers for a complex valued two-by-two block linear system with application to parabolic optimal control problems, Appl. Numer. Math., 152, 422-445 (2020) · Zbl 1433.65047
[37] Murphy, M. F.; Golub, G. H.; Wathen, A. J., A note on preconditioning for indefinite linear systems, SIAM J. Sci. Comput., 21, 6, 271-298 (2000)
[38] Anjam, I.; Valdman, J., Fast MATLAB assembly of FEM matrices in 2D and 3D: Edge elements, Appl. Math. Comput., 267, 252-263 (2015) · Zbl 1410.65441
[39] 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
[40] Kruzik, Jakub, Parallel implementation git repository (2020), https://gitlab.com/jkruzik/eddy_current
[41] Balay, Satish; Abhyankar, Shrirang; Adams, Mark F.; Brown, Jed; Brune, Peter; Buschelman, Kris; Dalcin, Lisandro; Dener, Alp; Eijkhout, Victor; Gropp, William D.; Karpeyev, Dmitry; Kaushik, Dinesh; Knepley, Matthew G.; May, Dave A.; McInnes, Lois Curfman; Mills, Richard Tran; Munson, Todd; Rupp, Karl; Sanan, Patrick; Smith, Barry F.; Zampini, Stefano; Zhang, Hong; Zhang, Hong, PETSc web page (2019), https://www.mcs.anl.gov/petsc
[42] Balay, Satish; Abhyankar, Shrirang; Adams, Mark F.; Brown, Jed; Brune, Peter; Buschelman, Kris; Dalcin, Lisandro; Dener, Alp; Eijkhout, Victor; Gropp, William D.; Karpeyev, Dmitry; Kaushik, Dinesh; Knepley, Matthew G.; May, Dave A.; McInnes, Lois Curfman; Mills, Richard Tran; Munson, Todd; Rupp, Karl; Sanan, Patrick; Smith, Barry F.; Zampini, Stefano; Zhang, Hong; Zhang, Hong, PETSc Users ManualTechnical Report ANL-95/11 - Revision 3.12 (2019), Argonne National Laboratory
[43] Barbora supercomputer web page (2020), https://docs.it4i.cz/barbora/introduction
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.