Given a matrix \(A \in \mathbb R^{n \times n}\), the standard eigenvalue problem (SEP) consists of finding eigenvalues \(\lambda_i \in \mathbb C\) and associated eigenvectors \(0 \neq v_i \in \mathbb C^{n}\) such that

\[ A v_i = \lambda_i v_i, \text{ for } i = 1, 2, \dots, n. \]

The eigenvalues are the \(n\) (potentially complex) roots of the polynomial \(\text{det}(A - \lambda I) = 0\) of degree \(n\). There is often a full set of \(n\) linearly independent eigenvectors, but if there are multiple eigenvalues (i.e., if \(\lambda_{i} = \lambda_{j}\) for some \(i \neq j\)) then there might not be a full set of independent eigenvectors.

The library provides 12 interface functions for the standard case.

Hessenberg reduction

Given a general matrix \(A\), the starneig_SEP_SM_Hessenberg() and starneig_SEP_DM_Hessenberg() interface functions compute a Hessenberg decomposition

\[ A = U * H * U^T, \]

where \(H\) is upper Hessenberg and \(U\) is orthogonal. On exit, \(A\) is overwritten by \(H\) and \(Q\) (which is an orthogonal matrix on entry) is overwritten by

\[ Q \gets Q * U. \]

This is done in order to greatly accelerate the subsequent computation of a Schur decomposition since when working on \(H\) of size \(n \times n\), the amount of work in each iteration of the QR algorithm is reduced from \(\mathcal{O}(n^3)\) to \(\mathcal{O}(n^2)\) flops.

Schur reduction

Given a Hessenberg decomposition

\[ A = Q * H * Q^T, \]

of a general matrix \(A\), the starneig_SEP_SM_Schur() and starneig_SEP_DM_Schur() interface functions compute a Schur decomposition

\[ A = Q * ( U * S * U^T ) * Q^T \]

where \(S\) is upper quasi-triangular with \(1 \times 1\) and \(2 \times 2\) blocks on the diagonal (Schur matrix) and \(U\) is orthogonal. The \(1 \times 1\) blocks correspond to the real eigenvalues and each \(2 \times 2\) block corresponds to a pair of complex conjugate eigenvalues. On exit, \(H\) is overwritten by \(S\) and \(Q\) is overwritten by

\[ Q \gets Q * U. \]

Eigenvalue reordering

Given a Schur decomposition

\[ A = Q * S * Q^T \]

of a general matrix \(A\) and a selection of eigenvalues, the starneig_SEP_SM_ReorderSchur() and starneig_SEP_DM_ReorderSchur() interface functions attempt to compute an updated Schur decomposition

\[ A = Q * \left( U * \begin{bmatrix} \hat S_{11} & \hat S_{12} \\ 0 & \hat S_{22} \end{bmatrix} * U^T \right) * Q^T, \]

where the selected eigenvalues appear in \(\hat S_{11}\). On exit, \(S\) is overwritten by \(\hat{S}\) and \(Q\) is overwritten by

\[ Q \gets Q * U. \]

Reordering may in rare cases fail. In such cases the output is guaranteed to be a Schur decomposition and all (if any) selected eigenvalues that are correctly placed are marked in the selection array on exit. Reordering may perturb the eigenvalues and the eigenvalues after reordering are returned.

Combined reduction to Schur form and eigenvalue reordering

Given a general matrix \(A\), the starneig_SEP_SM_Reduce() and starneig_SEP_DM_Reduce() interface functions compute a (reordered) Schur decomposition

\[ A = U * S * U^T. \]

Optionally, the interface functions attempt to reorder selected eigenvalues to the top left corner of the Schur matrix \(S\). On exit, \(A\) is overwritten by \(S\) and \(Q\) (which is an orthogonal matrix on entry) is overwritten by

\[ Q \gets Q * U. \]

Reordering may in rare cases fail. In such cases the output is guaranteed to be a Schur decomposition and all (if any) selected eigenvalues that are correctly placed are marked in the selection array on exit. Reordering may perturb the eigenvalues and the eigenvalues after reordering are returned.

Eigenvectors

Given a subset consisting of \(m \leq n\) of the eigenvalues \(\lambda_{i}\) for \(i = 1, 2, \ldots, m\) and a Schur decomposition \(A = Q S Q^{H}\), we can compute for each \(\lambda_{i}\) an eigenvector \(v_{i} \neq 0\) such that \(A v_{i} = \lambda_{i} v_{i}\) by first computing an eigenvector \(w_{i}\) of \(S\) and then transform it back to the original basis by pre-multiplication with \(Q\).

Given a Schur decomposition

\[ A = Q * S * Q^T \]

of a general matrix \(A\) and a selection of eigenvalues, the starneig_SEP_SM_Eigenvectors() and starneig_SEP_DM_Eigenvectors() interface functions compute and return an eigenvector for each of the selected eigenvalues.

The eigenvectors are stored as columns in the output matrix \(X\) in the same order as their corresponding eigenvalues appear in the selection array. A real eigenvector is stored as a single column. The real and imaginary parts of a complex eigenvector are stored as consecutive columns.

For a selected pair of complex conjugate eigenvalues, an eigenvector is computed only for the eigenvalue with positive imaginary part. Thus, every selected eigenvalue contributes one column to the output matrix and thus the number of selected eigenvalues is equal to the number of columns of \(X\).

Eigenvalue selection helper

Given a Schur matrix and a predicate function, the starneig_SEP_SM_Select() and starneig_SEP_DM_Select() interface functions conveniently generate a correct selection array and count the number of selected eigenvalues. The count is useful when allocating storage for the eigenvector matrix computed by the starneig_SEP_SM_Eigenvectors() and starneig_SEP_DM_Eigenvectors() interface functions.

// a predicate function that selects all eigenvalues that have a real
// part that is larger than a given value
static int predicate(double real, double imag, void *arg)
{
    double value = * (double *) arg;
 
    if (value < real)
        return 1;
    return 0;
}
 
void func(...)
{
    double *S; int ldS;
 
    ...
 
    double value = 0.5;
    int num_selected, *selected = malloc(n*sizeof(int));
    starneig_SEP_SM_Select(
        n, S, ldS, &predicate, &value, selected, &num_selected);
 
    ...
}

See modules Shared Memory / Standard EVP and Distributed Memory / Standard EVP for further information. See also examples sep_sm_full_chain.c, sep_dm_full_chain.c and sep_sm_eigenvectors.c.