Parallel Krylov solvers for the polynomial eigenvalue problem in SLEPc. (English) Zbl 1352.65116
Summary: Polynomial eigenvalue problems are often found in scientific computing applications. When the coefficient matrices of the polynomial are large and sparse, usually only a few eigenpairs are required and projection methods are the best choice. We focus on Krylov methods that operate on the companion linearization of the polynomial but exploit the block structure with the aim of being memory-efficient in the representation of the Krylov subspace basis. The problem may appear in the form of a low-degree polynomial (quartic or quintic, say) expressed in the monomial basis, or a high-degree polynomial (coming from interpolation of a nonlinear eigenproblem) expressed in a nonmonomial basis. We have implemented a parallel solver in SLEPc covering both cases that is able to compute exterior as well as interior eigenvalues via spectral transformation. We discuss important issues such as scaling and restart and illustrate the robustness and performance of the solver with some numerical experiments.
MSC:
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 65F50 | Computational methods for sparse matrices |
| 65Y05 | Parallel numerical computation |
| 15A54 | Matrices over function rings in one or more variables |
Keywords:
matrix polynomial; eigenvalues; companion linearization; Krylov subspace; nonmonomial bases; spectral transformation; parallel computing; SLEPc; projection methods; numerical experimentsReferences:
| [1] | P. R. Amestoy, I. S. Duff, J.-Y. L’Excellent, and J. Koster, {\it A fully asynchronous multifrontal solver using distributed dynamic scheduling}, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 15-41. · Zbl 0992.65018 |
| [2] | A. Amiraslani, D. A. Aruliah, and R. M. Corless, {\it Block LU factors of generalized companion matrix pencils}, Theoret. Comput. Sci., 381 (2007), pp. 134-147. · Zbl 1140.65032 |
| [3] | A. Amiraslani, R. M. Corless, and P. Lancaster, {\it Linearization of matrix polynomials expressed in polynomial bases}, IMA J. Numer. Anal., 29 (2009), pp. 141-157. · Zbl 1158.15022 |
| [4] | Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, eds., {\it Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide}, SIAM, Philadelphia, 2000. · Zbl 0965.65058 |
| [5] | Z. Bai and Y. Su, {\it SOAR: A second-order Arnoldi method for the solution of the quadratic eigenvalue problem}, SIAM J. Matrix Anal. Appl., 26 (2005), pp. 640-659. · Zbl 1080.65024 |
| [6] | S. Balay, S. Abhyankar, M. Adams, J. Brown, P. Brune, K. Buschelman, L. Dalcin, V. Eijkhout, W. Gropp, D. Kaushik, M. Knepley, L. Curfman McInnes, K. Rupp, B. Smith, S. Zampini, and H. Zhang, {\it PETSc Users Manual}, Tech. Report ANL-95/11-Revision 3.6, Argonne National Laboratory, 2015. |
| [7] | T. Betcke, {\it Optimal scaling of generalized and polynomial eigenvalue problems}, SIAM J. Matrix Anal. Appl., 30 (2008), pp. 1320-1338. · Zbl 1176.65038 |
| [8] | T. Betcke, N. J. Higham, V. Mehrmann, C. Schröder, and F. Tisseur, {\it NLEVP: A collection of nonlinear eigenvalue problems}, ACM Trans. Math. Software, 39 (2013), pp. 7:1-7:28. · Zbl 1295.65140 |
| [9] | T. Betcke and D. Kressner, {\it Perturbation, extraction and refinement of invariant pairs for matrix polynomials}, Linear Algebra Appl., 435 (2011), pp. 514-536. · Zbl 1228.15008 |
| [10] | C. Campos and J. E. Roman, {\it Parallel iterative refinement in polynomial eigenvalue problems}, Numer. Linear Algebra Appl. (2016). · Zbl 1413.65091 |
| [11] | C. Effenberger and D. Kressner, {\it Chebyshev interpolation for nonlinear eigenvalue problems}, BIT, 52 (2012), pp. 933-951. · Zbl 1263.65048 |
| [12] | H. Fan, W. Lin, and P. Van Dooren, {\it Normwise scaling of second order polynomial matrices}, SIAM J. Matrix Anal. Appl., 26 (2004), pp. 252-256. · Zbl 1088.15010 |
| [13] | I. Gohberg, P. Lancaster, and L. Rodman, {\it Matrix Polynomials}, Academic Press, New York, 1982. · Zbl 0482.15001 |
| [14] | S. Hammarling, C. J. Munro, and F. Tisseur, {\it An algorithm for the complete solution of quadratic eigenvalue problems}, ACM Trans. Math. Software, 39 (2013), pp. 18:1-18:19. · Zbl 1295.65060 |
| [15] | V. Hernandez, J. E. Roman, and A. Tomas, {\it Parallel Arnoldi eigensolvers with enhanced scalability via global communications rearrangement}, Parallel Comput., 33 (2007), pp. 521-540. |
| [16] | V. Hernandez, J. E. Roman, and V. Vidal, {\it SLEPc: A scalable and flexible toolkit for the solution of eigenvalue problems}, ACM Trans. Math. Software, 31 (2005), pp. 351-362. · Zbl 1136.65315 |
| [17] | N. J. Higham, R.-C. Li, and F. Tisseur, {\it Backward error of polynomial eigenproblems solved by linearization}, SIAM J. Matrix Anal. Appl., 29 (2007), pp. 1218-1241. · Zbl 1159.65042 |
| [18] | M. Hochbruck and D. Lochel, {\it A multilevel Jacobi-Davidson method for polynomial PDE eigenvalue problems arising in plasma physics}, SIAM J. Sci. Comput., 32 (2010), pp. 3151-3169. · Zbl 1278.76131 |
| [19] | F.-N. Hwang, Z.-H. Wei, T.-M. Huang, and W. Wang, {\it A parallel additive Schwarz preconditioned Jacobi-Davidson algorithm for polynomial eigenvalue problems in quantum dot simulation}, J. Comput. Phys., 229 (2010), pp. 2932-2947. · Zbl 1187.65034 |
| [20] | D. Kressner, {\it A block Newton method for nonlinear eigenvalue problems}, Numer. Math., 114 (2009), pp. 355-372. · Zbl 1191.65054 |
| [21] | D. Kressner and J. E. Roman, {\it Memory-efficient Arnoldi algorithms for linearizations of matrix polynomials in Chebyshev basis}, Numer. Linear Algebra Appl., 21 (2014), pp. 569-588. · Zbl 1340.65059 |
| [22] | D. Lu and Y. Su, {\it Two-Level Orthogonal Arnoldi Process for the Solution of Quadratic Eigenvalue Problems}, manuscript, 2012. |
| [23] | D. S. Mackey, N. Mackey, C. Mehl, and V. Mehrmann, {\it Vector spaces of linearizations for matrix polynomials}, SIAM J. Matrix Anal. Appl., 28 (2006), pp. 971-1004. · Zbl 1132.65027 |
| [24] | K. Meerbergen, {\it The Quadratic Arnoldi method for the solution of the quadratic eigenvalue problem}, SIAM J. Matrix Anal. Appl., 30 (2008), pp. 1463-1482. · Zbl 1176.65041 |
| [25] | J. E. Roman, C. Campos, E. Romero, and A. Tomas, {\it SLEPc Users Manual}, Tech. report DSIC-II/24/02-Revision 3.6, D. Sistemes Informàtics i Computació, Universitat Politècnica de València, 2015. |
| [26] | G. W. Stewart, {\it A Krylov-Schur algorithm for large eigenproblems}, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 601-614. · Zbl 1003.65045 |
| [27] | Y. Su, J. Zhang, and Z. Bai, {\it A compact Arnoldi algorithm for polynomial eigenvalue problems}, \newblock presented at RANMEP, 2008. |
| [28] | F. Tisseur, {\it Backward error and condition of polynomial eigenvalue problems}, Linear Algebra Appl., 309 (2000), pp. 339-361. · Zbl 0955.65027 |
| [29] | F. Tisseur and K. Meerbergen, {\it The quadratic eigenvalue problem}, SIAM Rev., 43 (2001), pp. 235-286. · Zbl 0985.65028 |
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.
