Improved Lanczos Method for the Eigenvalue Analysis of Structures

Improved Lanczos Method for the Eigenvalue Analysis of Structures 2002한국전산구조공학회 봄학술발표회 2002년 4월 13일 Byoung-Wan Kim1), Woon-Hak Kim2) and In-Won Lee3) 1) Graduate Student, Dept. of Civil and Environmental Eng., KAIST 2) Professor, Dept. of Civil Engineering, Hankyong National Univ. 3) Professor, Dept. of Civil and Environmental Eng., KAIST Introduction Matrix-powered Lanczos method Numerical examples Conclusions Contents Introduction Background Dynamic analysis of structures - Direct integration method - Mode superposition method  Eigenvalue analysis Eigenvalue analysis - Subspace iteration method - Determinant search method - Lanczos method The Lanczos method is very efficient. Literature review The Lanczos method was first proposed in 1950. Erricson and Ruhe (1980): Lanczos algorithm with shifting Smith et al. (1993): Implicitly restarted Lanczos algorithm Gambolati and Putti (1994): Conjugate gradient scheme in Lanczos method In the fields of quantum physics, Grosso et al. (1993) modified Lanczos recursion to improve convergence. Objective Application of Lanczos method using the power technique to the eigenproblem of structures in structural dynamics  Matrix-powered Lanczos method Eigenproblem of structure Matrix-powered Lanczos method Modified Gram-Schmidt process of Krylov sequence Modified Lanczos recursion Reduced tridiagonal standard eigenproblem Summary of algorithm and operation count n = order of M and K, m = half-bandwidth of M and K q = the number of calculated Lanczos vectors or order of T sj = the number of iterations of jth step in QR iteration Operation Calculation Number of operations Factorization Iteration i = 1 ··· q Substitution Multiplication Multiplication Reorthogonalization Multiplication Division Repeat Reduced eigensolution Numerical examples Simple spring-mass system (Chen 1993) Plan framed structure (Bathe and Wilson 1972) Three-dimensional frame structure (Bathe and Wilson 1972) Three-dimensional building frame (Kim and Lee 1999) Structures Physical error norm (Bathe 1996) Simple spring-mass system (DOFs: 100) System matrices  Failure in convergence due to numerical instability of high matrix power Number of operations No. of eigenpairs  = 1  = 2  = 3  = 4 2 4 6 8 10 38663 78922 120458 157649 214729 29823 58529 85712 117587 154418 26954 47567 73040 103055 138122 23653 44122 69391 99550  Plane framed structure (DOFs: 330) Geometry and properties A = 0.2787 m2 I = 8.63110-3 m4 E = 2.068107 Pa  = 5.154102 kg/m3 Number of operations  Failure in convergence due to numerical instability of high matrix power No. of eigenpairs  = 1  = 2  = 3  = 4 6 12 18 24 30 10908273 20855865 27029145 31581179 102944376 7429050 13578945 18676209 22516533 65994807 7072452 11688377 16508507 20164797 54112986 6633536 11237625 16047093   Three-dimensional frame structure (DOFs: 468) Geometry and properties E = 2.068107 Pa  = 5.154102 kg/m3 : A = 0.2787 m2, I = 8.63110-3 m4 : A = 0.3716 m2, I = 10.78910-3 m4 : A = 0.1858 m2, I = 6.47310-3 m4 : A = 0.2787 m2, I = 8.63110-3 m4 Column in front building Column in rear building All beams into x-direction All beams into y-direction Number of operations No. of eigenpairs  = 1  = 2  = 3  = 4 10 20 30 40 50 71602154 181780512 307269560 684162222 1024104917 50687925 124269611 215884077 453454527 656188310 48705515 116680070 192064376 378770940 553972908 46214349 108715163 182518601 356596304 504420108 Geometry and properties Three-dimensional building frame (DOFs: 1008) A = 0.01 m2 I = 8.310-6 m4 E = 2.11011 Pa  = 7850 kg/m3 Number of operations  Failure in convergence due to numerical instability of high matrix power No. of eigenpairs  = 1  = 2  = 3  = 4 20 40 60 80 100 395079020 1196316954 3045578295 3398746793 3536190824 278717178 801878160 1993108128 2509125474 3625240574           Conclusions Matrix-powered Lanczos method has not only the better convergence but also the less operation count than the conventional Lanczos method. The suitable power of the dynamic matrix that gives numerically stable solution in the matrix-powered Lanczos method is the second power. Thank you, Mr. Chairman. Good afternoon, Ladies and Gentlemen. My name is Byoung-Wan Kim and the title of my presentation is ‘Matrix power Lanczos method and its application to the eigensolution of structures.’ This research was conducted by Research Assistant Professor Hyun-Jo Jung, Professor In-Won Lee of the Korea Advanced Institute of Science and Technology, and myself. The outline of my presentation is as follows: Introduction, matrix power Lanczos method, numerical examples, and conclusions. The dynamic analysis is divided into two solution methods; direct integration method and mode superposition method. Eigenvalue analysis is an essential step when the mode superposition method is used. Subspace iteration method, determinant search method and Lanczos method are widely used in eigenvalue analysis. Among them, Lanczos method is very efficient. Lanczos method was first proposed in 1950 by Lanczos. To improve the method many researchers have studied various procedures as follows: In 1980, Erricson accelerated Lanczos algorithm with shifting technique. In 1993, Smith proposed restarted Lanczos algorithm. In 1994, Gambolati employed conjugate gradient scheme in Lanczos algorithm to improve convergence. Recently, my advisor Lee developed Lanczos-based algorithm for nonclassical damping system, 1999. In the fields of quantum physics, the following Lanczos recursion is used to obtain the eigenstate of quantum systems. In 1993, Grosso modified the Lanczos recursion to improve convergence with second-powered operator like this. where a and b are scalar coefficients f is basis functions H is a given operator Et is trial energy which corresponds to shift n is Lanczos step number That power technique is not applied to structural dynamics yet. The objective of this study is to apply the powered Lanczos method to the eigensolution in structural dynamics. Matrix power Lanczos method is proposed as the name in this study. Now, I’ll present the algorithm for matrix power Lanczos method. The eigenproblem of structure can be expressed as. where M and K are symmetric mass and stiffness matrix, respectively. lambdai and phii are ith eigenpair. n is order of M and K. Lanczos schemed this Gram-schmidt process about Krylov sequence to calculate Lanczos vectors. I apply the power technique to the dynamic matrix in Krylov sequence like this. where delta is a positive integer, upsilon is scalar coefficient, x0 is a trial vector, x is Lanczos vector, kmyuinversem is dynamic matrix. kmyu is k minus myum, myu is shift. Modified process contains Lanczos vectors with deltai iterated Krylov sequence, so it has better convergence than conventional process. From the modified Gram-Schmidt process, following modified Lanczos recursion can be derived. xibar,alphai,the next Lanczos vector xi+1 and betai are calculated as follows: Then, we can solve this reduced tridiagonal eigenproblem. where X is a set of Lanczos vectors and T is a tridiagonal matrix like this. QR iteration combined with inverse iteration can be used to solve the reduced eigenproblem. This table shows summary of algorithm and operation count for matrix power Lanczos method. To verify the effectiveness of the matrix power Lanczos method, a simple spring-mass system, a plan frame structure, a three-dimensional frame structure and a three-dimensional building frame are analyzed. Physical error norm like this is used to check convergence. The first example is a simple spring-mass system with ten hundred degrees of freedom. System matrices are shown. This table and this figure show the number of operations for calculating eigenpairs of simple spring-mass system. As you can see, matrix power Lanczos method has better convergence than conventional Lanczos method. In some cases, high matrix power causes failure in convergence due to numerical instability. Asterisk means such convergence failure. Convergence failure occurs in fourth power in this example. The second example is a plane framed structure with three hundred and thirty degrees of freedom. Geometry and properties are shown in this figure. This table and this figure show the number of operations for calculating eigenpairs of plane framed structure. As you can see, matrix power Lanczos method has better convergence than conventional Lanczos method. Convergence failure occurs in fourth power in this example. The third example is a three-dimensional frame structure with four hundred and sixty eight degrees of freedom. Geometry and properties are shown in this figure. This table and this figure show the number of operations for calculating eigenpairs of three-dimensional frame structure. As you can see, matrix power Lanczos method has better convergence than conventional Lanczos method. Convergence failure doesn't occur in this example. The last example is a three-dimensional building frame with one thousand eight eight degrees of freedom. Geometry and properties are shown in this figure. This table and this figure show the number of operations for calculating eigenpairs of three-dimensional building frame. Matrix power Lanczos method has better convergence than conventional Lanczos method. Convergence failures occur in third and fourth power in this example. Finally, I present the conclusions of the study. First, The convergence of matrix power Lanczos method is better than that of the conventional Lanczos method. Second, The optimal power of dynamic matrix that reduces the number of operations and gives numerically stable solution in matrix power Lanczos method is the second power.