PARCEL SYCL v1.2 / User Guide User Guide API Reference Search Download 日本語

9 Eigenvalue Solvers

This chapter describes the eigenvalue methods used in this library. The target is the standard eigenvalue problem Ax=λxAx = \lambda x for an nglobal×nglobaln_{global} \times n_{global} real sparse matrix AA given in CRS format; the generalized eigenvalue problem Ax=λBxAx = \lambda Bx 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 σ\sigma 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., ±λ\pm\lambda). 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 AK−1AK^{-1} 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 AA is not assumed. The operator Op\mathrm{Op} applied in the iteration is selected with set_precon_spectrum() as follows.

Mode How to specify Op\mathrm{Op} Eigenvalue returned
AA set_precon_spectrum(false) (default) AA Largest-magnitude eigenvalue of AA
AK−1AK^{-1} set_precon_spectrum(true) AK−1AK^{-1} Largest-magnitude eigenvalue of AK−1AK^{-1}

In the AK−1AK^{-1} mode, each iteration multiplies by K−1K^{-1} and then by AA. KK is built from the AA 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 AA mode, these preconditioner settings are not used even if specified. Since preconditioning compresses the spectrum, the eigenvalues of AK−1AK^{-1} 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).

x(0)x^{(0)} is the initial vector built from the global row index gg as 1+0.5sin⁡(0.317g+0.7)+0.3cos⁡(0.181g−1.3)1 + 0.5\sin(0.317g + 0.7) + 0.3\cos(0.181g - 1.3) (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 x(0)x^{(0)} does not depend on the number of MPI partitions or on uneven row partitioning. specspec is the value specified with set_precon_spectrum(), KK is the preconditioner matrix, toltol is the convergence tolerance specified with set_tolerance() (default 1.0e-8), and NN is the maximum number of iterations specified with set_max_iteration() (default 10000).

  1. Chooseinitialguessx(0)\mathrm{Choose}\ \mathrm{initial}\ \mathrm{guess}\ x^{(0)}
  2. fori=0,1,…,N−1\mathrm{for}\ i = 0,1,\ldots,N - 1
  3.   ifspecthen\mathrm{if}\ spec\ \mathrm{then}
  4.     solvezfromKz=x(i)\mathrm{solve}\ z\ \mathrm{from}\ Kz = x^{(i)}
  5.   else\mathrm{else}
  6.     z=x(i)z = x^{(i)}
  7.   endif\mathrm{endif}
  8.   y=Azy = Az
  9.   λ(i)=⟨x(i),y⟩/⟨x(i),x(i)⟩\lambda^{(i)} = \langle x^{(i)},y \rangle\ /\ \langle x^{(i)},x^{(i)} \rangle
  10.   x(i+1)=y/∥y∥x^{(i + 1)} = y\ /\ \|y\|
  11.   ifi>0and|λ(i)−λ(i−1)|/|λ(i)|<tolthen\mathrm{if}\ i > 0\ \mathrm{and}\ |\lambda^{(i)} - \lambda^{(i - 1)}|\ /\ |\lambda^{(i)}| < tol\ \mathrm{then}
  12.     quit\mathrm{quit}
  13.   endif\mathrm{endif}
  14. end\mathrm{end}

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. A−1A^{-1} is not formed explicitly; in each iteration the linear system Ay=x(i)Ay = x^{(i)} is solved with the inner linear solver. Since y=A−1x(i)y = A^{-1}x^{(i)} implies x(i)=Ayx^{(i)} = Ay, θ(i)=⟨y,x(i)⟩/⟨y,y⟩=⟨y,Ay⟩/⟨y,y⟩\theta^{(i)} = \langle y, x^{(i)} \rangle / \langle y, y \rangle = \langle y, Ay \rangle / \langle y, y \rangle is the Rayleigh quotient of AA at yy, and θ(i)\theta^{(i)} converges to the smallest-magnitude eigenvalue as yy 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 AA 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 σ=0\sigma = 0. 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 AA must be symmetric (positive definite or negative definite). pcg can be selected only in the AA mode; in the AK−1AK^{-1} mode pgmres is used regardless of this setting.

The operator Op\mathrm{Op} applied in the iteration is selected with set_precon_spectrum() as follows. Op\mathrm{Op} is not formed explicitly; it is applied by solving an equation with the inner linear solver.

Mode How to specify Op\mathrm{Op} Eigenvalue returned
AA set_precon_spectrum(false) (default) A−1A^{-1} Smallest-magnitude eigenvalue of AA
AK−1AK^{-1} set_precon_spectrum(true) (AK−1)−1(AK^{-1})^{-1} Smallest-magnitude eigenvalue of AK−1AK^{-1}

In the AA mode, Ay=x(i)Ay = x^{(i)} is solved with the inner linear solver. Its preconditioner KinK_{in} is built from AA 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 AK−1AK^{-1} mode, (AK−1)y=x(i)(AK^{-1})y = x^{(i)} is solved with an inner right-preconditioned pgmres (preconditioner KK), and yy 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 KinK_{in} 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 AK−1AK^{-1} mode, the preconditioner of the inner pgmres is KK itself, and settings such as set_linsolve_precon_algo() are not used. As in the power method, KK is built from AA with the user’s preconditioner settings.

In the AK−1AK^{-1} mode, KK need not be formed explicitly; the preconditioner only needs to apply K−1K^{-1}. This is because right-preconditioned GMRES internally treats AK−1AK^{-1} as the coefficient matrix, so returning the internal variable yy without the final multiplication by K−1K^{-1} gives the action of (AK−1)−1(AK^{-1})^{-1}.

x(0)x^{(0)} is built with the same formula as in the power method and normalized before use. specspec is the value specified with set_precon_spectrum(), KK is the preconditioner matrix, KinK_{in} is the preconditioner matrix of the inner linear solver (Kin=IK_{in} = I without preconditioning), mm is the restart length specified with set_linsolve_restart() (default 30), toltol is the value of set_tolerance() (default 1.0e-8), and NN is the value of set_max_iteration() (default 10000). The inner linear solver in lines 4 and 6 starts from y=0y = 0 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.

  1. Chooseinitialguessx(0)with∥x(0)∥=1\mathrm{Choose}\ \mathrm{initial}\ \mathrm{guess}\ x^{(0)}\ \mathrm{with}\ \|x^{(0)}\| = 1
  2. fori=0,1,…,N−1\mathrm{for}\ i = 0,1,\ldots,N - 1
  3.   ifspecthen\mathrm{if}\ spec\ \mathrm{then}
  4.     solveyfrom(AK−1)y=x(i)byGMRES(m)preconditionedwithK\mathrm{solve}\ y\ \mathrm{from}\ (AK^{-1})y = x^{(i)}\ \mathrm{by}\ \mathrm{GMRES}(m)\ \mathrm{preconditioned}\ \mathrm{with}\ K
  5.   else\mathrm{else}
  6.     solveyfromAy=x(i)byGMRES(m)orCGpreconditionedwithKin\mathrm{solve}\ y\ \mathrm{from}\ Ay = x^{(i)}\ \mathrm{by}\ \mathrm{GMRES}(m)\ \mathrm{or}\ \mathrm{CG}\ \mathrm{preconditioned}\ \mathrm{with}\ K_{in}
  7.   endif\mathrm{endif}
  8.   θ(i)=⟨y,x(i)⟩/⟨y,y⟩\theta^{(i)} = \langle y,x^{(i)} \rangle\ /\ \langle y,y \rangle
  9.   x(i+1)=y/∥y∥x^{(i + 1)} = y\ /\ \|y\|
  10.   ifi>0and|θ(i)−θ(i−1)|/|θ(i)|<tolthen\mathrm{if}\ i > 0\ \mathrm{and}\ |\theta^{(i)} - \theta^{(i - 1)}|\ /\ |\theta^{(i)}| < tol\ \mathrm{then}
  11.     quit\mathrm{quit}
  12.   endif\mathrm{endif}
  13. end\mathrm{end}

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 Op\mathrm{Op} used in the Arnoldi decomposition is as follows.

Mode How to specify Op\mathrm{Op} Eigenvalues returned
No shift set_precon_spectrum(false) (default) AA λ=θ\lambda = \theta (eigenvalues of AA)
No shift (AK−1AK^{-1}) set_precon_spectrum(true) AK−1AK^{-1} λ=θ\lambda = \theta (eigenvalues of AK−1AK^{-1})
shift-invert set_shift(σ) + pass A−σIA - \sigma I as the fourth argument (A−σI)−1(A - \sigma I)^{-1} λ=σ+1/θ\lambda = \sigma + 1/\theta (eigenvalues of AA)
shift-invert (no fourth argument) set_shift(σ) only (A−σI)−1(A - \sigma I)^{-1} λ=σ+1/θ\lambda = \sigma + 1/\theta (eigenvalues of AA)
shift-invert (AK−1AK^{-1}) set_shift(σ) + set_precon_spectrum(true) (AK−1−σI)−1(AK^{-1} - \sigma I)^{-1} λ=σ+1/θ\lambda = \sigma + 1/\theta (eigenvalues of AK−1AK^{-1})

As in the power method, KK is built from AA with the user’s preconditioner settings, and is not used in the AA mode without shift. In shift-invert, (A−σI)z=v(A - \sigma I)z = v (or (AK−1−σI)z=v(AK^{-1} - \sigma I)z = v) 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 A−σIA - \sigma I is passed as the fourth argument, the preconditioner KinK_{in} of the inner pgmres is built from this matrix (default: Jacobi preconditioner). When the fourth argument is omitted, the system is solved from AA and the shift σ\sigma, and KinK_{in} is fixed to II. In the AK−1AK^{-1} mode, the preconditioner of the inner pgmres is KK, and A−σIA - \sigma I is not needed.

x(0)x^{(0)} is the initial vector the user gives in the first nlocaln_{local} elements of EigenVec, Op\mathrm{Op} is the operator in the table above, Vj=[v1,…,vj]V_{j} = [v_{1},\ldots,v_{j}], HH is the matrix with elements hi,jh_{i,j}, mm is the maximum subspace dimension, kkeepk_{keep} is the number of Ritz vectors kept at restart, nevnev is the number of eigenvalues checked for convergence, and NRN_{R} is the maximum number of restarts. mm, kkeepk_{keep} and nevnev are specified with set_ks_subspace(m, k_keep, nev) (default 30, 10, 4), NRN_{R} with set_ks_max_restart() (default 200), and toltol with set_tolerance() (default 1.0e-8). eme_{m} is the mm-th unit vector.

  1. Computev1=x(0)/∥x(0)∥forsomeinitialguessx(0)\mathrm{Compute}\ v_{1} = x^{(0)}\ /\ \|x^{(0)}\|\ \mathrm{for}\ \mathrm{some}\ \mathrm{initial}\ \mathrm{guess}\ x^{(0)}
  2. k=0k = 0
  3. forν=0,1,…,NR−1\mathrm{for}\ \nu = 0,1,\ldots,N_{R} - 1
  4.   forj=k+1,…,m\mathrm{for}\ j = k + 1,\ldots,m
  5.     w=Opvjw = \mathrm{Op}\ v_{j}
  6.     h1:j,j=0h_{1:j,j} = 0
  7.     forpass=1,2\mathrm{for}\ pass = 1,2
  8.       ξ=VjTw\xi = V_{j}^{T}w
  9.       w=w−Vjξw = w - V_{j}\xi
  10.       h1:j,j=h1:j,j+ξh_{1:j,j} = h_{1:j,j} + \xi
  11.     end\mathrm{end}
  12.     hj+1,j=∥w∥h_{j + 1,j} = \|w\|
  13.     vj+1=w/hj+1,jv_{j + 1} = w\ /\ h_{j + 1,j}
  14.   end\mathrm{end}
  15.   Computeeigenpairs(θl,yl)ofHmandsortby|θl|indescendingorder\mathrm{Compute}\ \mathrm{eigenpairs}\ (\theta_{l},y_{l})\ \mathrm{of}\ H_{m}\ \mathrm{and}\ \mathrm{sort}\ \mathrm{by}\ |\theta_{l}|\ \mathrm{in}\ \mathrm{descending}\ \mathrm{order}
  16.   if|hm+1,m||emTyl|/|θl|≤tolforl=1,…,nevthen\mathrm{if}\ |h_{m + 1,m}||e_{m}^{T}y_{l}|\ /\ |\theta_{l}| \leq tol\ \mathrm{for}\ l = 1,\ldots,nev\ \mathrm{then}
  17.     quit\mathrm{quit}
  18.   endif\mathrm{endif}
  19.   ComputerealSchurformHm=QTQT\mathrm{Compute}\ \mathrm{real}\ \mathrm{Schur}\ \mathrm{form}\ H_{m} = QTQ^{T}
  20.   ReorderQ,Tsothatthekkeeplargest|θ|comefirstandsetk\mathrm{Reorder}\ Q,T\ \mathrm{so}\ \mathrm{that}\ \mathrm{the}\ k_{keep}\ \mathrm{largest}\ |\theta|\ \mathrm{come}\ \mathrm{first}\ \mathrm{and}\ \mathrm{set}\ k
  21.   Vk=VmQ:,1:kV_{k} = V_{m}Q_{:,1:k}
  22.   vk+1=vm+1v_{k + 1} = v_{m + 1}
  23.   H1:k,1:k=T1:k,1:k,hk+1,1:k=hm+1,mQm,1:kH_{1:k,1:k} = T_{1:k,1:k},\ \ h_{k + 1,1:k} = h_{m + 1,m}Q_{m,1:k}
  24. end\mathrm{end}
  25. Computeeigenpairs(θl,yl)ofHmandsortby|θl|indescendingorder\mathrm{Compute}\ \mathrm{eigenpairs}\ (\theta_{l},y_{l})\ \mathrm{of}\ H_{m}\ \mathrm{and}\ \mathrm{sort}\ \mathrm{by}\ |\theta_{l}|\ \mathrm{in}\ \mathrm{descending}\ \mathrm{order}
  26. forl=1,…,kkeep\mathrm{for}\ l = 1,\ldots,k_{keep}
  27.   xl=Vmylx_{l} = V_{m}y_{l}
  28.   ifshiftinvertmodethen\mathrm{if}\ \mathrm{shift}\ \mathrm{invert}\ \mathrm{mode}\ \mathrm{then}
  29.     λl=σ+1/θl\lambda_{l} = \sigma + 1\ /\ \theta_{l}
  30.   else\mathrm{else}
  31.     λl=θl\lambda_{l} = \theta_{l}
  32.   endif\mathrm{endif}
  33. end\mathrm{end}

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 (min⁡(kkeep,size/nlocal)\min(k_{keep}, \text{size}/n_{local}) vectors). If only the leading nevnev vectors are needed, allocate EigenVec with nlocal×nevn_{local} \times nev 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.