Share Pdf : Advances In Algebraic Nonlinear Eigenvalue Problems

Download and Preview : Advances In Algebraic Nonlinear Eigenvalue Problems

Report CopyRight/DMCA Form For : Advances In Algebraic Nonlinear Eigenvalue Problems

## Transcription

I Part 1 Linear eigenvalue problems, I Part 2 Nonlinear eigenvalue problems. I Part 3 Eigenvalue problems with eigenvector nonlinearity. Outline cont d, I Part 1 Linear eigenvalue problems. 1 Accelerated subspace iteration, 2 Steepest descent method. 3 Arnoldi method, 4 Rational Krylov method, 5 Topics of more recent interest. I Part 2 Nonlinear eigenvalue problems, 1 Essential theory.

2 Methods based on Newton iteration, 3 Methods specially designed for QEP and REP. 4 Methods based on approximation and linearization. 5 Of things not treated, I Part 3 Eigenvalue problems with eigenvector nonlinearity. 1 Kohn Sham density functional theory, 2 Sum of trace ratio. 3 Robust Rayleigh quotient optimization, 4 Of things not treated. Part 1 Linear eigenvalue problems, Getting started.

1 Standard Linear eigenvalue problems, where A Cn n. 2 Generalized linear eigenvalue problems, where A B Cn n. 3 Generalized Hermitian definite linear eigenvalue problems. where A B Cn n and A A and B B 0, 4 Textbooks and monographs for examples. I B Parlett The Symmetric Eigenvalue Problem revised edition SIAM 1998 first. edition 1982, I Y Saad Numerical Methods for Large Eigenvalue Problems revised edition SIAM 2011. first edition 1992, I G W Stewart Matrix Algorithms Vol II Eigensystems SIAM 2001.

I G Golub and C Van Loan Matrix Computations 4th Ed John Hopkins University. Press 2013 Chapters 7 8 10, I J Demmel Applied Numerical Linear Algebra SIAM 1997 Chapters 4 5 7. I G W Stewart and J G Sun Matrix Perturbation Theory Academic Press 1990. I J G Sun Matrix Perturbation Analysis 2nd edition Science Press 2001 in Chinese. I Textbooks in Chinese, I Z Bai J Demmel J Dongarra A Ruhe and H van der Vorst editors Templates for. the solution of Algebraic Eigenvalue Problems A Practical Guide SIAM Philadelphia. 2000 available at http web cs ucdavis edu bai ET contents html. Outline of Part 1, 1 Accelerated subspace iteration. 2 Steepest descent method, 3 Arnoldi method, 4 Rational Krylov method. 5 Topics of more recent interest, a Computing many eigenpairs of a Hermitian matrix.

b Solving ill conditioned generalized symmetric definite eigenvalue problems. Part 1 1 Accelerated subspace iteration, 1 Consider the generalized Hermitian definite eigenvalue problem. where A B Cn n A A and B B 0 x is an eigenpair of the pencil. 2 Eigenvalue decomposition there exists an n n nonsingular matrix X such that. AX BX and X BX I, where is a real diagonal matrix and X is called B orthogonal Each diagonal. entry of with its corresponding vector x of X constitute an eigenpair of the. matrix pencil A B, 3 Mathematically determining eigenpairs for the generalized eigenproblem of A B. is equivalent to determining eigenpairs of the single matrix B 1 A Define. M B 1 A X X 1 X X B, 4 Accelerated subspace iteration with Rayleigh Ritz projection. 1 choose vector Q0 Cn k Q 0 Q0 I, 2 for j 1 2 do, 3 compute Yj M Qj 1.

4 compute A bj Y AYj and Bbj Y BYj, compute the eigen decomposition A bj X. bj Xbj bj and Xb B, 5 j j Xj I, 6 set Qj Yj X bj, 7 test for convergence of approximate eigenpairs bj Qj. 5 Acceleration filter functions, a Ideal accelerator filter spectral projector M XI XI B where XI is the set of. columns from the eigenvector matrix X corresponding to the eigenvectors of interest Ex. verify that it converges in one step, b Classical subspace iteration M M. c Multiple step subspace iteration M M q for some integer q 1. d Chebyshev subspace iteration M pq M where pq is a scaled Chebyshev. polynomial of degree q of the first kind, e Rational filters contour integral FEAST.

