×

Subspace acceleration for large-scale parameter-dependent Hermitian eigenproblems. (English) Zbl 1382.65104

Summary: This work is concerned with approximating the smallest eigenvalue of a parameter-dependent Hermitian matrix \(A(\mu)\) for many parameter values \(\mu\) in a domain \(D\subset \mathbb{R}^P\). The design of reliable and efficient algorithms for addressing this task is of importance in a variety of applications. Most notably, it plays a crucial role in estimating the error of reduced basis methods for parametrized partial differential equations. The current state-of-the-art approach, the so-called successive constraint method (SCM), addresses affine linear parameter dependencies by combining sampled Rayleigh quotients with linear programming techniques. In this work, we propose a subspace approach that additionally incorporates the sampled eigenvectors of \(A(\mu)\) and implicitly exploits their smoothness properties. Like SCM, our approach results in rigorous lower and upper bounds for the smallest eigenvalues on \(D\). Theoretical and experimental evidence is given to demonstrate that our approach represents a significant improvement over SCM in the sense that the bounds are often much tighter, at negligible additional cost.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15B57 Hermitian, skew-Hermitian, and related matrices
15A18 Eigenvalues, singular values, and eigenvectors
47A55 Perturbation theory of linear operators

Software:

lobpcg.m; rbMIT; ARPACK
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] R. Andreev and C. Schwab, {\it Sparse tensor approximation of parametric eigenvalue problems}, in Numerical Analysis of Multiscale Problems, Lect. Notes Comput. Sci. Eng. 83, Springer, Heidelberg, 2012, pp. 203-241. · Zbl 1248.65116
[2] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, eds., {\it Templates for the Solution of Algebraic Eigenvalue Problems}, Software, Environ. Tools 11, SIAM, Philadelphia, 2000.
[3] M. Barrault, Y. Maday, N. C. Nguyen, and A. T. Patera, {\it An “empirical interpolation” method: Application to efficient reduced-basis discretization of partial differential equations}, C. R. Math. Acad. Sci. Paris, 339 (2004), pp. 667-672. · Zbl 1061.65118
[4] T. Betcke and L. N. Trefethen, {\it Reviving the method of particular solutions}, SIAM Rev., 47 (2005), pp. 469-491. · Zbl 1077.65116
[5] C. Davis and W. M. Kahan, {\it The rotation of eigenvectors by a perturbation.} III, SIAM J. Numer. Anal., 7 (1970), pp. 1-46. · Zbl 0198.47201
[6] J. De Vlieger and K. Meerbergen, {\it A subspace method for unimodal symmetric eigenvalue optimization problems involving large scale matrices}, Technical report, TW616, KU Leuven, Leuven, Belgium, 2012.
[7] C. Engström, C. Hafner, and K. Schmidt, {\it Computation of lossy Bloch waves in two-dimensional photonic crystals}, J. Comput. Theor. Nanosci., 6 (2009), pp. 1-9.
[8] A. Ghosh, S. Boyd, and A. Saberi, {\it Minimizing effective resistance of a graph}, SIAM Rev., 50 (2008), pp. 37-66. · Zbl 1134.05057
[9] E. Gutkin, E. A. Jonckheere, and M. Karow, {\it Convexity of the joint numerical range: Topological and differential geometric viewpoints}, Linear Algebra Appl., 376 (2004), pp. 143-171. · Zbl 1050.15026
[10] H. Hakula, V. Kaarnioja, and M. Laaksonen, {\it Approximate methods for stochastic eigenvalue problems}, Appl. Math. Comput., 267 (2015), pp. 664-681. · Zbl 1410.60066
[11] C. Helmberg and F. Rendl, {\it A spectral bundle method for semidefinite programming}, SIAM J. Optim., 10 (2000), pp. 673-696. · Zbl 0960.65074
[12] J. S. Hesthaven, B. Stamm, and S. Zhang, {\it Efficient greedy algorithms for high-dimensional parameter spaces with applications to empirical interpolation and reduced basis methods}, ESAIM Math. Model. Numer. Anal., 48 (2014), pp. 259-283. · Zbl 1292.41001
[13] D. B. P. Huynh, D. J. Knezevic, Y. Chen, J. S. Hesthaven, and A. T. Patera, {\it A natural-norm successive constraint method for inf-sup lower bounds}, Comput. Methods Appl. Mech. Engrg., 199 (2010), pp. 1963-1975. · Zbl 1231.76208
[14] D. B. P. Huynh, N. C. Nguyen, A. T. Patera, and G. Rozza, {\it rbMIT Software [Software]}, MIT, Cambridge, 2010.
[15] D. B. P. Huynh, G. Rozza, S. Sen, and A. T. Patera, {\it A successive constraint linear optimization method for lower bounds of parametric coercivity and inf-sup stability constants}, C. R. Math. Acad. Sci. Paris, 345 (2007), pp. 473-478. · Zbl 1127.65086
[16] C. R. Johnson, {\it A Gersgorin-type lower bound for the smallest singular value}, Linear Algebra Appl., 112 (1989), pp. 1-7. · Zbl 0723.15013
[17] F. Kangal, K. Meerbergen, E. Mengi, and W. Michiels, {\it A Subspace Method for Large Scale Eigenvalue Optimization}, preprint, arXiv:1508.04214, 2015. · Zbl 1378.65090
[18] T. Kato, {\it Perturbation Theory for Linear Operators}, Classics Math., Springer-Verlag, Berlin, 1995. · Zbl 0836.47009
[19] Y. Kim and M. Mesbahi, {\it On maximizing the second smallest eigenvalue of a state-dependent graph Laplacian}, IEEE Trans. Automat. Control, 51 (2006), pp. 116-120. · Zbl 1366.05069
[20] A. V. Knyazev, {\it Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method}, SIAM J. Sci. Comput., 23 (2001), pp. 517-541. · Zbl 0992.65028
[21] D. Kressner and B. Vandereycken, {\it Subspace methods for computing the pseudospectral abscissa and the stability radius}, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 292-313. · Zbl 1306.65187
[22] P. Lancaster, {\it On eigenvalues of matrices dependent on a parameter}, Numer. Math., 6 (1964), pp. 377-387. · Zbl 0133.26201
[23] R. B. Lehoucq, D. C. Sorensen, and C. Yang, {\it ARPACK Users’ Guide}, Software Environ. Tools 6, SIAM, Philadelphia, 1998.
[24] A. S. Lewis and M. L. Overton, {\it Eigenvalue optimization}, Acta Numer., 5 (1996), pp. 149-190. · Zbl 0870.65047
[25] C.-K. Li and R.-C. Li, {\it A note on eigenvalues of perturbed Hermitian matrices}, Linear Algebra Appl., 395 (2005), pp. 183-190. · Zbl 1068.15027
[26] L. Machiels, Y. Maday, I. B. Oliveira, A. T. Patera, and D. V. Rovas, {\it Output bounds for reduced-basis approximations of symmetric positive definite eigenvalue problems}, C. R. Math. Acad. Sci. Paris, 331 (2000), pp. 153-158. · Zbl 0960.65063
[27] A. Manzoni and F. Negri, {\it Heuristic strategies for the approximation of stability factors in quadratically nonlinear parametrized PDEs}, Adv. Comput. Math., 41 (2015), pp. 1255-1288. · Zbl 1336.76020
[28] J. C. Mason and D. C. Handscomb, {\it Chebyshev Polynomials}, Chapman & Hall/CRC, Boca Raton, FL, 2003.
[29] J. Matousek and B. Gärtner, {\it Understanding and Using Linear Programming}, Springer, Berlin, 2007. · Zbl 1133.90001
[30] H. Meidani and R. Ghanem, {\it Spectral power iterations for the random eigenvalue problem}, AIAA J., 52 (2014), pp. 912-925.
[31] E. Mengi, E. A. Yildirim, and M. Kiliç, {\it Numerical optimization of eigenvalues of Hermitian matrix functions}, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 699-724. · Zbl 1307.65043
[32] N. C. Nguyen, K. Veroy, and A. T. Patera, {\it Certified real-time solution of parametrized partial differential equations}, in Handbook of Materials Modeling, Springer, Dordrecht, The Netherlands, 2005, pp. 1529-1564.
[33] B. N. Parlett, {\it The Symmetric Eigenvalue Problem}, Classics Appl. Math. 20, SIAM, Philadelphia, 1998. · Zbl 0885.65039
[34] A. T. Patera and G. Rozza, {\it Reduced Basis Approximation and A Posteriori Error Estimation for Parametrized Partial Differential Equations}, MIT-Pappalardo Grad. Monogr. Mech. Eng., MIT, Cambridge, MA, 2007.
[35] C. Prud’homme, D. V. Rovas, K. Veroy, L. Machiels, Y. Maday, A. T. Patera, and G. Turinici, {\it A mathematical and computational framework for reliable real-time solution of parametrized partial differential equations}, ESAIM Math. Model. Numer. Anal., 36 (2002), pp. 747-771. · Zbl 1024.65104
[36] M. Reed and B. Simon, {\it Methods of Modern Mathematical Physics. IV. Analysis of Operators}, Academic, New York, 1978. · Zbl 0401.47001
[37] M. Rojas, S. A. Santos, and D. C. Sorensen, {\it A new matrix-free algorithm for the large-scale trust-region subproblem}, SIAM J. Optim., 11 (2001), pp. 611-646. · Zbl 0994.65067
[38] G. Rozza, D.B.P. Huynh, and A. T. Patera, {\it Reduced basis approximation and a posteriori error estimation for affinely parametrized elliptic coercive partial differential equations: Application to transport and continuum mechanics}, Arch. Comput. Methods Eng., 15 (2008), pp. 229-275. · Zbl 1304.65251
[39] S. Sen, K. Veroy, D. B. P. Huynh, S. Deparis, N. C. Nguyen, and A. T. Patera, {\it “Natural norm” a posteriori error estimators for reduced basis approximations}, J. Comput. Phys., 217 (2006), pp. 37-62. · Zbl 1100.65094
[40] L. N. Trefethen and M. Embree, {\it Spectra and Pseudospectra}, Princeton University Press, Princeton, NJ, 2005. · Zbl 1085.15009
[41] K. Veroy, D. V. Rovas, and A. T. Patera, {\it A posteriori error estimation for reduced-basis approximation of parametrized elliptic coercive partial differential equations: “Convex inverse” bound conditioners}, ESAIM Control Optim. Calc. Var., 8 (2002), pp. 1007-1028. · Zbl 1092.35031
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.