Introduction

Let $A$ be a square $n$ by $n$ matrix, $x$ a nonzero $n$ by 1 vector (a column vector), and $\lambda$ a scalar, such that

$$Ax = \lambda x.$$ (1)

Then $\lambda$ is called an eigenvalue of $A$, and $x$ is called a (right) eigenvector. Sometimes we refer to $(\lambda,x)$ as an eigenpair. We refer the reader to the list of symbols and acronyms on page ; we will use the notation listed there freely throughout the text.

In this chapter we introduce and classify all the eigenproblems discussed in this book, describing their basic mathematical properties and interrelationships. Eigenproblems can be defined by a single square matrix $A$ as in (2.1), by a nonsquare matrix $A$, by 2 or more square or rectangular matrices, or even by a matrix function of $\lambda$. We use the word ``eigenproblem'' in order to encompass computing eigenvalues, eigenvectors, Schur decompositions, condition numbers of eigenvalues, singular value and vectors, and yet other terms to be defined below. After reading this chapter the reader should be able to recognize the mathematical types of many eigenproblems, which are essential to picking the most effective algorithms. Not recognizing the right mathematical type of an eigenproblem can lead to using an algorithm that might not work at all or that might take orders of magnitude more time and space than a more specialized algorithm.

To illustrate the sources and interrelationships of these eigenproblems, we have a set of related examples for each one. The sections of this chapter are organized to correspond to the next six chapters of this book:

Section 2.2:

Hermitian eigenproblems (HEP) (Chapter 4). This corresponds to $Ax = \lambda x$ as in (2.1), where $A$ is Hermitian, i.e., $A = A^*$.

Section 2.3:

Generalized Hermitian eigenproblems (GHEP) (Chapter 5). This corresponds to $Ax = \lambda Bx$, where $A$ and $B$ are Hermitian and $B$ is positive definite (has all positive eigenvalues).

Section 2.4:

Singular value decomposition (SVD) (Chapter 6). Given any rectangular matrix $A$, this corresponds to finding the eigenvalues and eigenvectors of the Hermitian matrices $A^* A$ and $AA^*$.

Section 2.5:

Non-Hermitian eigenproblems (NHEP) (Chapter 7). This corresponds to $Ax = \lambda x$ as in (2.1), where $A$ is square but otherwise general.

Section 2.6:

Generalized non-Hermitian eigenproblems (GNHEP) (Chapter 8). This corresponds to $Ax = \lambda Bx$. We will first treat the most common case of the regular generalized eigenproblem, which occurs when $A$ and $B$ are square and $\alpha A - \beta B$ is nonsingular for some choice of scalars $\alpha$ and $\beta$. We will also discuss the singular case.

Section 2.7:

Nonlinear eigenproblems (Chapter 9). The simplest case of this is the quadratic eigenvalue problem $L(\lambda)x = (\lambda^2 M + \lambda D + K)x = 0$ and includes higher degree polynomials as well. We also discuss maximizing a real function $F(Y)$ over the space of $m$ by $n$ orthonormal matrices; this includes eigenproblems as a special case as well as much more complicated problems such as simultaneously reducing two or more symmetric matrices to diagonal form as nearly as possible using the same set of approximate eigenvectors for all of them.

Bai's note: this section is not necessary, there are not much we can/need to say. $Ax = \lambda Bx$ in the singular case is discussed in Chap 8.

[Sec ] More generalized eigenproblems (Chapter 9). This chapter includes several cases. First, we discuss $Ax = \lambda Bx$ in the singular case, i.e. when the eigenvalues are not continuous functions. Second we discuss polynomial eigenproblems $\sum_{i=0}^k \lambda^i A_i x = 0$. When $k=1$ we get $-A_0 x = \lambda A_1 x$ which corresponds to cases considered before. Third, we consider the fully nonlinear case $A(\lambda)x = 0$, where $A$ can depend on $\lambda$ in any continuous way. When $A(\lambda)$ is a polynomial in $\lambda$ we get the previous case.

All the eigenproblems described above arise naturally in applications arising in science and engineering. In each section we also show how one can recognize and solve closely related eigenproblems (for example, GEHPs, where $\alpha A + \beta B$ is positive definite instead of $B$). Chapters are presented in roughly increasing order of generality and complexity. For example, the HEP $Ax = \lambda x$ is clearly a special case of the GHEP $Ax = \lambda Bx$, because we can set $B=I$. It is also a special case of the NHEP, because we can ignore $A$'s Hermitian symmetry and treat it as a general matrix.

In general, the larger or more difficult an eigenvalue problem, the more important it is to use an algorithm that exploits as much of its mathematical structure as possible (such as symmetry or sparsity). For example, one can use algorithms for non-Hermitian problems to treat Hermitian ones, but the price is a large increase in time, storage, and possibly lower accuracy.

Each section from 2.2 through 2.6 is organized as follows.

