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

2 Convergence by Solver

For each solver, this chapter gives the method of the convergence check, and the convergence state and returned values when a breakdown or a non-finite value is encountered. It does not depend on the language. “Solution”, “iterations” and “residual” in the tables are the values of the results, and NN is the maximum number of iterations. The methods are described in the “Linear Solvers” chapter and the “Eigenvalue Solvers” chapter of the User Guide.

2.1 pcg

At each iteration ii (i=0,1,…i = 0, 1, \ldots), immediately after the solution is updated by x(i+1)=x(i)+α(i)p(i)x^{(i+1)} = x^{(i)} + \alpha^{(i)}p^{(i)} with the search direction p(i)p^{(i)} and the step length α(i)\alpha^{(i)}, and the residual by the recurrence r(i+1)=r(i)−α(i)Ap(i)r^{(i+1)} = r^{(i)} - \alpha^{(i)}Ap^{(i)}, the relative recurrence residual ∥r(i+1)∥/∥b∥\|r^{(i+1)}\| / \|b\| is checked (for the whole method, see the algorithm in the User Guide). The check uses the recurrence residual, not the true residual b−Ax(i+1)b - Ax^{(i+1)}. Before the iteration, the relative initial residual of r(0)=b−Ax(0)r^{(0)} = b - Ax^{(0)} is checked, and if it is below toltol no iteration is done. The results are as follows (checked from the top row).

Condition State Solution Iterations Residual
Relative initial residual <tol< tol before the iteration CONVERGED_RTOL Initial guess (unchanged) 0 Relative initial residual (the true residual has the same value)
Relative residual non-finite (NaN / Inf) DIVERGED_NANORINF x(i+1)x^{(i+1)} of that iteration i+1i + 1 That non-finite value
Relative residual <tol< tol CONVERGED_RTOL x(i+1)x^{(i+1)} i+1i + 1 That relative residual
None of the above in NN iterations DIVERGED_ITS x(N)x^{(N)} NN The last relative residual

∥b∥=0\|b\| = 0 follows the common handling in the linear solvers. Breakdowns such as division by zero are not detected, so the state is never DIVERGED_BREAKDOWN; if the residual becomes non-finite as a result, the state is DIVERGED_NANORINF. Rank 0 writes the line <iteration> : residual norm = ... at every iteration. The true relative residual ∥b−Ax∥/∥b∥\|b - Ax\| / \|b\| is computed after the iteration, written on the line finish : residual true norm, and returned as the true residual; it is not used for the check.

The solution is updated in groups of PARCEL_PSTEP iterations (environment variable, default 1), and the remainder is added at termination (whatever the reason), so the returned xx is as in the table above. With the default 1, a single search direction is kept. With PARCEL_PSTEP=4, a history of 4 search directions is kept (memory of 3 vectors), and the solver becomes slightly faster because the solution is read and written less often (“Choosing Between Memory and Speed” in the User Guide). With PARCEL_PSTEP of 2 or more, xx during the iteration lags by up to PARCEL_PSTEP iterations (“Recurrence Residual and True Residual” in the User Guide).

2.2 pbicgstab

At iteration ii (i=0,1,…i = 0, 1, \ldots), from the search direction p(i)p^{(i)} it computes p̂=K−1p(i)\hat{p} = K^{-1}p^{(i)}, q=Ap̂q = A\hat{p}, α=ρ(i)/⟨r*,q⟩\alpha = \rho^{(i)} / \langle r^{\ast},q \rangle (r*r^{\ast} is the dual residual fixed to the initial residual r(0)r^{(0)}, ρ(i)=⟨r*,r(i)⟩\rho^{(i)} = \langle r^{\ast},r^{(i)} \rangle), the intermediate residual e=r(i)−αqe = r^{(i)} - \alpha q, ê=K−1e\hat{e} = K^{-1}e, v=Aêv = A\hat{e}, ω=⟨e,v⟩/⟨v,v⟩\omega = \langle e,v \rangle / \langle v,v \rangle, and updates the solution by x(i+1)=x(i)+αp̂+ωêx^{(i+1)} = x^{(i)} + \alpha\hat{p} + \omega\hat{e} and the residual by the recurrence r(i+1)=e−ωvr^{(i+1)} = e - \omega v (for the whole method, see the algorithm in the User Guide; ω\omega is c3c_{3} and ρ\rho is c1c_{1} there). As in pcg, the convergence check uses the relative recurrence residual ∥r(i+1)∥/∥b∥\|r^{(i+1)}\| / \|b\| right after the update. If the relative initial residual is below toltol before the iteration, it returns CONVERGED_RTOL without iterating, as pcg does (iteration count 0, solution left at the initial guess, residual and true residual equal to the relative initial residual). Breakdowns are checked before α\alpha, ω\omega, and the coefficient of the next search direction β=ρ(i+1)/(⟨r*,q⟩ω)\beta = \rho^{(i+1)} / (\langle r^{\ast},q \rangle\omega) are formed. The results are as follows (checked from the top row within an iteration).