I P T P Tang and E Polizzi FEAST as a subspace iteration eigensolver accelerated by. approximate spectral projection SIMAX 35 pp 354 390 2014. f ARRABIT Augmented Rayleigh Ritz And Block ITeration. I Z Wen and Y Zhang Block algorithms with augmented Rayleigh Ritz projections for large scale. eigenpair computation arXiv 1507 06078v1 July 22 2015. g Zolotarev s best rational function approximation of the signum function. I Y Li and H Yang Spectrum slicing for sparse Hermitian definite matrices based on Zolotarev s. functions arXiv 1701 08935v2 Feb 28 2017, 6 matlab script demo RayleighRitz m. Part 1 2 Steepest descent method, 1 Consider the generalized Hermitian definite eigenvalue problem Ax Bx let. eigenvalues i be ordered such that 1 2 n, 2 Rayleigh quotient x. 3 Courant Fischer min max principle, i min max x, X dim X i x X. In particular 1 minn x, 4 Ky Fan trace min principle.

i min trace X AX, 5 Cauchy interlacing property Let 1 2 k be the eigenvalues of the. pencil W AW W BW where W Cn k and rank W k then, j j j n k for 1 j k. 6 The Steepest Descent SD is a general technique to solve minx f x. 7 Recall 1 minx x, I Gradient x Ax x Bx, I SD direction x parallels to the residual r x Ax x Bx. I Line search plain SD x xc t r xc where t argmint xc t r xc. 8 The SD method subspace projection version, 1 choose a vector x0. 2 compute x0 x0 kx0 kB 0 x 0 Ax0 and r0 Ax0 0 Bx0, 3 for j 0 1 2 do.

4 if krj k2 kAxj k2 j kBxj k tol then break, 5 set Z xj rj search space. 6 compute the smaller eigenvalue and corresponding eigenvector v of. 7 compute xj 1 x kx kB where x Zv, 8 set j 1 and compute the residue rj 1 Axj 1 j 1 Bxj 1. 10 return j xj as an approximate eigenpair to 1 x1. 9 Extensions, I Locally optimal conjugate gradient method LOCG of Knyazev 1991. Z span xj 1 xj A j B xj, I Extended SD method inverse free of Golub and Ye 2002. Z span xj A j B xj A j B xj, for some integer m 2, 10 Practical issues.

I Preconditioning e g, Z e span xj 1 xj K A j B xj. I Blocking, I Deflation, 11 matlab script demo SD m and demo preconditionedSD m. 12 Further reading, I R C Li Rayleigh quotient based numerical methods for eigenvalue problems Lecture. notes at Gene Golub SIAM Summer School 2013 available at. http www siam org students g2s3 2013 course html and references therein. Part 1 3 Arnoldi method, 1 Arnoldi process generates an orthonormal basis Vj of the Krylov subspace. Kj A v1 span v1 Av1 Aj 1 v1, 2 Arnoldi method for computing approximate eigenpairs of A.

1 choose vector v1 kv1 k 1, 2 for j 1 2 do, 3 compute v b Avj. 4 orthogonalize v e vb Vj hj hj Vj v, 5 get new vector vj 1 v e hj 1 j where hj 1 j ke. 6 compute the Ritz pairs i xi, 7 test for convergence. 3 Recurrence relation Arnoldi decomposition, AVj Vj Hj hj 1 j vj 1 e j Vj 1 Hj. 4 Ritz pairs i e approximate eigenpairs of A are given by i xi Vj yi where. i yi are eigenpairs of Hj Vj AVj, 5 Practical issues.

a Reorthogonalization to treat the loss of orthogonality in finite precision arithmetic. b Restarting explicit and implicit, c Deflation aka locking. d Shift and invert spectral transformation known as the shift and invert Arnoldi method. 6 matlab script demo eigs m, 7 Further reading covered in the most textbooks. Advances in Algebraic Nonlinear Eigenvalue Problems Zhaojun Bai University of California Davis with the assistance of Ding Lu of University of Geneva Lecture notes prepared for LSEC Summer School July 24 August 5 2017 Version August 5 2017 1 183 Outline I Part 1 Linear eigenvalue problems I Part 2 Nonlinear eigenvalue problems I Part 3 Eigenvalue problems with eigenvector