zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
A method based on Rayleigh quotient gradient flow for extreme and interior eigenvalue problems. (English) Zbl 1186.65043

Summary: Recently, a continuous method has been proposed by G. H. Golub and L.-Z. Liao [ibid. 145, No. 1, 31–51 (2006; Zbl 1092.65029)] as an alternative way to solve the minimum and interior eigenvalue problems. According to their numerical results, their method seems promising. This article is an extension along this line.

In this article, firstly, we convert an eigenvalue problem to an equivalent constrained optimization problem. Secondly, using the Karush-Kuhn-Tucker conditions of this equivalent optimization problem, we obtain a variant of the Rayleigh quotient gradient flow, which is formulated by a system of differential-algebraic equations. Thirdly, based on the Rayleigh quotient gradient flow, we give a practical numerical method for the minimum and interior eigenvalue problems. Finally, we also give some numerical experiments of our method, the Golub and Liao method, and EIGS (a Matlab implementation for computing eigenvalues using restarted Arnoldi’s method) for some typical eigenvalue problems. Our numerical experiments indicate that our method seems promising for most test problems.

MSC:
65F15Eigenvalues, eigenvectors (numerical linear algebra)
65K05Mathematical programming (numerical methods)
65K10Optimization techniques (numerical methods)
65L15Eigenvalue problems for ODE (numerical methods)
Software:
Matlab
References:
[1]Ascher, U. M.; Petzold, L. R.: Computer methods for ordinary differential equations and differential-algebraic equations, (1998) · Zbl 0908.65055
[2]Ashcraft, C.; Grimes, R. G.; Lewis, J. G.: Accurate symmetric indefinite linear equation solvers, SIAM J. Matrix anal. Appl. 20, 513-561 (1998) · Zbl 0923.65010 · doi:10.1137/S0895479896296921
[3]Botsaris, C. A.: A class of methods for unconstrained minimization based on stable numerical integration techniques, J. math. Anal. appl. 63, 729-749 (1978) · Zbl 0405.65041 · doi:10.1016/0022-247X(78)90068-9
[4]Brown, A. A.; Bartholomew-Biggs, M. C.: Some effective methods for unconstrained optimization based on the solution of systems of ordinary differential equations, J. optim. Theory appl. 62, 211-224 (1989) · Zbl 0651.90067 · doi:10.1007/BF00941054
[5]Coffey, T. S.; Kelley, C. T.; Keyes, D. E.: Pseudotransient continuation and differential-algebraic equations, SIAM J. Sci. comput. 25, 553-569 (2003) · Zbl 1048.65080 · doi:10.1137/S106482750241044X
[6]Deuflhard, P.: Newton methods for nonlinear problems: affine invariance and adaptive algorithms, (2004)
[7]Duff, I. S.: MA57-a code for the solution of sparse symmetric definite and indefinite systems, ACM trans. Math. software 30, 118-144 (2004) · Zbl 1070.65525 · doi:10.1145/992200.992202
[8]Fletcher, R.: Practical methods of optimization, vol. 1: unconstrained optimization, (1980)
[9]Fletcher, R.: Practical methods of optimization, vol. 2: constrained optimization, (1981)
[10]Fiacco, A. V.; Mccormick, G. P.: Nonlinear programming: sequential unconstrained minimization techniques, (1968) · Zbl 0193.18805
[11]Golub, G. H.; Liao, L. -Z.: Continuous methods for extreme and interior eigenvalue problems, Linear algebra appl. 415, 31-51 (2006) · Zbl 1092.65029 · doi:10.1016/j.laa.2005.01.009
[12]Gao, X. -B.; Golub, G. H.; Liao, L. -Z.: Continuous methods for symmetric generalized eigenvalue problems, Linear algebra appl. 428, 676-696 (2008) · Zbl 1140.65029 · doi:10.1016/j.laa.2007.08.034
[13]Gear, C. W.: Numerical initial value problems in ordinary differential equations, (1971) · Zbl 1145.65316
[14]Golub, G. H.; Van Loan, C. F.: Matrix computation, (1996)
[15]Gould, N. I. M.; Scott, J. A.; Hu, Y. -F.: A numerical evaluation of sparse direct solvers for the solution of large sparse symmetric linear systems of equations, ACM trans. Math. software 33, 1-32 (2007)
[16]Hairer, E.; Wanner, G.: Solving ordinary differential equations II, stiff and differential-algebraic problems, (1996)
[17]He, B. -S.: Solving trust region problem in large scale optimization, J. comput. Math. 18, 1-12 (2000) · Zbl 0951.65055
[18]Helmke, U.; Moore, J. B.: Optimization and dynamical systems, (1996)
[19]Higham, D. J.: Trust region algorithms and timestep selection, SIAM J. Numer. anal. 37, 194-210 (1999) · Zbl 0945.65068 · doi:10.1137/S0036142998335972
[20]Kelley, C. T.; Keyes, D. E.: Convergence analysis of pseudo-transient continuation, SIAM J. Numer. anal. 35, 508-523 (1998) · Zbl 0911.65080 · doi:10.1137/S0036142996304796
[21]Levenberg, K.: A method for the solution of certain problems in least squares, Q. appl. Math. 2, 164-168 (1944) · Zbl 0063.03501
[22]Luo, X. -L.; Liao, L. -Z.; Tam, H. -W.: Convergence analysis of Levenberg-Marquardt methods, Optim. methods softw. 22, 659-678 (2007) · Zbl 1186.90110 · doi:10.1080/10556780601079233
[23]Luo, X. -L.; Kelley, C. T.; Liao, L. -Z.; Tam, H. -W.: Combining trust-region techniques and rosenbrock methods to compute stationary points, J. optim. Theory appl. 140, 265-286 (2009) · Zbl 1190.90213 · doi:10.1007/s10957-008-9469-0
[24]Luo, X. -L.: A trajectory-following method for solving the steady state of chemical reaction rate equations, J. theor. Comput. chem. 8, 1039-1058 (2009)
[25]Lehoucq, R. B.; Sorensen, D. C.: Deflation techniques for an implicitly re-started arnoldi iteration, SIAM J. Matrix anal. Appl. 17, 789-821 (1996) · Zbl 0863.65016 · doi:10.1137/S0895479895281484
[26]Marquardt, D.: An algorithm for least-squares estimation of nonlinear parameters, SIAM J. Appl. math. 11, 431-441 (1963) · Zbl 0112.10505 · doi:10.1137/0111030
[27]MATLAB R2008a, The MathWorks Inc. lt;http://www.mathworks.comgt;, 2008.
[28]Matrix Market. lt;http://math.nist.gov/MatrixMarketgt;.
[29]Nocedal, J.; Wright, S. J.: Numerical optimization, (1999)
[30]Schropp, J.: Geometric properties of Runge – Kutta discretizations for index 2 differential algebraic equations, SIAM J. Numer. anal. 40, 872-890 (2002) · Zbl 1053.65062 · doi:10.1137/S0036142900376626
[31]Schropp, J.: One- and multistep discretizations of index 2 differential algebraic systems and their use in optimization, J. comput. Appl. math. 150, 375-396 (2003) · Zbl 1019.65063 · doi:10.1016/S0377-0427(02)00671-4
[32]Shampine, L. F.; Reichelt, M. W.: The Matlab ODE suite, SIAM J. Sci. comput. 18, 1-22 (1997) · Zbl 0868.65040 · doi:10.1137/S1064827594276424
[33]Zirilli, F.: The use of ordinary differential equations in the solution of nonlinear systems of equations, Nonlinear optimization, 39-47 (1981) · Zbl 0545.65033