1. The basic definitions of eigenvalues and eigenvectors will be given.

2. Eigenspaces will be defined. A subspace $\cal Y$ is defined as the space ${\rm span}\{y_1,\ldots,y_k\}$ spanned by a chosen set of vectors $y_1,\ldots,y_k$; i.e., $\cal Y$ is the set of all linear combinations of $y_1,\ldots,y_k$. Eigenspaces are (typically) spanned by a subset of eigenvectors and may be called invariant subspaces, deflating subspaces, or something else depending on the type of eigenproblem.

3. Equivalences will be defined; these are transformations (such as changing $A$ to $SAS^{-1}$) that leave the eigenvalues unchanged and can be used to compute a ``simpler representation'' of the eigenproblem. Depending on the situation, equivalences are also called similarities or congruences.

4. Eigendecompositions will be defined; these are commonly computed ``simpler representations.''

5. Conditioning will be discussed. A condition number measures how sensitive the eigenvalues and eigenspaces of $A$ are to small changes in $A$. These small changes could arise from roundoff or other unavoidable approximations made by the algorithm, or from uncertainty in the entries of $A$. One can get error bounds on computed eigenvalues and eigenspaces by multiplying their condition numbers by a bound on the change in $A$. For more details on how condition numbers are used to get error bounds, see §2.1.1.

   An eigenvalue or eigenspace is called well-conditioned if its error bound is acceptably small for the user (this obviously depends on the user), and ill-conditioned if it is much larger. Conditioning is important not just to interpret the computed results of an algorithm, but to choose the information to be computed. For example, different representations of the same eigenspace may have very different condition numbers, and it is often better to compute the better conditioned representation. Conditioning is discussed in more detail in each chapter, but the general results are summarized here.

6. Different ways of specifying an eigenproblem are listed. The most expensive eigenvalue problem is to ask for all eigenvalues and eigenvectors of $A$. Since this is often too expensive in time and space, users frequently ask for less information, such as the largest 10 eigenvalues and perhaps their eigenvectors. (Note that if $A$ is sparse, typically the eigenvectors are dense, so storing all the eigenvectors can take much more memory than storing $A$.) Also, some eigenproblems for the same matrix $A$ may be much better conditioned than others, and these may be preferable to compute.

7. Related eigenproblems are discussed. For example, if it is possible to convert an eigenproblem into a simpler and cheaper special case, this is shown.

8. The vibrational analysis of the mass-spring system shown in Figure 2.1 is used to illustrate the source and formulation of each eigenproblem.

   Figure 2.1: Damped, vibrating mass-spring system.

   

   Newton's law $F=ma$ applied to this vibrating mass-spring system yields
   

   $$k_i (x_{i-1}(t)-x_i(t)) + k_{i+1} (x_{i+1}(t)-x_i(t)) - b_{i} \dot{x}_i(t) = m_i \ddot{x}_i (t),$$
   
   
   where the first term on the left-hand side is the force on mass $i$ from spring $i$, the second term is the force on mass $i$ from spring $i+1$, and the third term is the force on mass $i$ from damper $i$. In matrix form, these equations can be written as
   
   $$M \ddot{x}(t) = -B \dot{x}(t) - K x(t),$$
   
   
   where $M = {\rm diag}( m_1,\ldots, m_n )$, $B = {\rm diag}( b_1,\ldots, b_n )$, and
   
   $$K = \bmat{ccccc} k_1 + k_2 & -k_2 & & & \\ -k_2 & k_2 + k_3... ...-1} & k_{n-1} + k_n & -k_n \\ & & & -k_n & k_n \emat \; \; .$$
   
   
   We assume all the masses $m_i$ are positive. $M$ is called the mass matrix, $B$ is the damping matrix, and $K$ is the stiffness matrix. All three matrices are symmetric. They are also positive definite (have all positive eigenvalues) when the $m_i$, $b_i$, and $k_i$ are positive, respectively. This differential equation becomes an eigenvalue problem by seeking solutions of the form $x(t) = e^{\lambda t} x$, where $\lambda$ is a constant scalar and $x$ is a constant vector, both of which are determined by solving appropriate eigenproblems.

   Electrical engineers analyzing linear circuits arrive at an analogous equation by applying Kirchoff's and related laws instead of Newton's law. In this case $x$ represents branch currents, $M$ represent inductances, $B$ represents resistances, and $K$ represents admittances (reciprocal capacitances).

Chapter 9 on nonlinear eigenproblems is organized differently, according to the structure of the specific nonlinear problems discussed.

Finally, Chapters 10 and 11 treat issues common to many or all of the above eigenvalue problems. Chapter 10 treats data structures, algorithms, and software for sparse matrices, especially sparse linear solvers, which often are the most time-consuming part of an eigenvalue algorithm. Chapter 11 treats preconditioning techniques or methods for converting an eigenproblem into a simpler one. Some preconditioning techniques are well established; others are a matter of current research.