NAG Library Chapter Introduction
f02 – Eigenvalues and Eigenvectors
1
Scope of the Chapter
This chapter provides functions for various types of matrix eigenvalue problem:
 standard eigenvalue problems (finding eigenvalues and eigenvectors of a square matrix $A$);
 singular value problems (finding singular values and singular vectors of a rectangular matrix $A$);
 generalized eigenvalue problems (finding eigenvalues and eigenvectors of a matrix pencil $A\lambda B$).
 quadratic eigenvalue problems (finding eigenvalues and eigenvectors of the quadratic ${\lambda}^{2}A+\lambda B+C$).
Functions are provided for both real and complex data.
The majority of functions for these problems can be found in
Chapter f08 which contains software derived from LAPACK (see
Anderson et al. (1999)). However, you should read the the
f02 Chapter Introduction before turning to
Chapter f08, especially if you are a new user.
Chapter f12 contains functions for large sparse eigenvalue problems, although one such function is also available in this chapter.
Chapters f02 and
f08 contain
Black Box (or
Driver) functions that enable many problems to be solved by a call to a single function, and the decision trees in
Section 4 direct you to the most appropriate functions in
Chapters f02 and
f08. The
Chapter f02 functions call functions in
Chapters f07 and
f08 wherever possible to perform the computations, and there are pointers in
Section 4 to the relevant decision trees in
Chapter f08.
2
Background to the Problems
Here we describe the different types of problem which can be tackled by the functions in this chapter, and give a brief outline of the methods used to solve them. If you have one specific type of problem to solve, you need only read the relevant subsection and then turn to
Section 3. Consult a standard textbook for a more thorough discussion, for example
Golub and Van Loan (1996) or
Parlett (1998).
In each subsection, we first describe the problem in terms of real matrices. The changes needed to adapt the discussion to complex matrices are usually simple and obvious: a matrix transpose such as ${Q}^{\mathrm{T}}$ must be replaced by its conjugate transpose ${Q}^{\mathrm{H}}$; symmetric matrices must be replaced by Hermitian matrices, and orthogonal matrices by unitary matrices. Any additional changes are noted at the end of the subsection.
2.1
Standard Eigenvalue Problems
Let
$A$ be a square matrix of order
$n$. The
standard eigenvalue problem is to find eigenvalues,
$\lambda $, and corresponding eigenvectors,
$x\ne 0$, such that
(The phrase ‘eigenvalue problem’ is sometimes abbreviated to
eigenproblem.)
2.1.1
Standard symmetric eigenvalue problems
If $A$ is real symmetric, the eigenvalue problem has many desirable features, and it is advisable to take advantage of symmetry whenever possible.
The eigenvalues
$\lambda $ are all real, and the eigenvectors can be chosen to be mutually orthogonal. That is, we can write
or equivalently:
where
$\Lambda $ is a real diagonal matrix whose diagonal elements
${\lambda}_{i}$ are the eigenvalues, and
$Z$ is a real orthogonal matrix whose columns
${z}_{i}$ are the eigenvectors. This implies that
${z}_{i}^{\mathrm{T}}{z}_{j}=0$ if
$i\ne j$, and
${\Vert {z}_{i}\Vert}_{2}=1$.
Equation
(2) can be rewritten
This is known as the
eigendecomposition or
spectral factorization of
$A$.
Eigenvalues of a real symmetric matrix are wellconditioned, that is, they are not unduly sensitive to perturbations in the original matrix
$A$. The sensitivity of an eigenvector depends on how small the gap is between its eigenvalue and any other eigenvalue: the smaller the gap, the more sensitive the eigenvector. More details on the accuracy of computed eigenvalues and eigenvectors are given in the function documents, and in the
f08 Chapter Introduction.
For dense or band matrices, the computation of eigenvalues and eigenvectors proceeds in the following stages:
1. 
$A$ is reduced to a symmetric tridiagonal matrix $T$ by an orthogonal similarity transformation: $A=QT{Q}^{\mathrm{T}}$, where $Q$ is orthogonal. (A tridiagonal matrix is zero except for the main diagonal and the first subdiagonal and superdiagonal on either side.) $T$ has the same eigenvalues as $A$ and is easier to handle. 
2. 
Eigenvalues and eigenvectors of $T$ are computed as required. If all eigenvalues (and optionally eigenvectors) are required, they are computed by the $QR$ algorithm, which effectively factorizes $T$ as $T=S\Lambda {S}^{\mathrm{T}}$, where $S$ is orthogonal, or by the divideandconquer method.
If only selected eigenvalues are required, they are computed by bisection, and if selected eigenvectors are required, they are computed by inverse iteration. If $s$ is an eigenvector of $T$, then $Qs$ is an eigenvector of $A$. 
All the above remarks also apply – with the obvious changes – to the case when $A$ is a complex Hermitian matrix. The eigenvectors are complex, but the eigenvalues are all real, and so is the tridiagonal matrix $T$.
If
$A$ is large and sparse, the methods just described would be very wasteful in both storage and computing time, and therefore an alternative algorithm, known as
subspace iteration, is provided (for real problems only) to find a (usually small) subset of the eigenvalues and their corresponding eigenvectors.
Chapter f12 contains functions based on the Lanczos method for real symmetric large sparse eigenvalue problems, and these functions are usually more efficient than subspace iteration.
2.1.2
Standard nonsymmetric eigenvalue problems
A real nonsymmetric matrix
$A$ may have complex eigenvalues, occurring as complex conjugate pairs. If
$x$ is an eigenvector corresponding to a complex eigenvalue
$\lambda $, then the complex conjugate vector
$\stackrel{}{x}$ is the eigenvector corresponding to the complex conjugate eigenvalue
$\stackrel{}{\lambda}$. Note that the vector
$x$ defined in equation
(1) is sometimes called a
right eigenvector; a
left eigenvector
$y$ is defined by
Functions in this chapter only compute right eigenvectors (the usual requirement), but functions in
Chapter f08 can compute left or right eigenvectors or both.
The eigenvalue problem can be solved via the
Schur factorization of
$A$, defined as
where
$Z$ is an orthogonal matrix and
$T$ is a real upper
quasitriangular matrix, with the same eigenvalues as
$A$.
$T$ is called the
Schur form of
$A$. If all the eigenvalues of
$A$ are real, then
$T$ is upper triangular, and its diagonal elements are the eigenvalues of
$A$. If
$A$ has complex conjugate pairs of eigenvalues, then
$T$ has
$2$ by
$2$ diagonal blocks, whose eigenvalues are the complex conjugate pairs of eigenvalues of
$A$. (The structure of
$T$ is simpler if the matrices are complex – see below.)
For example, the following matrix is in quasitriangular form
and has eigenvalues
$1$,
$2\pm i$, and
$3$. (The elements indicated by ‘
$*$’ may take any values.)
The columns of
$Z$ are called the
Schur vectors. For each
$k\left(1\le k\le n\right)$, the first
$k$ columns of
$Z$ form an orthonormal basis for the invariant subspace corresponding to the first
$k$ eigenvalues on the diagonal of
$T$. (An
invariant subspace (for
$A$) is a subspace
$S$ such that for any vector
$v$ in
$S$,
$Av$ is also in
$S$.) Because this basis is orthonormal, it is preferable in many applications to compute Schur vectors rather than eigenvectors. It is possible to order the Schur factorization so that any desired set of
$k$ eigenvalues occupy the
$k$ leading positions on the diagonal of
$T$, and functions for this purpose are provided in
Chapter f08.
Note that if $A$ is symmetric, the Schur vectors are the same as the eigenvectors, but if $A$ is nonsymmetric, they are distinct, and the Schur vectors, being orthonormal, are often more satisfactory to work with in numerical computation.
Eigenvalues and eigenvectors of a nonsymmetric matrix may be illconditioned, that is, sensitive to perturbations in
$A$.
Chapter f08 contains functions which compute or estimate the condition numbers of eigenvalues and eigenvectors, and the
f08 Chapter Introduction gives more details about the error analysis of nonsymmetric eigenproblems. The accuracy with which eigenvalues and eigenvectors can be obtained is often improved by
balancing a matrix. This is discussed further in
Section 3.4.
Computation of eigenvalues, eigenvectors or the Schur factorization proceeds in the following stages:
1. 
$A$ is reduced to an upper Hessenberg matrix $H$ by an orthogonal similarity transformation: $A=QH{Q}^{\mathrm{T}}$, where $Q$ is orthogonal. (An upper Hessenberg matrix is zero below the first subdiagonal.) $H$ has the same eigenvalues as $A$, and is easier to handle. 
2. 
The upper Hessenberg matrix $H$ is reduced to Schur form $T$ by the $QR$ algorithm, giving the Schur factorization $H=ST{S}^{\mathrm{T}}$. The eigenvalues of $A$ are obtained from the diagonal blocks of $T$. The matrix $Z$ of Schur vectors (if required) is computed as $Z=QS$. 
3. 
After the eigenvalues have been found, eigenvectors may be computed, if required, in two different ways. Eigenvectors of $H$ can be computed by inverse iteration, and then premultiplied by $Q$ to give eigenvectors of $A$; this approach is usually preferred if only a few eigenvectors are required. Alternatively, eigenvectors of $T$ can be computed by backsubstitution, and premultiplied by $Z$ to give eigenvectors of $A$. 
All the above remarks also apply – with the obvious changes – to the case when $A$ is a complex matrix. The eigenvalues are in general complex, so there is no need for special treatment of complex conjugate pairs, and the Schur form $T$ is simply a complex upper triangular matrix.
As for the symmetric eigenvalue problem, if
$A$ and is large and sparse then it is generally preferable to use an alternative method.
Chapter f12 provides functions based on Arnoldi's method for both real and complex matrices, intended to find a subset of the eigenvalues and vectors.
2.2
The Singular Value Decomposition
The
singular value decomposition (SVD) of a real
$m$ by
$n$ matrix
$A$ is given by
where
$U$ and
$V$ are orthogonal and
$\Sigma $ is an
$m$ by
$n$ diagonal matrix with real diagonal elements,
${\sigma}_{i}$, such that
The
${\sigma}_{i}$ are the
singular values of
$A$ and the first
$\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left(m,n\right)$ columns of
$U$ and
$V$ are, respectively, the
left and
right singular vectors of
$A$. The singular values and singular vectors satisfy
where
${u}_{i}$ and
${v}_{i}$ are the
$i$th columns of
$U$ and
$V$ respectively.
The singular value decomposition of
$A$ is closely related to the eigendecompositions of the symmetric matrices
${A}^{\mathrm{T}}A$ or
$A{A}^{\mathrm{T}}$, because:
However, these relationships are not recommended as a means of computing singular values or vectors unless
$A$ is sparse and functions from
Chapter f12 are to be used.
If
${U}_{k}$,
${V}_{k}$ denote the leading
$k$ columns of
$U$ and
$V$ respectively, and if
${\Sigma}_{k}$ denotes the leading principal submatrix of
$\Sigma $, then
is the best rank
$k$ approximation to
$A$ in both the
$2$norm and the Frobenius norm.
Singular values are wellconditioned; that is, they are not unduly sensitive to perturbations in
$A$. The sensitivity of a singular vector depends on how small the gap is between its singular value and any other singular value: the smaller the gap, the more sensitive the singular vector. More details on the accuracy of computed singular values and vectors are given in the function documents and in the
f08 Chapter Introduction.
The singular value decomposition is useful for the numerical determination of the rank of a matrix, and for solving linear least squares problems, especially when they are rankdeficient (or nearly so). See
Chapter f04.
Computation of singular values and vectors proceeds in the following stages:
1. 
$A$ is reduced to an upper bidiagonal matrix $B$ by an orthogonal transformation $A={U}_{1}B{V}_{1}^{\mathrm{T}}$, where ${U}_{1}$ and ${V}_{1}$ are orthogonal. (An upper bidiagonal matrix is zero except for the main diagonal and the first superdiagonal.) $B$ has the same singular values as $A$, and is easier to handle. 
2. 
The SVD of the bidiagonal matrix $B$ is computed as $B={U}_{2}\Sigma {V}_{2}^{\mathrm{T}}$, where ${U}_{2}$ and ${V}_{2}$ are orthogonal and $\Sigma $ is diagonal as described above. Then in the SVD of $A$, $U={U}_{1}{U}_{2}$ and $V={V}_{1}{V}_{2}$. 
All the above remarks also apply – with the obvious changes – to the case when $A$ is a complex matrix. The singular vectors are complex, but the singular values are real and nonnegative, and the bidiagonal matrix $B$ is also real.
By formulating the problems appropriately, real large sparse singular value problems may be solved using the symmetric eigenvalue functions in
Chapter f12.
2.3
Generalized Eigenvalue Problems
Let
$A$ and
$B$ be square matrices of order
$n$. The
generalized eigenvalue problem is to find eigenvalues,
$\lambda $, and corresponding eigenvectors,
$x\ne 0$, such that
For given
$A$ and
$B$, the set of all matrices of the form
$A\lambda B$ is called a
pencil, and
$\lambda $ and
$x$ are said to be an eigenvalue and eigenvector of the pencil
$A\lambda B$.
When
$B$ is nonsingular, equation
(4) is mathematically equivalent to
$\left({B}^{1}A\right)x=\lambda x$, and when
$A$ is nonsingular, it is equivalent to
$\left({A}^{1}B\right)x=\left(1/\lambda \right)x$. Thus, in theory, if one of the matrices
$A$ or
$B$ is known to be nonsingular, the problem could be reduced to a standard eigenvalue problem.
However, for this reduction to be satisfactory from the point of view of numerical stability, it is necessary not only that
$B$ (or
$A$) should be nonsingular, but that it should be wellconditioned with respect to inversion. The nearer
$B$ is to singularity, the more unsatisfactory
${B}^{1}A$ will be as a vehicle for determining the required eigenvalues. Welldetermined eigenvalues of the original problem
(4) may be poorly determined even by the correctly rounded version of
${B}^{1}A$.
We consider first a special class of problems in which $B$ is known to be nonsingular, and then return to the general case in the following subsection.
2.3.1
Generalized symmetricdefinite eigenvalue problems
If $A$ and $B$ are symmetric and $B$ is positive definite, then the generalized eigenvalue problem has desirable properties similar to those of the standard symmetric eigenvalue problem. The eigenvalues are all real, and the eigenvectors, while not orthogonal in the usual sense, satisfy the relations ${z}_{i}^{\mathrm{T}}B{z}_{j}=0$ for $i\ne j$ and can be normalized so that ${z}_{i}^{\mathrm{T}}B{z}_{i}=1$.
Note that it is not enough for $A$ and $B$ to be symmetric; $B$ must also be positive definite, which implies nonsingularity. Eigenproblems with these properties are referred to as symmetricdefinite problems.
If
$\Lambda $ is the diagonal matrix whose diagonal elements are the eigenvalues, and
$Z$ is the matrix whose columns are the eigenvectors, then
To compute eigenvalues and eigenvectors, the problem can be reduced to a standard symmetric eigenvalue problem, using the Cholesky factorization of
$B$ as
$L{L}^{\mathrm{T}}$ or
${U}^{\mathrm{T}}U$ (see
Chapter f07). Note, however, that this reduction does implicitly involve the inversion of
$B$, and hence this approach should
not be used if
$B$ is illconditioned with respect to inversion.
For example, with
$B=L{L}^{\mathrm{T}}$, we have
Hence the eigenvalues of
$Az=\lambda Bz$ are those of
$Cy=\lambda y$, where
$C$ is the symmetric matrix
$C={L}^{1}A{L}^{\mathrm{T}}$ and
$y={L}^{\mathrm{T}}z$. The standard symmetric eigenproblem
$Cy=\lambda y$ may be solved by the methods described in
Section 2.1.1. The eigenvectors
$z$ of the original problem may be recovered by computing
$z={L}^{\mathrm{T}}y$.
Most of the functions which solve this class of problems can also solve the closely related problems
where again
$A$ and
$B$ are symmetric and
$B$ is positive definite. See the function documents for details.
All the above remarks also apply – with the obvious changes – to the case when $A$ and $B$ are complex Hermitian matrices. Such problems are called Hermitiandefinite. The eigenvectors are complex, but the eigenvalues are all real.
If
$A$ and
$B$ are large and sparse, reduction to an equivalent standard eigenproblem as described above would almost certainly result in a large dense matrix
$C$, and hence would be very wasteful in both storage and computing time. The methods of subspace iteration and Lanczos type methods, mentioned in
Section 2.1.1, can also be used for large sparse generalized symmetricdefinite problems.
2.3.2
Generalized nonsymmetric eigenvalue problems
Any generalized eigenproblem which is not symmetricdefinite with wellconditioned $B$ must be handled as if it were a general nonsymmetric problem.
If $B$ is singular, the problem has infinite eigenvalues. These are not a problem; they are equivalent to zero eigenvalues of the problem $Bx=\mu Ax$. Computationally they appear as very large values.
If $A$ and $B$ are both singular and have a common null space, then $A\lambda B$ is singular for all $\lambda $; in other words, any value $\lambda $ can be regarded as an eigenvalue. Pencils with this property are called singular.
As with standard nonsymmetric problems, a real problem may have complex eigenvalues, occurring as complex conjugate pairs.
The generalized eigenvalue problem can be solved via the
generalized Schur factorization of
$A$ and
$B$:
where
$Q$ and
$Z$ are orthogonal,
$V$ is upper triangular, and
$U$ is upper quasitriangular (defined just as in
Section 2.1.2).
If all the eigenvalues are real, then $U$ is upper triangular; the eigenvalues are given by ${\lambda}_{i}={u}_{ii}/{v}_{ii}$. If there are complex conjugate pairs of eigenvalues, then $U$ has $2$ by $2$ diagonal blocks.
Eigenvalues and eigenvectors of a generalized nonsymmetric problem may be illconditioned; that is, sensitive to perturbations in $A$ or $B$.
Particular care must be taken if, for some $i$, ${u}_{ii}={v}_{ii}=0$, or in practical terms if ${u}_{ii}$ and ${v}_{ii}$ are both small; this means that the pencil is singular, or approximately so. Not only is the particular value ${\lambda}_{i}$ undetermined, but also no reliance can be placed on any of the computed eigenvalues. See also the function documents.
Computation of eigenvalues and eigenvectors proceeds in the following stages.
1. 
The pencil $A\lambda B$ is reduced by an orthogonal transformation to a pencil $H\lambda K$ in which $H$ is upper Hessenberg and $K$ is upper triangular: $A={Q}_{1}H{Z}_{1}^{\mathrm{T}}$ and $B={Q}_{1}K{Z}_{1}^{\mathrm{T}}$. The pencil $H\lambda K$ has the same eigenvalues as $A\lambda B$, and is easier to handle. 
2. 
The upper Hessenberg matrix $H$ is reduced to upper quasitriangular form, while $K$ is maintained in upper triangular form, using the $QZ$ algorithm. This gives the generalized Schur factorization: $H={Q}_{2}U{Z}_{2}$ and $K={Q}_{2}V{Z}_{2}$. 
3. 
Eigenvectors of the pencil $U\lambda V$ are computed (if required) by backsubstitution, and premultiplied by ${Z}_{1}{Z}_{2}$ to give eigenvectors of $A$. 
All the above remarks also apply – with the obvious changes – to the case when $A$ and $B$ are complex matrices. The eigenvalues are in general complex, so there is no need for special treatment of complex conjugate pairs, and the matrix $U$ in the generalized Schur factorization is simply a complex upper triangular matrix.
As for the generalized symmetricdefinite eigenvalue problem, if
$A$ and
$B$ are large and sparse then it is generally preferable to use an alternative method.
Chapter f12 provides functions based on Arnoldi's method for both real and complex matrices, intended to find a subset of the eigenvalues and vectors.
2.4
Quadratic eigenvalue problems
Let
$A$,
$B$ and
$C$ be square matrices of order
$n$. The
quadratic eigenvalue problem (QEP) is to find eigenvalues,
$\lambda $, and corresponding eigenvectors,
$x\ne 0$, such that
More specifically,
$x$ is a right eigenvector and a left eigenvector,
$y$, is such that
where
${y}^{\mathrm{H}}$ is the conjugate transpose of
$y$ (transpose when
$y$ is real).
In general the QEP has $2n$ eigenvalues and corresponding eigenvectors.
QEPs are generally solved by linearizing the problem to produce a
$2n$ by
$2n$ generalized eigenvalue problem. For example,
which is called the first companion form and has the same
$2n$ eigenvalues as the QEP.
If
then the QEP is said to be
regular, or
nonsingular. For a regular QEP, when
$C$ is singular the QEP has one or more zero eigenvalues and when
$A$ is singular the QEP has one or more infinite eigenvalues. As with the generalized problem particular care must be taken when the problem is singular (see
Section 2.3.2).
As with generalized nonsymmetric problems, a real QEP may have complex eigenvalues, occurring as complex conjugate pairs.
For further information on QEPs, see the survey article by
Tisseur and Meerbergen (2001), and for details on solving the dense QEP see
Hammarling et al. (2013).
3
Recommendations on Choice and Use of Available Functions
3.1
Black Box Functions and General Purpose Functions
Functions in the NAG C Library for solving eigenvalue problems fall into two categories.
1. 
Black Box Functions: these are designed to solve a standard type of problem in a single call – for example, to compute all the eigenvalues and eigenvectors of a real symmetric matrix. You are recommended to use a black box function if there is one to meet your needs; refer to the decision tree in Section 4.1 or the index in Section 5. 
2. 
General Purpose Functions: these perform the computational subtasks which make up the separate stages of the overall task, as described in Section 2 – for example, reducing a real symmetric matrix to tridiagonal form. General purpose functions are to be found, for historical reasons, some in this chapter, a few in Chapter f01, but most in Chapter f08. If there is no black box function that meets your needs, you will need to use one or more general purpose functions.
Here are some of the more likely reasons why you may need to do this:
 Your problem is already in one of the reduced forms – for example, your symmetric matrix is already tridiagonal.
 You wish to economize on storage for symmetric matrices (see Section 3.3).
 You wish to find selected eigenvalues or eigenvectors of a generalized symmetricdefinite eigenproblem (see also Section 3.2).

