What algorithm variant is right for your problem?

ARPACK-NG provides tools for solving a wide range of generalized eigenproblems

\[\hat A \mathbf{x} = \lambda \hat M \mathbf{x}\]

with large sparse square matrices \(\hat A\) and \(\hat M\) (a standard eigenproblem is one with \(\hat M = \hat I\)). At least one of \(\hat A\) and \(\hat M\) – called \(\hat B\) in the following – has to be Hermitian positive semi-definite so that it defines a weighted inner product \(\langle \mathbf{x}, \mathbf{y} \rangle = \mathbf{x}^\dagger \hat B \mathbf{y}\).

All supported classed of the eigenproblems can be transformed into the canonical form

\[\hat O \mathbf{x} = \mu \mathbf{x}.\]

Depending on what properties matrices \(\hat A\) and \(\hat M\) posses – being real or complex, symmetric, positive-definite, etc – a different algorithm and computational mode should be chosen for optimal performance and stability.

ezARPACK wraps ARPACK-NG’s low-level subroutines in a form of three major solver classes.

• ezarpack::arpack_solver<Symmetric, Backend>;

• ezarpack::arpack_solver<Asymmetric, Backend>;

• ezarpack::arpack_solver<Complex, Backend>.

There are also three wrappers for the Parallel ARPACK / MPI subroutines that offer interfaces nearly identical to those of their serial counterparts, and are meant for eigenproblems of a very big size.

• ezarpack::mpi::arpack_solver<Symmetric, Backend>;

• ezarpack::mpi::arpack_solver<Asymmetric, Backend>;

• ezarpack::mpi::arpack_solver<Complex, Backend>.

Here, the solvers are listed in the order of generality of the eigenproblems they can solve – the symmetric variant is the most specialized and fastest one, whereas the complex version is for the most general problems. Furthermore, each of the variants supports a few computational modes. Picking the right combination of solver and computational mode can be an overwhelming task for a non-expert.

In the table below, we give a classification of all supported eigenproblems with recommendations on what solver variant/computational mode to choose. In many cases, there are multiple acceptable choices, and the ‘Notes’ column contains some more elaborate detail. Forms of the transformed matrices \(\hat O\) and \(\hat B\) for each mode are also shown.

Note

There is no specialized solver for complex Hermitian matrices. This case is covered by ezarpack::arpack_solver<Complex, Backend>.

Type of \(\hat A\)	Type of \(\hat M\)	Solver variant	Computational mode	\(\hat O\)	\(\hat B\)	Notes
Real symmetric	\(\hat I\)	Symmetric	Standard	\(\hat A\)	\(\hat I\)	Optimal for finding extremal eigenvalues.
		Symmetric	ShiftAndInvert	\((\hat A - \sigma)^{-1}\)	\(\hat I\)	Optimal for finding eigenvalues in the interior of the spectrum, clustered around the real shift \(\sigma\).
Real symmetric	Real symmetric, positive-definite	Symmetric	Inverse	\(\hat M^{-1} \hat A\)	\(\hat M\)	Optimal for finding extremal eigenvalues when \(\hat M\) is well-conditioned.
		Symmetric	ShiftAndInvert	\((\hat A-\sigma \hat M)^{-1} \hat M\)	\(\hat M\)	Optimal for finding eigenvalues in the interior of the spectrum, clustered around the real shift \(\sigma\).
Real symmetric	Real symmetric, positive semi-definite	Symmetric	ShiftAndInvert	\((\hat A - \sigma \hat M)^{-1} \hat M\)	\(\hat M\)	Optimal for finding eigenvalues clustered around the real shift \(\sigma\).
		Symmetric	Cayley	\((\hat A - \sigma \hat M)^{-1} (\hat A + \sigma \hat M)\)	\(\hat M\)	Cayley-transformed eigenproblem. Another option for finding eigenvalues clustered around the real shift \(\sigma\). The transformation becomes ill-defined near \(\sigma = 0\).
Real symmetric, positive semi-definite	Real symmetric	Symmetric	Buckling	\((\hat A - \sigma \hat M)^{-1} \hat A\)	\(\hat A\)	Buckling-transformed eigenproblem. Optimal for finding eigenvalues clustered around the real shift \(\sigma\). The transformation becomes ill-defined near \(\sigma = 0\).
General real	\(\hat I\)	Asymmetric	Standard	\(\hat A\)	\(\hat I\)	Optimal for finding eigenvalues at the extreme points of the convex hull of the spectrum.
		Asymmetric	ShiftAndInvertReal	\(\Re [(\hat A - \sigma)^{-1}]\)	\(\hat I\)	Optimal for finding eigenvalues in the interior of the spectrum, clustered around the complex shift \(\sigma\). This mode must be chosen over ShiftAndInvertImag if \(\Im\sigma = 0\).
		Asymmetric	ShiftAndInvertImag	\(\Im [(\hat A - \sigma)^{-1}]\)	\(\hat I\)	Optimal for finding eigenvalues in the interior of the spectrum, clustered around the complex shift \(\sigma\). As \(\lambda\) goes to infinity, the eigenvalues are damped more strongly in this mode than in ShiftAndInvertReal.
