The solution of eigenvalue problems is an integral part of many scientific computations. For example, the numerical solution of problems in structural dynamics, electrical networks, macro-economics, quantum chemistry, and c- trol theory often requires solving eigenvalue problems. The coefficient matrix of the eigenvalue problem may be small to medium sized and dense, or large and sparse (containing many zeroelements). In the past tremendous advances have been achieved in the solution methods for symmetric eigenvalue pr- lems. The state of the art for nonsymmetric problems is not so advanced; nonsymmetric eigenvalue problems can be hopelessly difficult to solve in some situations due, for example, to poor conditioning. Good numerical algorithms for nonsymmetric eigenvalue problems also tend to be far more complex than their symmetric counterparts. This book deals with methods for solving a special nonsymmetric eig- value problem; the symplectic eigenvalue problem. The symplectic eigenvalue problem is helpful, e.g., in analyzing a number of different questions that arise in linear control theory for discrete-time systems. Certain quadratic eigenvalue problems arising, e.g., in finite element discretization in structural analysis, in acoustic simulation of poro-elastic materials, or in the elastic deformation of anisotropic materials can also lead to symplectic eigenvalue problems. The problem appears in other applications as well.
This edited volume highlights the scientific contributions of Volker Mehrmann, a leading expert in the area of numerical (linear) algebra, matrix theory, differential-algebraic equations and control theory. These mathematical research areas are strongly related and often occur in the same real-world applications. The main areas where such applications emerge are computational engineering and sciences, but increasingly also social sciences and economics. This book also reflects some of Volker Mehrmann's major career stages. Starting out working in the areas of numerical linear algebra (his first full professorship at TU Chemnitz was in "Numerical Algebra," hence the title of the book) and matrix theory, Volker Mehrmann has made significant contributions to these areas ever since. The highlights of these are discussed in Parts I and II of the present book. Often the development of new algorithms in numerical linear algebra is motivated by problems in system and control theory. These and his later major work on differential-algebraic equations, to which he together with Peter Kunkel made many groundbreaking contributions, are the topic of the chapters in Part III. Besides providing a scientific discussion of Volker Mehrmann's work and its impact on the development of several areas of applied mathematics, the individual chapters stand on their own as reference works for selected topics in the fields of numerical (linear) algebra, matrix theory, differential-algebraic equations and control theory.
The first in-depth, complete, and unified theoretical discussion of the two most important classes of algorithms for solving matrix eigenvalue problems: QR-like algorithms for dense problems and Krylov subspace methods for sparse problems. The author discusses the theory of the generic GR algorithm, including special cases (for example, QR, SR, HR), and the development of Krylov subspace methods. This book also addresses a generic Krylov process and the Arnoldi and various Lanczos algorithms, which are obtained as special cases. Theoretical and computational exercises guide students, step by step, to the results. Downloadable MATLAB programs, compiled by the author, are available on a supplementary Web site. Readers of this book are expected to be familiar with the basic ideas of linear algebra and to have had some experience with matrix computations. Ideal for graduate students, or as a reference book for researchers and users of eigenvalue codes.
A unified approach is proposed for applied mechanics and optimal control theory. The Hamilton system methodology in analytical mechanics is used for eigenvalue problems, vibration theory, gyroscopic systems, structural mechanics, wave-guide, LQ control, Kalman filter, robust control etc. All aspects are described in the same unified methodology. Numerical methods for all these problems are provided and given in meta-language, which can be implemented easily on the computer. Precise integration methods both for initial value problems and for two-point boundary value problems are proposed, which result in the numerical solutions of computer precision. Key Features of the text include: -Unified approach based on Hamilton duality system theory and symplectic mathematics. -Gyroscopic system vibration, eigenvalue problems. -Canonical transformation applied to non-linear systems. -Pseudo-excitation method for structural random vibrations. -Precise integration of two-point boundary value problems. -Wave propagation along wave-guides, scattering. -Precise solution of Riccati differential equations. -Kalman filtering. -HINFINITY theory of control and filter.
With a substantial amount of new material, the Handbook of Linear Algebra, Second Edition provides comprehensive coverage of linear algebra concepts, applications, and computational software packages in an easy-to-use format. It guides you from the very elementary aspects of the subject to the frontiers of current research. Along with revisions and
"The collection of the contributions to these volumes offers a flavor of the plethora of different approaches to attack structured matrix problems. The reader will find that the theory of structured matrices is positioned to bridge diverse applications in the sciences and engineering, deep mathematical theories, as well as computational and numberical issues. The presentation fully illustrates the fact that the technicques of engineers, mathematicisn, and numerical analysts nicely complement each other, and they all contribute to one unified theory of structured matrices"--Back cover.
This book is about computing eigenvalues, eigenvectors, and invariant subspaces of matrices. Treatment includes generalized and structured eigenvalue problems and all vital aspects of eigenvalue computations. A unique feature is the detailed treatment of structured eigenvalue problems, providing insight on accuracy and efficiency gains to be expected from algorithms that take the structure of a matrix into account.
Inverse eigenvalue problems arise in a remarkable variety of applications and associated with any inverse eigenvalue problem are two fundamental questions--the theoretical issue of solvability and the practical issue of computability. Both questions are difficult and challenging. In this text, the authors discuss the fundamental questions, some known results, many applications, mathematical properties, a variety of numerical techniques, as well as several open problems.This is the first book in the authoritative Numerical Mathematics and Scientific Computation series to cover numerical linear algebra, a broad area of numerical analysis. Authored by two world-renowned researchers, the book is aimed at graduates and researchers in applied mathematics, engineering and computer science and makes an ideal graduate text.
This thesis is on the numerical computation of eigenvalues of symmetric hierarchical matrices. The numerical algorithms used for this computation are derivations of the LR Cholesky algorithm, the preconditioned inverse iteration, and a bisection method based on LDL factorizations. The investigation of QR decompositions for H-matrices leads to a new QR decomposition. It has some properties that are superior to the existing ones, which is shown by experiments using the HQR decompositions to build a QR (eigenvalue) algorithm for H-matrices does not progress to a more efficient algorithm than the LR Cholesky algorithm. The implementation of the LR Cholesky algorithm for hierarchical matrices together with deflation and shift strategies yields an algorithm that require O(n) iterations to find all eigenvalues. Unfortunately, the local ranks of the iterates show a strong growth in the first steps. These H-fill-ins makes the computation expensive, so that O(n³) flops and O(n²) storage are required. Theorem 4.3.1 explains this behavior and shows that the LR Cholesky algorithm is efficient for the simple structured Hl-matrices. There is an exact LDLT factorization for Hl-matrices and an approximate LDLT factorization for H-matrices in linear-polylogarithmic complexity. This factorizations can be used to compute the inertia of an H-matrix. With the knowledge of the inertia for arbitrary shifts, one can compute an eigenvalue by bisectioning. The slicing the spectrum algorithm can compute all eigenvalues of an Hl-matrix in linear-polylogarithmic complexity. A single eigenvalue can be computed in O(k²n log^4 n). Since the LDLT factorization for general H-matrices is only approximative, the accuracy of the LDLT slicing algorithm is limited. The local ranks of the LDLT factorization for indefinite matrices are generally unknown, so that there is no statement on the complexity of the algorithm besides the numerical results in Table 5.7. The preconditioned inverse iteration computes the smallest eigenvalue and the corresponding eigenvector. This method is efficient, since the number of iterations is independent of the matrix dimension. If other eigenvalues than the smallest are searched, then preconditioned inverse iteration can not be simply applied to the shifted matrix, since positive definiteness is necessary. The squared and shifted matrix (M-mu I)² is positive definite. Inner eigenvalues can be computed by the combination of folded spectrum method and PINVIT. Numerical experiments show that the approximate inversion of (M-mu I)² is more expensive than the approximate inversion of M, so that the computation of the inner eigenvalues is more expensive. We compare the different eigenvalue algorithms. The preconditioned inverse iteration for hierarchical matrices is better than the LDLT slicing algorithm for the computation of the smallest eigenvalues, especially if the inverse is already available. The computation of inner eigenvalues with the folded spectrum method and preconditioned inverse iteration is more expensive. The LDLT slicing algorithm is competitive to H-PINVIT for the computation of inner eigenvalues. In the case of large, sparse matrices, specially tailored algorithms for sparse matrices, like the MATLAB function eigs, are more efficient. If one wants to compute all eigenvalues, then the LDLT slicing algorithm seems to be better than the LR Cholesky algorithm. If the matrix is small enough to be handled in dense arithmetic (and is not an Hl(1)-matrix), then dense eigensolvers, like the LAPACK function dsyev, are superior. The H-PINVIT and the LDLT slicing algorithm require only an almost linear amount of storage. They can handle larger matrices than eigenvalue algorithms for dense matrices. For Hl-matrices of local rank 1, the LDLT slicing algorithm and the LR Cholesky algorithm need almost the same time for the computation of all eigenvalues. For large matrices, both algorithms are faster than the dense LAPACK function dsyev.
