UMD AMSC 663 - Finding Rightmost Eigenvalues of Large, Sparse, Nonsymmetric Parameterized Eigenvalue Problems (16 pages)

Previewing pages 1, 2, 3, 4, 5 of 16 page document View the full content.
View Full Document

Finding Rightmost Eigenvalues of Large, Sparse, Nonsymmetric Parameterized Eigenvalue Problems



Previewing pages 1, 2, 3, 4, 5 of actual document.

View the full content.
View Full Document
Unformatted text preview:

Finding Rightmost Eigenvalues of Large Sparse Nonsymmetric Parameterized Eigenvalue Problems Minghao Wu AMSC Program mwu math umd edu Advisor Dr Howard Elman Department of Computer Science elman cs umd edu Motivation To determine the stability of the linearized system of the form Bx Ax The steady state solution x is stable if all the eigenvalues of Ax Bx have negative real parts unstable otherwise 2 Problem Statement To find the rightmost eigenvalues of Ax Bx where matrices A and B are Real N by N Large Sparse Nonsymmetric Depend on one or several parameters 3 Method Eigensolver Arnoldi Algorithm Iterative method Based on Krylov subspace K k A u1 u1 Au1 A2u1 Ak 1u1 Computes Arnoldi decomposition AU k U k H k k uk 1ekT where Uk uk 1 an orthonormal basis of u 1 Au1 Ak u1 Hk k by k upper Hessenberg matrix k N k scalar ek k by 1 vector 0 0 0 1 4 Arnoldi Algorithm continue Eigenvalues of Hk approximate eigenvalues of A Premultiply previous equation by transpose Uk U kT AU k U kTU k H k kU kT uk 1ekT H k Let z be an eigenpair of Hk then U kT A U k z H k z z U kT U k z U kT U k z U kT A U k z U k z 0 Residual As k increases Residual will decrease When k N Residual 0 5 Matrix Transformation Motivation Arnoldi Algorithm cannot solve generalized eigenvalue problem It converges to well separated extremal eigenvalues not rightmost eigenvalues Shift Invert Transformation 1 TSI A B A B B Ax Bx TSI x x 1 6 Matlab Code of Arnoldi Method Arnoldi Algorithm with Shift Invert matrix transformation routine v X U H SI Arnoldi A B k sigma Input A B matrix A and B in Ax Bx k number of eigenpairs wanted sigma the shift in shift invert matrix transformation Output v a vector of k computed eigenvalues X k eigenvectors associated with the eigenvalues U the Krylov basis Uk 1 H the upper Hessenberg matrix Hk 7 Test Problem Olmstead Model see Olmstead et al 1986 ut S xx cu xx Ru u 3 bSt 1 c u S with boundary conditions u S 0 x 0 This model represents the flow of a layer of viscoelastic fluid heated from below u the speed of the fluid S related to viscoelastic forces b c scalars R scalar Rayleigh number 8 Test Problem continue Discretize the model with finite differences grid size h 1 N 2 4 can be written as dy dt f y with y T u1 S1 u2 S 2 u N 2 S N 2 Evaluate the Jacobian matrix A df dy at steady state solution y N 1000 b 2 c 0 1 R 0 6 y 0 A df dy y is a nonsymmetric sparse matrix with bandwidth 6 9 Test Problem continue Computational Result Rightmost eigenvalues 1 2 0 0 4472i Residual Axi i xi 8 4504e 012 i 1 2 The result agrees with the literature 10 Implicitly Restarted Arnoldi IRA Motivation Large k is not practical Example Size of A 10 000 Value of k 100 Memory required to store U100 in 10 MB double precision When B is singular Arnoldi algorithm may give rise to spurious eigenvalues 11 IRA continue Basic idea of Implicitly Restarted Arnoldi Filter out the unwanted eigendirections from the starting vector by using the most recent spectrum information and a clever filtering technique IRA steps 1 Compute m eigenpairs k m N by Arnoldi method with starting vector u1 2 Filter out the m k unwanted eigendirections from u1 Key Technique shifted QR algorithm 3 Restart the process with filtered starting vector till the k eigenvalues of interest converge 12 Test Problem K C T C x 0 M 0 0 x 0 K 200 by 200 matrix full rank C 200 by 100 matrix full rank M 200 by 200 matrix full rank Eigenvalue problem with this kind of block structure appears in the stability analysis of steady state solution of Navier Stokes equations for incompressible flow 13 Test Problem continue Use Matlab function rand to generate K C M 2 7377 Re 49 9129 Find out 10 rightmost eigenvalues Use the IRA code written by Fei Xue 14 Test Problem continue Computational Result shift 60 Exact Eigenavalues Computed Eigenavalues IRA Computed Eigenavalues Arnoldi 49 9129 0i 49 9129 0i 2 9112 1 1256i 2 9112 1 1256i 193 8412 7113830 9524i 2 9112 1 1256i 2 9112 1 1256i 193 8412 7113830 9524i 2 5036 0 0624i 2 5036 0 0624i 3 0891 0i 2 5036 0 0624i 2 5036 0 0624i 2 6112 0i 2 3792 0i 2 3792 0i 0 5752 2 7079i 2 1318 0 9356i 2 1318 0 9356i 0 5752 2 7079i 2 1318 0 9356i 2 1318 0 9356i 1 0901 0 7532i 2 1081 1 3539i 2 1081 1 3539i 1 0901 0 7532i 2 1081 1 3539i 2 1081 1 3539i 47 3106 0i 49 9129 0i 15 Future Work AMSC 664 Solve the third test problem Implement iterative solvers for linear systems 16


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Finding Rightmost Eigenvalues of Large, Sparse, Nonsymmetric Parameterized Eigenvalue Problems and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Finding Rightmost Eigenvalues of Large, Sparse, Nonsymmetric Parameterized Eigenvalue Problems and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?