When checked Condition State Solution Iterations Residual
Before forming α\alpha ⟨r*,q⟩\langle r^{\ast},q \rangle is 0 or non-finite DIVERGED_BREAKDOWN x(i)x^{(i)} at the start of that iteration ii Relative residual of the previous iteration (the relative initial residual at the first iteration)
Before forming ω\omega v=0v = 0 (⟨v,v⟩=0\langle v,v \rangle = 0) and ∥e∥/∥b∥\|e\|/\|b\| non-finite DIVERGED_NANORINF x(i)+αp̂x^{(i)} + \alpha\hat{p} i+1i + 1 ∥e∥/∥b∥\|e\|/\|b\|
Same v=0v = 0 and ∥e∥/∥b∥<tol\|e\|/\|b\| < tol CONVERGED_RTOL x(i)+αp̂x^{(i)} + \alpha\hat{p} i+1i + 1 ∥e∥/∥b∥\|e\|/\|b\|
Same v=0v = 0 otherwise DIVERGED_BREAKDOWN x(i)+αp̂x^{(i)} + \alpha\hat{p} i+1i + 1 ∥e∥/∥b∥\|e\|/\|b\|
After the update Relative residual non-finite DIVERGED_NANORINF x(i+1)x^{(i+1)} i+1i + 1 That non-finite value
Same Relative residual <tol< tol CONVERGED_RTOL x(i+1)x^{(i+1)} i+1i + 1 That relative residual
After the convergence check ω=0\omega = 0 or ρ(i+1)=0\rho^{(i+1)} = 0 (β\beta cannot be formed) DIVERGED_BREAKDOWN x(i+1)x^{(i+1)} i+1i + 1 That relative residual
After NN iterations None of the above DIVERGED_ITS x(N)x^{(N)} NN The last relative residual

v=Aê=0v = A\hat{e} = 0 is a “lucky breakdown” in which ee becomes 0. In that case ω\omega would be 0/00/0, so it is not formed and the iteration stops with x(i)+αp̂x^{(i)} + \alpha\hat{p}. ω=0\omega = 0 or ρ(i+1)=0\rho^{(i+1)} = 0 is detected after the convergence check, so a converged iteration is not treated as a breakdown. All checks use inner products aggregated over all ranks, so all ranks take the same branch. ∥b∥=0\|b\| = 0 follows the common handling in the linear solvers.

Rank 0 writes the line <iteration> : residual norm = ... at every iteration (∥e∥/∥b∥\|e\|/\|b\| for an iteration stopped at v=0v = 0). For breakdowns other than v=0v = 0, it writes pbicgstab breakdown : followed by the cause (<r0,q> = 0, <r0,q> is not finite, omega (c3) = 0, rho (<r0,r>) = 0) and the iteration count. As in pcg, the true relative residual ∥b−Ax∥/∥b∥\|b - Ax\| / \|b\| is computed at termination, written on the line finish : residual true norm, and only returned as the true residual.

In configurations whose inner-product arithmetic precision is FP16, ⟨r*,q⟩\langle r^{\ast},q \rangle can become 0 or non-finite as the relative residual approaches the limit of the precision, ending with DIVERGED_BREAKDOWN (“Known Limits at Low Precision” in the User Guide).

2.3 pgmres

