9 Eigenvalue Solvers
This chapter describes the eigenvalue methods used in this library. The target is the standard eigenvalue problem for an real sparse matrix given in CRS format; the generalized eigenvalue problem is not supported. The matrices each method can handle and the eigenvalues it returns are listed below. The notation follows the conventions given at the beginning of the Linear Solvers chapter.
| Method | Class | Target matrix | Eigenvalues returned |
|---|---|---|---|
| Power method | parcel::krylov::power |
Symmetric or nonsymmetric | One eigenvalue of largest magnitude (real) |
| Inverse power method | parcel::krylov::inverse_power |
Symmetric or nonsymmetric. Symmetric (positive definite or negative definite) if pcg is chosen as the inner linear solver |
One eigenvalue of smallest magnitude (real) |
| Krylov-Schur method | parcel::krylov::ks_arnoldi |
Symmetric or nonsymmetric | Several eigenvalues of large magnitude (closest to the shift in shift-invert mode). Complex conjugate pairs are included (returned as pairs of real and imaginary parts) |
Because the power method and the inverse power method estimate the eigenvalue with a real Rayleigh quotient, they do not converge when the eigenvalue at the targeted end (largest or smallest magnitude) is a complex conjugate pair, or when several eigenvalues have the same magnitude (e.g., ). Use the Krylov-Schur method for such matrices. The handling of the preconditioner (set_precon_spectrum()) is given in each section. Using the power method (largest-magnitude end) and the inverse power method (smallest-magnitude end) with set_precon_spectrum(true) allows the eigenvalue distribution and the condition number of the preconditioned matrix to be estimated from both ends.
9.1 Power Method [4]
The power method is the most basic iterative method for computing the eigenvalue of largest magnitude and its corresponding eigenvector. Symmetry of is not assumed. The operator applied in the iteration is selected with set_precon_spectrum() as follows.
| Mode | How to specify | Eigenvalue returned | |
|---|---|---|---|
set_precon_spectrum(false) (default) |
Largest-magnitude eigenvalue of | ||
set_precon_spectrum(true) |
Largest-magnitude eigenvalue of |
In the mode, each iteration multiplies by and then by . is built from the passed to the solver according to the settings the user specified with set_precon_algo(), set_blockjacobi(), set_jacobi(), set_scaling_matrix() and set_scaling_vector() (see the “Preconditioners” chapter). In the mode, these preconditioner settings are not used even if specified. Since preconditioning compresses the spectrum, the eigenvalues of tend to cluster around 1. In this case the ratio of the largest-magnitude eigenvalue to the second one approaches 1, and the convergence becomes slow or fails (the same applies to the Krylov-Schur method).
- Algorithm
is the initial vector built from the global row index as (the input values of EigenVec are not used). A vector of all ones is not used because it can be exactly orthogonal to a particular eigenvector. The first global row index of each rank is obtained as the cumulative sum of the local row counts (MPI_Exscan), so does not depend on the number of MPI partitions or on uneven row partitioning. is the value specified with set_precon_spectrum(), is the preconditioner matrix, is the convergence tolerance specified with set_tolerance() (default 1.0e-8), and is the maximum number of iterations specified with set_max_iteration() (default 10000).
The rate of convergence is determined by the ratio of the largest-magnitude eigenvalue to the eigenvalue with the second largest magnitude; the closer the ratio is to 1, the slower the convergence.
The details of the convergence check, the handling of breakdowns and non-finite values, the returned values and the implementation details are given in “Convergence by Solver” in the API Reference.
9.2 Inverse Power Method [4]
The inverse power method computes the eigenvalue of smallest magnitude and its corresponding eigenvector. is not formed explicitly; in each iteration the linear system is solved with the inner linear solver. Since implies , is the Rayleigh quotient of at , and converges to the smallest-magnitude eigenvalue as converges to its eigenvector.
The default inner linear solver is the right-preconditioned generalized minimal residual method (parcel::krylov::pgmres, with modified Gram-Schmidt orthogonalization), which does not require to be symmetric. However, the Rayleigh quotient does not converge when the smallest-magnitude eigenvalue is a complex conjugate pair; in that case use the Krylov-Schur method in shift-invert mode with . Specifying set_linsolve_algo(parcel::krylov::LINSOLVE_PCG) switches the inner linear solver to the preconditioned conjugate gradient method (parcel::krylov::pcg). In this case must be symmetric (positive definite or negative definite). pcg can be selected only in the mode; in the mode pgmres is used regardless of this setting.
The operator applied in the iteration is selected with set_precon_spectrum() as follows. is not formed explicitly; it is applied by solving an equation with the inner linear solver.
| Mode | How to specify | Eigenvalue returned | |
|---|---|---|---|
set_precon_spectrum(false) (default) |
Smallest-magnitude eigenvalue of | ||
set_precon_spectrum(true) |
Smallest-magnitude eigenvalue of |
In the mode, is solved with the inner linear solver. Its preconditioner is built from according to settings such as set_linsolve_precon_algo() (default: Jacobi preconditioner PRECON_JACOBI with 1 iteration). In configurations with a low-precision preconditioner, set_linsolve_precon_algo(parcel::PRECON_NONE) may be faster (“Known Limits at Low Precision”). In the mode, is solved with an inner right-preconditioned pgmres (preconditioner ), and is used as is.
The inner linear solver has settings separate from those of the outer eigenvalue iteration. The solver type is specified with set_linsolve_algo(), the convergence tolerance with set_linsolve_tolerance(), the maximum number of iterations with set_linsolve_max_iteration(), the restart length of pgmres with set_linsolve_restart(), and the preconditioner with set_linsolve_precon_algo(), set_linsolve_blockjacobi() and set_linsolve_jacobi() (shared with shift-invert of the Krylov-Schur method; the list and default values are given in “Member Functions Common to the Eigenvalue Solvers” in the API Reference). In the mode, the preconditioner of the inner pgmres is itself, and settings such as set_linsolve_precon_algo() are not used. As in the power method, is built from with the user’s preconditioner settings.
In the mode, need not be formed explicitly; the preconditioner only needs to apply . This is because right-preconditioned GMRES internally treats as the coefficient matrix, so returning the internal variable without the final multiplication by gives the action of .
- Algorithm
is built with the same formula as in the power method and normalized before use. is the value specified with set_precon_spectrum(), is the preconditioner matrix, is the preconditioner matrix of the inner linear solver ( without preconditioning), is the restart length specified with set_linsolve_restart() (default 30), is the value of set_tolerance() (default 1.0e-8), and is the value of set_max_iteration() (default 10000). The inner linear solver in lines 4 and 6 starts from and iterates until the relative residual falls below the value of set_linsolve_tolerance() (default 1.0e-10), up to the value of set_linsolve_max_iteration() (default 5000) iterations. Line 6 uses GMRES(m) by default, and CG when set_linsolve_algo(parcel::krylov::LINSOLVE_PCG) is specified.
The details of the convergence check, the handling of breakdowns and non-finite values, the returned values and the implementation details are given in “Convergence by Solver” in the API Reference.
9.3 Krylov-Schur Method [5]
ks_arnoldi implements the Krylov-Schur method [5], which combines the Arnoldi decomposition with restarting by the real Schur decomposition to compute several eigenpairs simultaneously. It applies to both symmetric and nonsymmetric matrices, and also computes complex conjugate pairs of eigenvalues. The operator used in the Arnoldi decomposition is as follows.
| Mode | How to specify | Eigenvalues returned | |
|---|---|---|---|
| No shift | set_precon_spectrum(false) (default) |
(eigenvalues of ) | |
| No shift () | set_precon_spectrum(true) |
(eigenvalues of ) | |
| shift-invert | set_shift(σ) + pass as the fourth argument |
(eigenvalues of ) | |
| shift-invert (no fourth argument) | set_shift(σ) only |
(eigenvalues of ) | |
| shift-invert () | set_shift(σ) + set_precon_spectrum(true) |
(eigenvalues of ) |
As in the power method, is built from with the user’s preconditioner settings, and is not used in the mode without shift. In shift-invert, (or ) is solved at each Arnoldi step with the inner pgmres. The settings of the inner linear solver are specified with the same set_linsolve_* as in the inverse power method. When is passed as the fourth argument, the preconditioner of the inner pgmres is built from this matrix (default: Jacobi preconditioner). When the fourth argument is omitted, the system is solved from and the shift , and is fixed to . In the mode, the preconditioner of the inner pgmres is , and is not needed.
- Algorithm
is the initial vector the user gives in the first elements of EigenVec, is the operator in the table above, , is the matrix with elements , is the maximum subspace dimension, is the number of Ritz vectors kept at restart, is the number of eigenvalues checked for convergence, and is the maximum number of restarts. , and are specified with set_ks_subspace(m, k_keep, nev) (default 30, 10, 4), with set_ks_max_restart() (default 200), and with set_tolerance() (default 1.0e-8). is the -th unit vector.
The orthogonalization in lines 7 to 11 is by default CGS2, which applies the classical Gram-Schmidt method twice (the inner products of one projection are gathered in a single collective communication, and the basis is updated with a single gemv). With set_qr_algo(parcel::qr::QR_MGS), it is replaced by modified Gram-Schmidt applied twice (an inner product and an axpy per column); QR_CGS selects CGS2 (the same constants as pgmres; ks_arnoldi applies either method twice), and other values throw std::invalid_argument. Both restore orthogonality in the second pass, and the accuracy of the eigenvalues is equivalent. Modified Gram-Schmidt can be faster on CPU configurations with a small number of local rows per rank; CGS2 is faster on CPUs with many local rows and on GPUs. The default is CGS2. However, the build for PS-A (the spack environment psa) uses MGS2 by default (the build-time macro PARCEL_KS_ORTHO_DEFAULT=mgs, spack variant ks_ortho=mgs; see “Default Orthogonalization of ks_arnoldi”), because MGS2 can be faster on CPUs with a small number of local rows per thread and a large cache. A value given with set_qr_algo() takes precedence over the build-time default.
The eigenvectors in line 27 are written only as many as fit in EigenVec ( vectors). If only the leading vectors are needed, allocate EigenVec with elements.
The details of the convergence check, the handling of breakdowns and non-finite values, the returned values and the implementation details are given in “Convergence by Solver” in the API Reference.