Theory and Algorithms for Linear Eigenvalue Problems

Access to files

•   FULL-TEXT.PDF (pdf)

Abstract

In the first part of this thesis, methods for the partial solution of generalized eigenvalue problems arising from structural dynamics are studied. A natural choice for partially solving the generalized eigenvalue problem (GEP) is the Lanczos iteration, or the shift-and-invert Lanczos (SIL) algorithm if a large number of eigenpairs is required. When the external loading of the associated structural dynamics problem is specific to that of earthquake engineering, the contribution of an eigenvector of a generalized eigenvalue problem can be quantified by a simple expression. Based on this property, a novel shifting strategy for the SIL algorithm which arises from the theory of orthogonal polynomials is presented. We discuss the Lanczos algorithm and its variant suited for the partial solution of the GEP arising from structural dynamics, followed by the shift-and-invert Lanczos algorithm. Various theoretical aspects and numerical issues of these algorithms are examined and addressed. The Ritz vector and the Lanczos vector methods are also introduced. These methods use vectors other than eigenvectors for the solution of structural dynamics problems. The Ritz vector method is widely used by engineers and is often implemented in engineering software. Orthogonal polynomials and the theory required to devise a new shifting strategy for the SIL algorithm are then introduced. With a specific choice of the starting vector for the Lanczos process it becomes possible to identify the intervals of the spectrum of the associated GEP in which the eigenvalues corresponding to the eigenvectors of interest lie. The shifts for the SIL algorithm are then chosen in the middle of these intervals, and a stopping criterion is provided. The algorithm is termed MASIL. The numerical experiments are performed on real engineering problems with our implementations of SIL, MASIL, Ritz vector, and Lanczos vector methods. While providing a comparable approximation to the solution of the structural dynamics problem, the MASIL approach computes up to 70% fewer eigenvectors and requires fewer shifts, on average, when compared with the standard shifting strategy used for this problem. The Ritz and Lanczos vector methods often provide an accurate approximation to the solution of the structural dynamics problem, but we show that there are cases where these methods do not provide a satisfactory approximation. In the second part of this thesis we explore max-plus algebra. It has been recently observed that an order of magnitude approximations to the absolute values of the eigenvalues of linear and polynomial eigenvalue problems can be obtained by the use of max-plus algebra, when the underlying matrices are unstructured and have large variations between the magnitudes of their entries. We extend the existing algorithms to return only some of the eigenvalues of the standard and generalized max-plus eigenvalue problems, and provide a result which allows for an estimation of the number of eigenvalues in modulus in a given interval. We then present numerical experiments assessing the quality of the max-plus approximations, and find that an order of magnitude approximations to the eigenvalues of symmetric definite eigenvalue problems can also be obtained.

Keyword(s)

max-plus eigenvalue problems; orthogonal polynomials; shift-and-invert Lanczos algorithm; shifting strategy; structural analysis; symmetric generalized eigenvalue problem

Bibliographic metadata

Institutional metadata

Record metadata