The decision trees in
Section 4.2 list the combinations of general purpose functions which are needed to solve many common types of problem.
Sometimes a combination of a black box function and one or more general purpose functions will be the most convenient way to solve your problem: the black box function can be used to compute most of the results, and a general purpose function can be used to perform a subsidiary computation, such as computing condition numbers of eigenvalues and eigenvectors.
3.2
Computing Selected Eigenvalues and Eigenvectors
The decision trees and the function documents make a distinction between functions which compute all eigenvalues or eigenvectors, and functions which compute selected eigenvalues or eigenvectors; the two classes of function use different algorithms.
It is difficult to give clear guidance on which of these two classes of function to use in a particular case, especially with regard to computing eigenvectors. If you only wish to compute a very few eigenvectors, then a function for selected eigenvectors will be more economical, but if you want to compute a substantial subset (an old rule of thumb suggested more than 25%), then it may be more economical to compute all of them. Conversely, if you wish to compute all the eigenvectors of a sufficiently large symmetric tridiagonal matrix, the function for selected eigenvectors may be faster.
The choice depends on the properties of the matrix and on the computing environment; if it is critical, you should perform your own timing tests.
For dense nonsymmetric eigenproblems, there are no algorithms provided for computing selected eigenvalues; it is always necessary to compute all the eigenvalues, but you can then select specific eigenvectors for computation by inverse iteration.
3.3
Storage Schemes for Symmetric Matrices
Functions which handle symmetric matrices are usually designed to use either the upper or lower triangle of the matrix; it is not necessary to store the whole matrix. If either the upper or lower triangle is stored conventionally in the upper or lower triangle of a twodimensional array, the remaining elements of the array can be used to store other useful data. However, that is not always convenient, and if it is important to economize on storage, the upper or lower triangle can be stored in a onedimensional array of length $n\left(n+1\right)/2$; in other words, the storage is almost halved. This storage format is referred to as packed storage.
Functions designed for packed storage are usually less efficient, especially on highperformance computers, so there is a tradeoff between storage and efficiency.
A band matrix is one whose nonzero elements are confined to a relatively small number of subdiagonals or superdiagonals on either side of the main diagonal. Algorithms can take advantage of bandedness to reduce the amount of work and storage required.
Functions which take advantage of packed storage or bandedness are provided for both standard symmetric eigenproblems and generalized symmetricdefinite eigenproblems.
3.4
Balancing for Nonsymmmetric Eigenproblems
There are two preprocessing steps which one may perform on a nonsymmetric matrix $A$ in order to make its eigenproblem easier. Together they are referred to as balancing.
1. 
Permutation: this involves reordering the rows and columns to make $A$ more nearly upper triangular (and thus closer to Schur form): ${A}^{\prime}=PA{P}^{\mathrm{T}}$, where $P$ is a permutation matrix. If $A$ has a significant number of zero elements, this preliminary permutation can reduce the amount of work required, and also improve the accuracy of the computed eigenvalues. In the extreme case, if $A$ is permutable to upper triangular form, then no floatingpoint operations are needed to reduce it to Schur form. 
2. 
Scaling: a diagonal matrix $D$ is used to make the rows and columns of ${A}^{\prime}$ more nearly equal in norm: ${A}^{\prime \prime}=D{A}^{\prime}{D}^{1}$. Scaling can make the matrix norm smaller with respect to the eigenvalues, and so possibly reduce the inaccuracy contributed by roundoff (see Chapter II/11 of Wilkinson and Reinsch (1971)). 
Functions are provided in
Chapter f08 for performing either or both of these preprocessing steps, and also for transforming computed eigenvectors or Schur vectors back to those of the original matrix.
Black box functions in this chapter which compute the Schur factorization perform only the permutation step, since diagonal scaling is not in general an orthogonal transformation. The black box functions which compute eigenvectors perform both forms of balancing.
3.5
Nonuniqueness of Eigenvectors and Singular Vectors
Eigenvectors, as defined by equations
(1) or
(4), are
not uniquely defined. If
$x$ is an eigenvector, then so is
$kx$ where
$k$ is any nonzero scalar. Eigenvectors computed by different algorithms, or on different computers, may appear to disagree completely, though in fact they differ only by a scalar factor (which may be complex). These differences should not be significant in any application in which the eigenvectors will be used, but they can arouse uncertainty about the correctness of computed results.
Even if eigenvectors
$x$ are normalized so that
${\Vert x\Vert}_{2}=1$, this is not sufficient to fix them uniquely, since they can still be multiplied by a scalar factor
$k$ such that
$\leftk\right=1$. To counteract this inconvenience, most of the functions in this chapter, and in
Chapter f08, normalize eigenvectors (and Schur vectors) so that
${\Vert x\Vert}_{2}=1$ and the component of
$x$ with largest absolute value is real and positive. (There is still a possible indeterminacy if there are two components of equal largest absolute value – or in practice if they are very close – but this is rare.)
In symmetric problems the computed eigenvalues are sorted into ascending order, but in nonsymmetric problems the order in which the computed eigenvalues are returned is dependent on the detailed working of the algorithm and may be sensitive to rounding errors. The Schur form and Schur vectors depend on the ordering of the eigenvalues and this is another possible cause of nonuniqueness when they are computed. However, it must be stressed again that variations in the results from this cause should not be significant. (Functions in
Chapter f08 can be used to transform the Schur form and Schur vectors so that the eigenvalues appear in any given order if this is important.)
In singular value problems, the left and right singular vectors $u$ and $v$ which correspond to a singular value $\sigma $ cannot be normalized independently: if $u$ is multiplied by a factor $k$ such that $\leftk\right=1$, then $v$ must also be multiplied by $k$.
Nonuniqueness also occurs among eigenvectors which correspond to a multiple eigenvalue, or among singular vectors which correspond to a multiple singular value. In practice, this is more likely to be apparent as the extreme sensitivity of eigenvectors which correspond to a cluster of close eigenvalues (or of singular vectors which correspond to a cluster of close singular values).
4
Decision Trees
4.1
Black Box Functions
The decision tree for this section is divided into three subtrees.
Note: for the
Chapter f08 functions there is generally a choice of simple and comprehensive function. The comprehensive functions return additional information such as condition and/or error estimates.
Tree 1: Eigenvalues and Eigenvectors of Real Matrices
Is this a sparse eigenproblem $Ax=\lambda x$ or $Ax=\lambda Bx$? 

