Benchmark problems for eigenvalue reordering algorithms sought

Question

Every real matrix $A$ can be reduce to real Schur form $T = U^T A U$ using an orthogonal similiary transform $U$. Here the matrix $T$ is quasi-triangular form with 1 by 1 or 2 by 2 blocks on the main diagonal. Each 1 by 1 block corresponds to a real eigenvalue of $A$ and each 2 by 2 block corresponds to a pair of complex conjugate eigenvalues of $A$.

The eigenvalue reordering problem consists of finding an orthogonal similarity transformation $V$ such that the user's selection of eigenvalues of $A$ appears along the diagonal of the upper left corner of $S = V^T T V$.

In LAPACK the relevant routine double precision routine is called DTRSEN. Daniel Kressner has written a blocked version by the name BDTRSEN. The ScaLAPACK routine is PDTRSEN.

I am looking for applications and algorithms where advances in solving the eigenvalue reordering problem would have real benefits.

We can easily generate test matrices in quasi triangular form, but we are having trouble deciding the shape of a realistic distribution of the user's selection of eigenvalues.

From my perspective, subspace iteration with Ritz acceleration is an ideal algorithm for testing improvements to the reordering algorithm. It needs (sparse) matrix vector multiplication, a tall QR algorithm and a reordering algorithm.

However, is hard for me to find real life problems where it is clear that a particular set of eigenpairs is physically interesting.

We can do eigenvalue reordering for dense matrices of dimension 40,000 using a shared memory machine. The best performance is achieved when the user selects about 50% of all eigenvalues.

Answer 1

The question is quite old, but I can give a meaningful answer here.

One of the most common algorithms to solve algebraic Riccati equations $A^TX+XA+Q=XGX$ (the Schur method) goes as follows:

1. Compute a Schur decomposition of the Hamiltonian matrix $H = \begin{bmatrix}A& G\\ Q & -A^T \end{bmatrix}$
2. Reorder so that the eigenvalues in the left-half plane (which are precisely 50% of them) come first
3. Take the first $n$ columns of the reordered orthogonal matrix $U$.

So you can take benchmark problems for algebraic Riccati equations and control theory problems, such as CAREX and Oberwolfach, and formulate associated reordering problems.

Answer 2

I'm sure I don't fully appreciate the utility of the eigenvalue reordering algorithm, but many answers come to mind for this part of your question:

However, is hard for me to find real life problems where it is clear that a particular set of eigenpairs is physically interesting.

For example, in certain hydrodynamic stability problems you will have unique eigenvalues that are associated with physical phenomena such as Kelvin--Helmholtz modes or Tollmien--Schlichting waves. In fluid-structure-interaction problems, the resonant mode can be associated with a flapping instability.

Is this along the lines of what you are looking for? If so, I'm sure others will chirp in with examples from their fields; if not, can you sharpen up the question?