The convergence check is done at the start of each restart jj (j=0,1,…,J−1j = 0, 1, \ldots, J - 1; J=⌈N/m⌉J = \lceil N/m \rceil) with the relative residual ∥r∥/∥b∥\|r\| / \|b\| of the true residual r=b−Ax(j)r = b - Ax^{(j)} computed from the approximate solution x(j)x^{(j)} at that point (x(0)x^{(0)} is the initial guess). If it is not satisfied, the Arnoldi process of AK−1AK^{-1} is advanced by mm columns from v1=r/∥r∥v_{1} = r / \|r\|, x(j+1)x^{(j+1)} is obtained by the correction that minimizes the residual norm, and the next restart begins (for the whole method, see the algorithm in the User Guide). No check is done during the Arnoldi process. The residual norm obtained by Givens rotations (the last component of the rotated right-hand side) is not used for the check; unless a lucky breakdown (next paragraph) occurs, the solution is updated after mm columns have been built. The results are as follows.

Condition State Solution Iterations Residual
Relative residual non-finite at the start of restart jj DIVERGED_NANORINF x(j)x^{(j)} jmjm That non-finite value
Relative residual <tol< tol at the start of restart jj CONVERGED_RTOL x(j)x^{(j)} jmjm That relative residual
hk,ih_{k,i} or hi+1,ih_{i+1,i} non-finite in the Arnoldi process of restart jj DIVERGED_NANORINF x(j)x^{(j)} (not updated) jmjm Relative residual at the start of restart jj
Lucky breakdown in restart jj with no column usable for the update (HH singular at the first column) DIVERGED_BREAKDOWN (note) x(j)x^{(j)} (not updated) jmjm True relative residual at termination
JJ restarts completed CONVERGED_RTOL if the true relative residual at termination is below toltol, DIVERGED_NANORINF if it is non-finite, DIVERGED_ITS otherwise x(J)x^{(J)} NN True relative residual at termination

(Note) If the true relative residual at termination is below toltol, the state is CONVERGED_RTOL (this does not normally happen because xx was not updated).

The iteration count is counted as the number of restarts times mm (a restart cut short by a lucky breakdown also counts as mm). If NN is not a multiple of mm, only the last restart stops the Arnoldi process at N−(J−1)mN - (J-1)m columns and solves the least-squares problem with that number of columns to update the solution. The iteration count when the limit is reached is therefore exactly NN (even if N<mN < m, NN iterations are done). If NN is a multiple of mm, every restart has mm columns. The true relative residual is also computed at termination, written on the line finish : residual true norm, and returned as the true residual. Rank 0 writes the line <iteration> : residual norm = ... at the start of each restart. ∥b∥=0\|b\| = 0 follows the common handling in the linear solvers.

In column ii of the Arnoldi process, w=AK−1viw = AK^{-1}v_{i} is orthogonalized against v1,…,viv_{1},\ldots,v_{i}, the coefficients are hk,ih_{k,i} (k=1,…,ik = 1,\ldots,i), and the norm ∥w∥\|w\| after orthogonalization is hi+1,ih_{i+1,i}. If hi+1,ih_{i+1,i} becomes 10−1410^{-14} times or less (or 0) of the norm of ww before orthogonalization, ∑k≤ihk,i2+hi+1,i2\sqrt{\sum_{k \leq i} h_{k,i}^{2} + h_{i+1,i}^{2}}, the Krylov subspace is regarded as invariant (a “lucky breakdown”). With hi+1,i=0h_{i+1,i} = 0, a Givens rotation is also applied to column ii, and the Arnoldi process stops at that column. If the rotated diagonal element hi,ih_{i,i} is nonzero and finite, the least-squares problem is solved with the first ii columns, otherwise with the first i−1i - 1 columns, to obtain x(j+1)x^{(j+1)}, which is checked by the true residual at the start of the next restart. Rank 0 writes the line pgmres : Arnoldi breakdown at column .... If there is no usable column (h1,1h_{1,1} is 0 at i=1i = 1), it ends with DIVERGED_BREAKDOWN as in the table.

When the orthogonalization method is classical Gram-Schmidt, instead of the default modified Gram-Schmidt method (computing hk,i=⟨w,vk⟩h_{k,i} = \langle w,v_{k} \rangle and updating w=w−hk,ivkw = w - h_{k,i}v_{k} in the order k=1,…,ik = 1,\ldots,i), hk,i=⟨w,vk⟩h_{k,i} = \langle w,v_{k} \rangle (k=1,…,ik = 1,\ldots,i) are computed together (one collective communication) and w=w−∑khk,ivkw = w - \sum_{k} h_{k,i}v_{k}.

2.4 pcagmres