Is the problem symmetric? 

f02fkc 
yes  yes 
 no    no  

f02ekc 


Is the eigenproblem $\left({\lambda}^{2}A+\lambda B+C\right)x=0$? 

f02jcc 
yes 
 no  
Is the eigenproblem $Ax=\lambda Bx$? 

Are $A$ and $B$ symmetric with $B$ positive definite and wellconditioned w.r.t inversion? 

Are $A$ and $B$ band matrices? 

f08uac, f08ubc or f12ffc and f12agc 
yes  yes  yes 
 no    no    no  


f08sac or f08sbc 
 
 

Are $A$ and $B$ band matrices? 

f12afc and f12agc 
 yes 
  no  

Is the generalized Schur factorization required? 

f08xac 
 yes 
  no  

f08wac or f08wbc 


The eigenproblem is $Ax=\lambda x$. Is $A$ symmetric? 

Are all eigenvalues or all eigenvectors required? 

f08fac 
yes  yes 
 no    no  

f08fbc 


Are eigenvalues only required? 

f08nac or f08nbc 
yes 
 no  
Is the Schur factorization required? 

f08pac or f08pbc 
yes 
 no  
Are all eigenvectors required? 

f08nac or f08nbc 
yes 
 no  
f02ecc 

Tree 2: Eigenvalues and Eigenvectors of Complex Matrices
Is this a sparse eigenproblem $Ax=\lambda x$ or $Ax=\lambda Bx$? 