General real	Real symmetric, positive-definite	Asymmetric	Inverse	\(\hat M^{-1} \hat A\)	\(\hat M\)	Optimal for finding eigenvalues at the extreme points of the convex hull of the spectrum.
		Asymmetric	ShiftAndInvertReal	\(\Re [(\hat A - \sigma\hat M)^{-1} \hat M]\)	\(\hat M\)	Optimal for finding eigenvalues in the interior of the spectrum, clustered around the complex shift \(\sigma\). This mode must be chosen over ShiftAndInvertImag if \(\Im\sigma = 0\).
		Asymmetric	ShiftAndInvertImag	\(\Im [(\hat A - \sigma\hat M)^{-1} \hat M]\)	\(\hat M\)	Optimal for finding eigenvalues in the interior of the spectrum, clustered around the complex shift \(\sigma\). As \(\lambda\) goes to infinity, the eigenvalues are damped more strongly in this mode than in ShiftAndInvertImag.
General real	Real symmetric, positive semi-definite	Asymmetric	ShiftAndInvertReal	\(\Re [(\hat A - \sigma\hat M)^{-1} \hat M]\)	\(\hat M\)	Optimal for finding eigenvalues in the interior of the spectrum, clustered around the complex shift \(\sigma\). This mode must be chosen over ShiftAndInvertImag if \(\Im\sigma = 0\).
		Asymmetric	ShiftAndInvertImag	\(\Im [(\hat A - \sigma\hat M)^{-1} \hat M]\)	\(\hat M\)	Optimal for finding eigenvalues in the interior of the spectrum, clustered around the complex shift \(\sigma\). As \(\lambda\) goes to infinity, the eigenvalues are damped more strongly in this mode than in ShiftAndInvertImag.
General real	General real, invertible	Asymmetric	Standard	\(\hat M^{-1} \hat A\)	\(\hat I\)	Not directly supported by ARPACK-NG. One can manually form operator \(\hat O = \hat M^{-1} \hat A\) and use the Asymmetric solver in the standard mode. Best used when \(\hat M\) is well-conditioned and the eigenvalues of interest are at extreme points of the convex hull of the spectrum.
General real	General real	Asymmetric	Standard	\((\hat A - \sigma\hat M)^{-1} \hat M\)	\(\hat I\)	Not directly supported by ARPACK-NG. One can manually form operator \(\hat O = (\hat A - \sigma\hat M)^{-1}\hat M\) and use the Asymmetric solver in the standard mode. Best used when \(\hat M\) is nearly singular and/or for finding eigenvalues in the interior of the spectrum, clustered around the complex shift \(\sigma\). The eigenvalues \(\mu\) computed by the solver must be manually back-transformed according to \(\lambda = \mu^{-1} + \sigma\).
Complex	\(\hat I\)	Complex	Standard	\(\hat A\)	\(\hat I\)	Optimal for finding eigenvalues at the extreme points of the convex hull of the spectrum.
		Complex	ShiftAndInvert	\((\hat A - \sigma)^{-1}\)	\(\hat I\)	Optimal for finding eigenvalues in the interior of the spectrum, clustered around the complex shift \(\sigma\).
Complex	Complex, Hermitian, positive-definite	Complex	Inverse	\(\hat M^{-1} \hat A\)	\(\hat M\)	Optimal for finding eigenvalues at the extreme points of the convex hull of the spectrum when \(\hat M\) is well-conditioned.
		Complex	ShiftAndInvert	\((\hat A - \sigma \hat M)^{-1} \hat M\)	\(\hat M\)	Optimal for finding eigenvalues in the interior of the spectrum, clustered around the complex shift \(\sigma\).
Complex	Complex, Hermitian, positive semi-definite	Complex	ShiftAndInvert	\((\hat A - \sigma \hat M)^{-1} \hat M\)	\(\hat M\)	Optimal for finding eigenvalues in the interior of the spectrum, clustered around the complex shift \(\sigma\).
Complex	Complex, invertible	Complex	Standard	\(\hat M^{-1} \hat A\)	\(\hat I\)	Not directly supported by ARPACK-NG. One can manually form operator \(\hat O = \hat M^{-1} \hat A\) and use the Complex solver in the standard mode. Best used when \(\hat M\) is well-conditioned and the eigenvalues of interest are at extreme points of the convex hull of the spectrum.
Complex	General complex	Complex	Standard	\((\hat A - \sigma\hat M)^{-1} \hat M\)	\(\hat I\)	Not directly supported by ARPACK-NG. One can manually form operator \(\hat O = (\hat A - \sigma\hat M)^{-1}\hat M\) and use the Complex solver in the standard mode. Best used when \(\hat M\) is nearly singular and/or for finding eigenvalues in the interior of the spectrum, clustered around the complex shift \(\sigma\). The eigenvalues \(\mu\) computed by the solver must be manually back-transformed according to \(\lambda = \mu^{-1} + \sigma\).

Matrix \(\hat M\) being well-conditioned means that it has a moderate condition number \(||\hat M||_2\cdot||\hat M^{-1}||_2\). The shift \(\sigma\) used in various Shift-and-Invert modes has to be provided by the user based on a priori knowledge about the spectrum. The fastest convergence is achieved when it is close to the selected eigenvalues of interest.

The table presented here is meant to give only some basic guidance. For a much deeper overview of ARPACK-NG’s capabilities you are referred to the definitive

ARPACK Users’ Guide: Solution of Large Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods (R. B. Lehoucq, D. C. Sorensen, C. Yang, SIAM, 1998), https://epubs.siam.org/doi/book/10.1137/1.9780898719628