This section covers the case where QQ is formed (the Q mode AUTO or EXPLICIT). IMPLICIT is described in the next section. For the whole method, see the algorithm in the User Guide.

As in pgmres (pgmres), the convergence check is done at the start of each restart jj (j=0,1,…,J−1j = 0, 1, \ldots, J - 1; J=⌈N/(st)⌉J = \lceil N/(st) \rceil) with the relative residual ∥r∥/∥b∥\|r\| / \|b\| of the true residual r=b−Ax(j)r = b - Ax^{(j)}. No check is done during basis generation and Givens rotations; unless a lucky breakdown (below) occurs, one restart builds tt blocks of ss basis vectors, stst in total, before updating the solution. The Givens rotations are applied together after the Hessenberg matrix of the tt blocks has been assembled. The initial residual is also checked before the iteration (common handling in the linear solvers). The results are as follows.

Condition State Solution Iterations Residual
Relative initial residual <tol< tol before the iteration CONVERGED_RTOL Initial guess (unchanged) 0 Relative initial residual (the true residual has the same value)
Relative residual non-finite at the start of restart jj DIVERGED_NANORINF x(j)x^{(j)} jstjst That non-finite value
Relative residual <tol< tol at the start of restart jj CONVERGED_RTOL x(j)x^{(j)} jstjst That relative residual
Lucky breakdown in restart jj with no valid column DIVERGED_BREAKDOWN (same note as pgmres) x(j)x^{(j)} (not updated) jstjst True relative residual at termination
JJ restarts completed Determined by the true relative residual at termination, as in pgmres x(J)x^{(J)} NN True relative residual at termination

The iteration count is counted as the number of restarts times stst (the total number of basis vectors built). If NN is not a multiple of stst, the last restart solves the least-squares problem with only the remaining N−(J−1)stN - (J-1)st columns (the solution equals that of GMRES with that iteration count). Since the basis is built in blocks of ss, the SpMV and preconditioner for the unused basis vectors of the last block (at most s−1s - 1) are executed in addition (not counted as iterations). The iteration count when the limit is reached is exactly NN. When it returns at the check before the iteration, it does not write the line finish : residual true norm. Otherwise, the true relative residual at termination, the progress lines written by rank 0, and the handling of ∥b∥=0\|b\| = 0 are the same as in pgmres. Non-finite values in the Hessenberg matrix do not lead to DIVERGED_NANORINF; the columns are excluded from the valid ones as described next.

In CA-GMRES, when the Krylov subspace becomes invariant in the middle of a block, the subsequent basis vectors are linear combinations of the previous ones. This lucky breakdown appears not as hi+1,i=0h_{i+1,i} = 0 of Arnoldi, but as a diagonal element of the upper triangular factor RR of the QR factorization becoming nearly 0 (rank deficiency). After the QR factorization of each block (the s+1s + 1 basis vectors in the first block; in later blocks, the ss basis vectors orthogonalized against QQ of the previous blocks), PARCEL compares the diagonal element |Rjj||R_{jj}| of each column of RR with the norm of that column (including the components removed against the previous blocks), and regards the first column where it is τ\tau times or less (including 0 or non-finite) as rank deficient. τ\tau is the larger of a value determined by the unit roundoff uu of the arithmetic precision of the QR factorization (103u10^{3}u for classical and modified Gram-Schmidt, 102u10^{2}\sqrt{u} for Cholesky QR) and the fluctuation 10ub10u_{b} due to the unit roundoff ubu_{b} of the data precision of the basis. If both precisions are the same, it is the former. After the rank-deficient column, RR is replaced by the identity before the Hessenberg matrix is assembled, only the columns before it are valid (if the off-diagonal elements of that column are also non-finite, one more column before), and the basis generation of that restart stops. Rank 0 writes the line pcagmres : rank-deficient basis block. In addition, during the Givens rotations, hi+1,ih_{i+1,i} of each column is compared with the norm of the column; if it is 10−1410^{-14} times or less, the process stops at that column as in pgmres, and if the column has non-finite elements it stops just before it (rank 0 writes the line pcagmres : Arnoldi breakdown, solve with ... columns). When the valid columns number ℓ<st\ell < st, the least-squares problem is solved with the first ℓ\ell columns to update the solution, which is checked at the start of the next restart. These lines record that a rank deficiency was detected and the system was solved with the valid columns; they do not mean failure (they appear even in double precision when the monomial basis with s=8s = 8 becomes ill-conditioned). If there is no valid column, it ends with DIVERGED_BREAKDOWN as in the table.

