×

A prediction-correction dynamic method for large-scale generalized eigenvalue problems. (English) Zbl 1470.65061

Summary: This paper gives a new prediction-correction method based on the dynamical system of differential-algebraic equations for the smallest generalized eigenvalue problem. First, the smallest generalized eigenvalue problem is converted into an equivalent-constrained optimization problem. Second, according to the Karush-Kuhn-Tucker conditions of this special equality-constrained problem, a special continuous dynamical system of differential-algebraic equations is obtained. Third, based on the implicit Euler method and an analogous trust-region technique, a prediction-correction method is constructed to follow this system of differential-algebraic equations to compute its steady-state solution. Consequently, the smallest generalized eigenvalue of the original problem is obtained. The local superlinear convergence property for this new algorithm is also established. Finally, in comparison with other methods, some promising numerical experiments are presented.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65L80 Numerical methods for differential-algebraic equations
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Auckenthaler, T.; Auckenthaler, T.; Bungartz, H.-J., Parallel solution of partial symmetric eigenvalue problems from electronic structure calculations, Parallel Computing, 37, 11, 783-794, (2011)
[2] Saad, Y., Numerical Methods for Large Eigenvalue Problems. Numerical Methods for Large Eigenvalue Problems, Algorithms and Architectures for Advanced Scientific Computing, (1992), Manchester, England: Manchester University Press, Manchester, England
[3] Golub, G. H.; Liao, L.-Z., Continuous methods for extreme and interior eigenvalue problems, Linear Algebra and its Applications, 415, 1, 31-51, (2006) · Zbl 1092.65029
[4] Gao, X.-B.; Golub, G. H.; Liao, L.-Z., Continuous methods for symmetric generalized eigenvalue problems, Linear Algebra and its Applications, 428, 2-3, 676-696, (2008) · Zbl 1140.65029
[5] Helmke, U.; Moore, J. B., Optimization and Dynamical Systems, (1996), Springer · Zbl 0943.93001
[6] Mahony, R.; Absil, P.-A., The continuous-time Rayleigh quotient flow on the sphere, Linear Algebra and its Applications, 368, 343-357, (2003) · Zbl 1030.65025
[7] Gear, C. W., Numerical Initial Value Problems in Ordinary Differential Equations, (1971), Englewood Cliffs, NJ, USA: Prentice-Hall, Englewood Cliffs, NJ, USA · Zbl 1145.65316
[8] He, B.; Yuan, X.; Zhang, J. J. Z., Comparison of two kinds of prediction-correction methods for monotone variational inequalities, Computational Optimization and Applications, 27, 3, 247-267, (2004) · Zbl 1061.90111
[9] He, B.; Yuan, X., On the \(O(1 / n)\) convergence rate of the Douglas-Rachford alternating direction method, SIAM Journal on Numerical Analysis, 50, 2, 700-709, (2012) · Zbl 1245.90084
[10] Nocedal, J.; Wright, S. J., Numerical Optimization. Numerical Optimization, Springer Series in Operations Research, (1999), New York, NY, USA: Springer, New York, NY, USA · Zbl 0930.65067
[11] Ascher, U. M.; Petzold, L. R., Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations, (1998), Philadelphia, Pa, USA: Society for Industrial and Applied Mathematics, Philadelphia, Pa, USA · Zbl 0908.65055
[12] Shampine, L. F.; Reichelt, M. W., The Matlab ODE suite, SIAM Journal on Scientific Computing, 18, 1, 1-22, (1997) · Zbl 0868.65040
[13] Liu, S.-T.; Luo, X.-L., A method based on Rayleigh quotient gradient flow for extreme and interior eigenvalue problems, Linear Algebra and its Applications, 432, 7, 1851-1863, (2010) · Zbl 1186.65043
[14] Ng, M. K.; Wang, F.; Yuan, X., Inexact alternating direction methods for image recovery, SIAM Journal on Scientific Computing, 33, 4, 1643-1668, (2011) · Zbl 1234.94013
[15] Kelley, C. T.; Liao, L.-Z.; Qi, L.; Chu, M. T.; Reese, J. P.; Winton, C., Projected pseudotransient continuation, SIAM Journal on Numerical Analysis, 46, 6, 3071-3083, (2008) · Zbl 1180.65060
[16] Luo, X. L., A dynamical method of DAEs for the smallest eigenvalue problem, Journal of Computational Science, 3, 3, 113-119, (2012)
[17] Parlett, B. N., The Symmetric Eigenvalue Problem. The Symmetric Eigenvalue Problem, Classics in Applied Mathematics, (1998), Philadelphia, Pa, USA: Society for Industrial and Applied Mathematics, Philadelphia, Pa, USA · Zbl 0885.65039
[19] Fokkema, D. R.; Sleijpen, G. L. G.; Van der Vorst, H. A., Jacobi-Davidson style QR and QZ algorithms for the reduction of matrix pencils, SIAM Journal on Scientific Computing, 20, 1, 94-125, (1998) · Zbl 0924.65027
[21] Zhang, T.; Law, K. H.; Golub, G. H., On the homotopy method for perturbed symmetric generalized eigenvalue problems, SIAM Journal on Scientific Computing, 19, 5, 1625-1645, (1998) · Zbl 0917.65035
[23] Luo, X.-l., A second-order pseudo-transient method for steady-state problems, Applied Mathematics and Computation, 216, 6, 1752-1762, (2010) · Zbl 1197.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. 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.