×

A parallel augmented subspace method for eigenvalue problems. (English) Zbl 1451.65206

Summary: A type of parallel augmented subspace scheme for eigenvalue problems is proposed by using coarse space in the multigrid method. With the help of coarse space in the multigrid method, solving the eigenvalue problem in the finest space is decomposed into solving the standard linear boundary value problems and very-low-dimensional eigenvalue problems. The computational efficiency can be improved since there is no direct eigenvalue solving in the finest space and the multigrid method can act as the solver for the deduced linear boundary value problems. Furthermore, for different eigenvalues, the corresponding boundary value problem and low-dimensional eigenvalue problem can be solved in the parallel way since they are independent of each other and there exists no data exchanging. This property means that we do not need to do the orthogonalization in the highest-dimensional spaces. This is the main aim of this paper since avoiding orthogonalization can improve the scalability of the proposed numerical method. Some numerical examples are provided to validate the proposed parallel augmented subspace method.

MSC:

65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65N25 Numerical methods for eigenvalue problems for boundary value problems involving PDEs
65L15 Numerical solution of eigenvalue problems involving ordinary differential equations
65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
65Y05 Parallel numerical computation

Software:

lobpcg.m; BLOPEX; JDQR; JDQZ; SLEPc
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] R. A. Adams, Sobolev Spaces, Academic Press, New York, 1975. · Zbl 0314.46030
[2] I. Babuška and J. Osborn, Finite element-Galerkin approximation of the eigenvalues and eigenvectors of selfadjoint problems, Math. Comp., 52 (1989), pp. 275-297. · Zbl 0675.65108
[3] I. Babuška and J. Osborn, Eigenvalue problems, in Handbook of Numerical Analysis, Vol. 2, P. G. Lions and P. G. Ciarlet, eds., Finite Element Methods (Part 1), North-Holland, Amsterdam, 1991, pp. 641-787. · Zbl 0875.65087
[4] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, eds., Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, SIAM, Philadelphia, 2000. · Zbl 0965.65058
[5] R. E. Bank and T. Dupont, An optimal order process for solving finite element equations, Math. Comp., 36 (1981), pp. 35-51. · Zbl 0466.65059
[6] J. H. Bramble, Multigrid Methods, Pitman Research Notes in Mathematics, Vol. 294, John Wiley and Sons, New York, 1993.
[7] J. H. Bramble and J. E. Pasciak, New convergence estimates for multigrid algorithms, Math. Comp., 49 (1987), pp. 311-329. · Zbl 0659.65098
[8] J. H. Bramble, J. Pasciak, and A. Knyazev, A subspace preconditioning algorithm for eigenvector/eigenvalue computation, Adv. Comput. Math., 6 (1996), pp. 159-189. · Zbl 0879.65024
[9] J. H. Bramble and X. Zhang, The Analysis of Multigrid Methods, Handbook of Numerical Analysis, Vol. 7, P. G. Ciarlet and J. L. Lions, eds., Elsevier Science, New York, 2000, pp. 173-415. · Zbl 0972.65103
[10] S. Brenner and L. Scott, The Mathematical Theory of Finite Element Methods, Springer-Verlag, Berlin, 1994. · Zbl 0804.65101
[11] F. Chatelin, Spectral Approximation of Linear Operators, Academic Press, New York, 1983. · Zbl 0517.65036
[12] H. Chen, H. Xie, and F. Xu, A full multigrid method for eigenvalue problems, J. Comput. Phys., 322 (2016), pp. 747-759. · Zbl 1352.65459
[13] P. G. Ciarlet, The Finite Element Method for Elliptic Problem, North-Holland, Amsterdam, 1978. · Zbl 0383.65058
[14] E. G. D’yakonov and M. Yu. Orekhov, Minimization of the computational labor in determining the first eigenvalues of differential operators, Math. Notes, 27 (1980), pp. 382-391. · Zbl 0468.65056
[15] W. Greiner, Quantum Mechanics: An Introduction, 3rd ed., Springer, Berlin, 1994. · Zbl 0803.00007
[16] W. Hackbusch, On the computation of approximate eigenvalues and eigenfunctions of elliptic operators by means of a multi-grid method, SIAM J. Numer. Anal., 16 (1979), pp. 201-215. · Zbl 0403.65043
[17] W. Hackbusch, Multi-Grid Methods and Applications, Springer-Verlag, Berlin, 1985. · Zbl 0595.65106
[18] V. Hernandez, J. E. Roman, and V. Vidal, SLEPc: A scalable and flexible toolkit for the solution of eigenvalue problems, ACM Trans. Math. Software, 31 (2005), pp. 351-362. · Zbl 1136.65315
[19] Q. Hong, H. Xie, and F. Xu, A multilevel correction type of adaptive finite element method for eigenvalue problems, SIAM J. Sci. Comput., 40 (2018), pp. A4208-A4235.
[20] A. Knyazev, Preconditioned eigensolvers-An oxymoron? Electron. Trans. Numer. Anal., 7 (1998), pp. 104-123. · Zbl 1053.65513
[21] A. Knyazev, Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method, SIAM J. Sci. Comput., 23 (2001), pp. 517-541. · Zbl 0992.65028
[22] A. V. Knyazev, M. E. Argentati, I. Lashuk, and E. E. Ovtchinnikov, Block locally optimal preconditioned eigenvalue xolvers (BLOPEX) in hypre and PETSc, SIAM J. Sci. Comput., 29 (2007), pp. 2224-2239. · Zbl 1149.65026
[23] A. Knyazev and K. Neymeyr, Efficient solution of symmetric eigenvalue problems using multigrid preconditioners in the locally optimal block conjugate gradient method, Electron. Trans. Numer. Anal., 15 (2003), pp. 38-55. · Zbl 1031.65126
[24] Q. Lin and H. Xie, A multi-level correction scheme for eigenvalue problems, Math. Comp., 84 (2015), pp. 71-88. · Zbl 1307.65159
[25] S. F. McCormick, ed., Multigrid Methods, SIAM Frontiers in Applied Mathematics 3, SIAM, Philadelphia, 1987. · Zbl 0659.65094
[26] Y. Saad, Numerical Methods for Large Eigenvalue Problems, SIAM, Philadelphia, 2011. · Zbl 1242.65068
[27] L. R. Scott and S. Zhang, Higher dimensional non-nested multigrid methods, Math. Comp., 58 (1992), pp. 457-466. · Zbl 0772.65077
[28] V. V. Shaidurov, Multigrid Methods for Finite Element, Kluwer Academic Publishers, Norwell, MA, 1995. · Zbl 0837.65118
[29] D. Sorensen, Implicitly Restarted Arnoldi/Lanczos Methods for Large Scale Eigenvalue Calculations, Springer, Berlin, 1997. · Zbl 0865.65019
[30] G. Strang and G. J. Fix, An Analysis of the Finite Element Method, Prentice Hall, Englewood Cliffs, NJ, 1973. · Zbl 0356.65096
[31] A. Toselli and O. Widlund, Domain Decomposition Methods: Algorithm and Theory, Springer-Verlag, Berlin, 2005. · Zbl 1069.65138
[32] H. Xie, A type of multilevel method for the Steklov eigenvalue problem, IMA J. Numer. Anal., 34 (2014), pp. 592-608. · Zbl 1312.65178
[33] H. Xie, A multigrid method for eigenvalue problem, J. Comput. Phys., 274 (2014), pp. 550-561. · Zbl 1352.65631
[34] H. Xie, L. Zhang, and H. Owhadi, Fast eigenvalue computation with operator adapted wavelets and hierarchical subspace correction, SIAM J. Numer. Anal., 57 (2019), pp. 2519-2550. · Zbl 1447.65165
[35] J. Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev., 34 (1992), pp. 581-613. · Zbl 0788.65037
[36] J. Xu, A new class of iterative methods for nonselfadjoint or indefinite problems, SIAM J. Numer. Anal., 29 (1992), pp. 303-319. · Zbl 0756.65050
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.