With AUTO (default), only when t=1t = 1 and the QR factorization is Cholesky QR, the orthonormal basis QQ is not formed explicitly, and the solution update uses the product of the basis VV and R−1yR^{-1}y (V=QRV = QR) instead of ∑kykqk\sum_{k} y_{k}q_{k}. With EXPLICIT, QQ is formed in this case as well.

2.5 pcagmres (Q Not Formed)

When the Q mode is IMPLICIT, the convergence check, the convergence state and returned values, and the handling of lucky breakdowns are the same as when QQ is formed (previous section). The true relative residual at termination is computed and returned as the true residual. For the whole method, see the algorithm in the User Guide. The differences are as follows.

When the QR factorization is Cholesky QR by the moment method, the Gram matrix of the first block is built by the moment method described in the “QR Factorization” chapter (later blocks are built from inner products of the basis, as above). The conditions for its use are given in Q Modes and QR Factorization.

2.6 power

At iteration ii (i=0,1,…i = 0, 1, \ldots), from x(i)x^{(i)} it computes y=Azy = Az (z=x(i)z = x^{(i)}; z=K−1x(i)z = K^{-1}x^{(i)} when the spectrum of the preconditioned matrix is computed) and the Rayleigh quotient λ(i)=⟨x(i),y⟩/⟨x(i),x(i)⟩\lambda^{(i)} = \langle x^{(i)},y \rangle / \langle x^{(i)},x^{(i)} \rangle, and sets x(i+1)=y/∥y∥x^{(i+1)} = y / \|y\| (x(0)x^{(0)} is the initial vector built from the global row numbers and is not normalized; the first row of each rank is obtained with MPI_Exscan, so the initial vector does not depend on the row partitioning; for the whole method, see the algorithm in the User Guide). The convergence check uses the relative change of the eigenvalue estimate δ(i)=|λ(i)−λ(i−1)|/|λ(i)|\delta^{(i)} = |\lambda^{(i)} - \lambda^{(i-1)}| / |\lambda^{(i)}| (i≥1i \geq 1) and is done at the end of every iteration. If λ(i)=0\lambda^{(i)} = 0, it divides by |λ(i−1)||\lambda^{(i-1)}|; if both are 0, δ(i)=0\delta^{(i)} = 0. The residual ∥Ay−λy∥\|Ay - \lambda y\| (∥AK−1y−λy∥\|AK^{-1}y - \lambda y\| in the AK−1AK^{-1} mode) is not used as a stopping criterion. The results are as follows (checked from the top row within an iteration).

Condition State Eigenvalue Eigenvector Iterations Residual
Any of ⟨x(i),x(i)⟩\langle x^{(i)},x^{(i)} \rangle, ⟨y,y⟩\langle y,y \rangle, ⟨x(i),y⟩\langle x^{(i)},y \rangle, λ(i)\lambda^{(i)} non-finite DIVERGED_NANORINF The last finite estimate λ(i−1)\lambda^{(i-1)} (0 at i=0i = 0) x(i)x^{(i)} i+1i + 1 NaN
yy exactly 0 (⟨y,y⟩=0\langle y,y \rangle = 0) DIVERGED_BREAKDOWN λ(i−1)\lambda^{(i-1)} (0 at i=0i = 0) x(i)x^{(i)} i+1i + 1 δ(i−1)\delta^{(i-1)} (NaN for i≤1i \leq 1)
δ(i)\delta^{(i)} non-finite DIVERGED_NANORINF λ(i−1)\lambda^{(i-1)} x(i)x^{(i)} i+1i + 1 NaN
δ(i)<tol\delta^{(i)} < tol CONVERGED_RTOL λ(i)\lambda^{(i)} yy i+1i + 1 δ(i)\delta^{(i)}
None of the above in NN iterations DIVERGED_ITS λ(N−1)\lambda^{(N-1)} The last yy NN δ(N−1)\delta^{(N-1)}