Are $A$ and $B$ banded matrices? 

f12atc and f12auc 
yes  yes 
 no    no  

See Chapter f12 


Is the eigenproblem $\left({\lambda}^{2}A+\lambda B+C\right)x=0$? 

f02jqc 
yes 
 no  
Is the eigenproblem $Ax=\lambda Bx$? 

Are $A$ and $B$ Hermitian with $B$ positive definite and wellconditioned w.r.t. inversion? 

f08unc or f08upc 
yes  yes 
 no    no  

Is the generalized Schur factorization required? 

f08xnc 
 yes 
  no  

f08wnc 


The eigenproblem is $Ax=\lambda x$. Is $A$ Hermitian? 

Are all eigenvalues and eigenvectors required? 

f08fnc or f08fpc 
yes  yes 
 no    no  

f08fpc 


Are eigenvalues only required? 

f08nnc or f08npc 
yes 
 no  
Is the Schur factorization required? 

f08pnc or f08ppc 
yes 
 no  
Are all eigenvectors required? 

f08nnc or f08npc 
yes 
 no  
f02gcc 

Tree 3: Singular Values and Singular Vectors
Is $A$ a complex matrix? 

f08kpc 
yes 
 no  
Are only the leading terms required? 

f02wgc 
yes 
 no  
f08kbc 