The yy returned as the eigenvector has the same direction as x(i+1)x^{(i+1)} and is not normalized. x(i)x^{(i)} in the table is normalized for i≥1i \geq 1 and is the initial vector for i=0i = 0. yy becomes exactly 0 when x(i)x^{(i)} lies in the null space, or when all elements underflow at low precision; the normalization that forms x(i+1)x^{(i+1)} would then divide by 0, so the iteration stops. When stopped on a non-finite value or y=0y = 0, rank 0 writes the line power : non-finite value at itr = ... or power : A K^-1 x is exactly zero at itr = ... (breakdown). All values used for the checks are aggregated over all ranks, so all ranks stop at the same iteration. Rank 0 writes the line i : Eigen Value = ... at iterations with i<10i < 10 and ii a multiple of 50.

The eigenvalue of largest magnitude is assumed to be real and separated in magnitude from the second one (not checked). The method does not converge when the extreme eigenvalue sought is a complex conjugate pair or when several eigenvalues have the same magnitude (for example ±λ\pm\lambda); use ks_arnoldi in that case.

2.7 inverse_power

In the AA mode (the spectrum of the preconditioned matrix is not computed), the preconditioner KinK_{in} of the inner linear solver is specified with the preconditioner of the inner linear solver (no preconditioning can also be specified). The outer preconditioner settings are not used. KinK_{in} only speeds up the convergence of the inner iteration; the returned eigenvalue is the eigenvalue of AA regardless of KinK_{in}. In the AK−1AK^{-1} mode, the inner pgmres solves (AK−1)y=x(i)(AK^{-1})y = x^{(i)} and returns the internal variable yy (without the final multiplication by K−1K^{-1}). Then θ(i)\theta^{(i)} is the Rayleigh quotient of AK−1AK^{-1} at yy and converges to the eigenvalue of AK−1AK^{-1} of smallest magnitude. The returned eigenvector is the right eigenvector of AK−1AK^{-1}. As in the power method, KK is built once from AA with the preconditioner settings. When AA is symmetric definite, setting the type of the inner linear solver to pcg is faster, with fewer operations and collective communications per iteration. The eigenvalue obtained is the same.

At iteration ii (i=0,1,…i = 0, 1, \ldots), the inner linear solver solves Ay=x(i)Ay = x^{(i)} ((AK−1)y=x(i)(AK^{-1})y = x^{(i)} in the AK−1AK^{-1} mode) from the initial guess y=0y = 0, and θ(i)=⟨y,x(i)⟩/⟨y,y⟩\theta^{(i)} = \langle y,x^{(i)} \rangle / \langle y,y \rangle and x(i+1)=y/∥y∥x^{(i+1)} = y / \|y\| are computed (for the whole method, see the algorithm in the User Guide). x(0)x^{(0)} is the initial vector of the power method, normalized (if its norm is 0 or non-finite, the normalization is skipped and rank 0 reports this). As in the power method, the convergence check uses the relative change of the eigenvalue estimate δ(i)=|θ(i)−θ(i−1)|/|θ(i)|\delta^{(i)} = |\theta^{(i)} - \theta^{(i-1)}| / |\theta^{(i)}| (i≥1i \geq 1; a zero denominator is handled as in the power method) and is done at the end of every iteration. If the inner linear solver does not converge for a reason other than DIVERGED_NANORINF, the outer iteration continues and the case is counted in the number of inner solver failures. The results are as follows (checked from the top row within an iteration).

Condition State Eigenvalue Eigenvector Iterations Residual
The inner linear solver ended with DIVERGED_NANORINF DIVERGED_NANORINF The last finite θ(i−1)\theta^{(i-1)} (0 at i=0i = 0) x(i)x^{(i)} i+1i + 1 NaN
⟨y,x(i)⟩\langle y,x^{(i)} \rangle or ⟨y,y⟩\langle y,y \rangle non-finite DIVERGED_NANORINF θ(i−1)\theta^{(i-1)} x(i)x^{(i)} i+1i + 1 NaN
The solution yy of the inner linear solver exactly 0 DIVERGED_BREAKDOWN θ(i−1)\theta^{(i-1)} x(i)x^{(i)} i+1i + 1 δ(i−1)\delta^{(i-1)} (NaN for i≤1i \leq 1)
θ(i)\theta^{(i)} or δ(i)\delta^{(i)} non-finite DIVERGED_NANORINF θ(i−1)\theta^{(i-1)} x(i)x^{(i)} i+1i + 1 NaN
δ(i)<tol\delta^{(i)} < tol CONVERGED_RTOL θ(i)\theta^{(i)} x(i+1)x^{(i+1)} i+1i + 1 δ(i)\delta^{(i)}
None of the above in NN iterations DIVERGED_ITS θ(N−1)\theta^{(N-1)} x(N)x^{(N)} NN δ(N−1)\delta^{(N-1)}