4.2
General Purpose Functions (Eigenvalues and Eigenvectors)
Functions for large sparse eigenvalue problems are to be found in
Chapter f12, see the
f12 Chapter Introduction.
The decision tree for this section addressing dense problems, is divided into eight subtrees:
As it is very unlikely that one of the functions in this section will be called on its own, the other functions required to solve a given problem are listed in the order in which they should be called.
4.3
General Purpose Functions (Singular Value Decomposition)
See
Section 4.2 in the f08 Chapter Introduction. For real sparse matrices where only selected singular values are required (possibly with their singular vectors), functions from
Chapter f12 may be applied to the symmetric matrix
${A}^{\mathrm{T}}A$; see
Section 10 in
nag_real_symm_sparse_eigensystem_iter (f12fbc).
5
Functionality Index
complex quadratic eigenproblem,   
all eigenvalues and optionally eigenvectors, backward,   
real quadratic eigenproblem,   
all eigenvalues and optionally eigenvectors, backward,   
real sparse eigenproblem,   
real sparse symmetric matrix,   
6
Auxiliary Functions Associated with Library Function Arguments
None.
7
Functions Withdrawn or Scheduled for Withdrawal
The following lists all those functions that have been withdrawn since Mark 23 of the Library or are scheduled for withdrawal at one of the next two marks.
8
References
Anderson E, Bai Z, Bischof C, Blackford S, Demmel J, Dongarra J J, Du Croz J J, Greenbaum A, Hammarling S, McKenney A and Sorensen D (1999) LAPACK Users' Guide (3rd Edition) SIAM, Philadelphia
Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore
Hammarling S, Munro C J and Tisseur F (2013) An algorithm for the complete solution of quadratic eigenvalue problems.
ACM Trans. Math. Software. 39(3):18:1–18:119 http://eprints.ma.man.ac.uk/1815/
Parlett B N (1998) The Symmetric Eigenvalue Problem SIAM, Philadelphia
Tisseur F and Meerbergen K (2001) The quadratic eigenvalue problem SIAM Review 43:235–286
Wilkinson J H and Reinsch C (1971) Handbook for Automatic Computation II, Linear Algebra Springer–Verlag