The returned eigenvector is normalized. When the iteration is stopped, rank 0 reports it on one line starting with inverse_power :. That the values used for the checks are the same on all ranks, and the progress lines written by rank 0, are as in the power method. The error of the inner linear solver becomes the error of θ(i)\theta^{(i)} as it is, so the inner linear solver must converge more tightly than the outer toltol.

AA is assumed to be nonsingular, and the eigenvalue of smallest magnitude to be real (not checked). For a nonsymmetric matrix whose eigenvalue of smallest magnitude is a complex conjugate pair, the Rayleigh quotient does not converge; use the shift-invert mode of ks_arnoldi with σ=0\sigma = 0.

2.8 ks_arnoldi

Op\mathrm{Op} is the operator to which the Arnoldi process is applied, and a Ritz pair (θ,x)(\theta, x) is an approximate eigenpair of Op\mathrm{Op} (symbols). For the whole method, see the algorithm in the User Guide. In shift-invert mode, (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 by the inner pgmres (right preconditioning, modified Gram-Schmidt orthogonalization). The preconditioner of the inner pgmres is described in the notes on the eigenvalue solvers, and the defaults of its tolerance and other settings in the settings.

The Arnoldi process starts from v1=x(0)/∥x(0)∥v_{1} = x^{(0)} / \|x^{(0)}\| (x(0)x^{(0)} is the initial vector). If ∥x(0)∥\|x^{(0)}\| is 0 or non-finite, x(0)x^{(0)} is replaced by the default initial vector of the power method (built from the global row numbers; rank 0 reports this). In column jj, w=Opvjw = \mathrm{Op}\,v_{j} is orthogonalized against Vj=[v1,…,vj]V_{j} = [v_{1},\ldots,v_{j}], the coefficients are hi,jh_{i,j} (i≤ji \leq j), the norm after orthogonalization is hj+1,j=∥w∥h_{j+1,j} = \|w\|, and vj+1=w/hj+1,jv_{j+1} = w / h_{j+1,j}. HH is the m×mm \times m matrix with the elements hi,jh_{i,j}.

The orthogonalization is done by CGS2 [6], which applies the classical Gram-Schmidt method twice (ξ=VjTw\xi = V_{j}^{T}w, w=w−Vjξw = w - V_{j}\xi repeated twice, and the sum of the coefficients ξ\xi gives h1:j,jh_{1:j,j}; see the “QR Factorization” chapter). The second pass removes the components left by the first projection and keeps the basis orthogonal. The inner products of one pass are aggregated with one collective communication. Setting the orthogonalization method to modified Gram-Schmidt switches to applying the modified Gram-Schmidt method twice (inner product, collective communication and axpy for each column). Both restore orthogonality in the second pass, and the accuracy of the eigenvalues is the same. On CPU configurations with few local rows per rank the modified Gram-Schmidt method may be faster, and with many local rows on CPUs and on GPUs CGS2 is faster. The orthogonalization of random directions (below) uses the same method. Since reorthogonalization suppresses spurious (ghost) eigenvalues at multiple eigenvalues, locking and deflation are not implemented.

The contraction Vk=VmQ:,1:kV_{k} = V_{m}Q_{:,1:k} at a restart is done within the basis VV, without allocating a second basis (for types not involving double-double and kkeep+1≤32k_{keep} + 1 \leq 32; otherwise a second basis of m+1m + 1 columns is allocated).

The convergence check is done once in each restart, after the Arnoldi decomposition has been extended to mm columns. The eigenpairs (θl,yl)(\theta_{l}, y_{l}) of HH are sorted in descending order of |θl||\theta_{l}|, and for the first nevnev Ritz pairs (θl,Vmyl)(\theta_{l}, V_{m}y_{l}), the estimate |hm+1,m||emTyl|/|θl||h_{m+1,m}||e_{m}^{T}y_{l}| / |\theta_{l}| (eme_{m} is the mm-th unit vector) of the relative residual ∥Opx−θx∥/(|θ|∥x∥)\|\mathrm{Op}\,x - \theta x\| / (|\theta|\|x\|) with respect to Op\mathrm{Op} is compared with toltol. For a complex conjugate pair, the norm of the two components (real and imaginary) is used. Ritz pairs with |θl|<10−300|\theta_{l}| < 10^{-300} are counted as not satisfying the check. In shift-invert mode, the check is done on θ\theta (before the transformation). It converges when all nevnev estimates are toltol or less. Otherwise the real Schur decomposition of HH is reordered to bring the Ritz values of large |θ||\theta| to the front, the kk Schur vectors (kkeepk_{keep}; it can be kkeep+1k_{keep} + 1 because a complex conjugate pair is kept together) are kept, and the next restart begins. The Arnoldi decomposition is brought back to mm columns with mm applications of Op\mathrm{Op} in the first cycle and m−km - k in later cycles. The results are as follows.

Condition State Residual
hi,jh_{i,j} or hj+1,jh_{j+1,j} non-finite in the Arnoldi process DIVERGED_NANORINF The value so far
Ritz value or residual estimate of a target pair non-finite DIVERGED_NANORINF NaN
nevnev residual estimates ≤tol\leq tol (no random direction in the basis) CONVERGED_RTOL Maximum of the residual estimates
Same (random directions in the basis), and the true residuals also ≤tol\leq tol CONVERGED_RTOL Maximum of the true residuals
Same (random directions in the basis), and a true residual exceeds toltol DIVERGED_BREAKDOWN Maximum of the true residuals
Invariant subspace (below) confirmed by true residuals ≤tol\leq tol CONVERGED_RTOL Maximum of the true residuals
Stopped without confirming an invariant subspace by the true residual (limit of random directions, space exhausted) DIVERGED_BREAKDOWN Maximum of the residual estimates
Effective dimension of the invariant subspace below nevnev DIVERGED_BREAKDOWN The value so far
Invariant subspace reached but the check not satisfied DIVERGED_BREAKDOWN Maximum of the residual estimates
LAPACK failure (below) DIVERGED_BREAKDOWN The value so far
None of the above in NRN_{R} restarts DIVERGED_ITS Maximum of the last residual estimates

“The value so far” is the value obtained in the previous restart, and NaN if it stopped in the first restart. The iteration count is the number of restarts performed, including the one in which it stopped. In every case, the eigendecomposition of the last HH (the leading block of the effective dimension when stopped at an invariant subspace) is recomputed to form the Ritz pairs, which are output (the last Ritz pairs are returned even if it did not converge in NRN_{R} restarts).

If hj+1,jh_{j+1,j} becomes 10−1410^{-14} times or less (or 0) of the norm of ww before orthogonalization, ∑i≤jhi,j2+hj+1,j2\sqrt{\sum_{i \leq j} h_{i,j}^{2} + h_{j+1,j}^{2}}, the Krylov subspace is regarded as invariant (an invariant subspace) and hj+1,j=0h_{j+1,j} = 0. The residual estimates of the Ritz pairs then become 0, but with a low-precision basis, ww after orthogonalization can become 0 through cancellation or underflow, giving a false invariant subspace, so it is handled as follows.

If the run ends with an effective dimension below kkeepk_{keep}, the missing eigenvalues and eigenvectors are returned as 0 (rank 0 reports this).

The eigendecomposition of HH is computed with LAPACK dgeev, and the real Schur decomposition and reordering for the restart with dgees and dtrsen, on the host. Only rank 0 computes them and distributes the results to all ranks (HH is also made equal to the value on rank 0), so branches do not split between ranks through differences in rounding. If LAPACK fails (info nonzero, including the case where the number of vectors kept after dtrsen is not 1 or more and less than mm), the state is DIVERGED_BREAKDOWN. The sort by |θ||\theta| places NaN last. Rank 0 writes the intermediate decisions and the reasons for stopping on lines starting with [KS].

The output is kkeepk_{keep} pairs in descending order of |θ||\theta| (the first nevnev are checked for convergence; Output of Eigenvalues and Eigenvectors). In shift-invert mode, descending |θ||\theta| corresponds to closest to σ\sigma first. Ritz values for which |θ|2≤10−300|\theta|^{2} \leq 10^{-300} in the inverse transformation of shift-invert are returned as the eigenvalue +∞+\infty.