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 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 (), immediately after the solution is updated by with the search direction and the step length , and the residual by the recurrence , the relative recurrence residual is checked (for the whole method, see the algorithm in the User Guide). The check uses the recurrence residual, not the true residual . Before the iteration, the relative initial residual of is checked, and if it is below no iteration is done. The results are as follows (checked from the top row).
| Condition | State | Solution | Iterations | Residual |
|---|---|---|---|---|
| Relative initial residual 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 | of that iteration | That non-finite value | |
| Relative residual | CONVERGED_RTOL | That relative residual | ||
| None of the above in iterations | DIVERGED_ITS | The last relative residual |
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 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 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, during the iteration lags by up to PARCEL_PSTEP iterations (“Recurrence Residual and True Residual” in the User Guide).
2.2 pbicgstab
At iteration (), from the search direction it computes , , ( is the dual residual fixed to the initial residual , ), the intermediate residual , , , , and updates the solution by and the residual by the recurrence (for the whole method, see the algorithm in the User Guide; is and is there). As in pcg, the convergence check uses the relative recurrence residual right after the update. If the relative initial residual is below 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 , , and the coefficient of the next search direction are formed. The results are as follows (checked from the top row within an iteration).
| When checked | Condition | State | Solution | Iterations | Residual |
|---|---|---|---|---|---|
| Before forming | is 0 or non-finite | DIVERGED_BREAKDOWN | at the start of that iteration | Relative residual of the previous iteration (the relative initial residual at the first iteration) | |
| Before forming | () and non-finite | DIVERGED_NANORINF | |||
| Same | and | CONVERGED_RTOL | |||
| Same | otherwise | DIVERGED_BREAKDOWN | |||
| After the update | Relative residual non-finite | DIVERGED_NANORINF | That non-finite value | ||
| Same | Relative residual | CONVERGED_RTOL | That relative residual | ||
| After the convergence check | or ( cannot be formed) | DIVERGED_BREAKDOWN | That relative residual | ||
| After iterations | None of the above | DIVERGED_ITS | The last relative residual |
is a “lucky breakdown” in which becomes 0. In that case would be , so it is not formed and the iteration stops with . or 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. follows the common handling in the linear solvers.
Rank 0 writes the line <iteration> : residual norm = ... at every iteration ( for an iteration stopped at ). For breakdowns other than , 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 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, 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 (; ) with the relative residual of the true residual computed from the approximate solution at that point ( is the initial guess). If it is not satisfied, the Arnoldi process of is advanced by columns from , 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 columns have been built. The results are as follows.
| Condition | State | Solution | Iterations | Residual |
|---|---|---|---|---|
| Relative residual non-finite at the start of restart | DIVERGED_NANORINF | That non-finite value | ||
| Relative residual at the start of restart | CONVERGED_RTOL | That relative residual | ||
| or non-finite in the Arnoldi process of restart | DIVERGED_NANORINF | (not updated) | Relative residual at the start of restart | |
| Lucky breakdown in restart with no column usable for the update ( singular at the first column) | DIVERGED_BREAKDOWN (note) | (not updated) | True relative residual at termination | |
| restarts completed | CONVERGED_RTOL if the true relative residual at termination is below , DIVERGED_NANORINF if it is non-finite, DIVERGED_ITS otherwise | True relative residual at termination |
(Note) If the true relative residual at termination is below , the state is CONVERGED_RTOL (this does not normally happen because was not updated).
The iteration count is counted as the number of restarts times (a restart cut short by a lucky breakdown also counts as ). If is not a multiple of , only the last restart stops the Arnoldi process at 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 (even if , iterations are done). If is a multiple of , every restart has 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. follows the common handling in the linear solvers.
In column of the Arnoldi process, is orthogonalized against , the coefficients are (), and the norm after orthogonalization is . If becomes times or less (or 0) of the norm of before orthogonalization, , the Krylov subspace is regarded as invariant (a “lucky breakdown”). With , a Givens rotation is also applied to column , and the Arnoldi process stops at that column. If the rotated diagonal element is nonzero and finite, the least-squares problem is solved with the first columns, otherwise with the first columns, to obtain , 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 ( is 0 at ), 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 and updating in the order ), () are computed together (one collective communication) and .
2.4 pcagmres
This section covers the case where 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 (; ) with the relative residual of the true residual . No check is done during basis generation and Givens rotations; unless a lucky breakdown (below) occurs, one restart builds blocks of basis vectors, in total, before updating the solution. The Givens rotations are applied together after the Hessenberg matrix of the 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 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 | DIVERGED_NANORINF | That non-finite value | ||
| Relative residual at the start of restart | CONVERGED_RTOL | That relative residual | ||
| Lucky breakdown in restart with no valid column | DIVERGED_BREAKDOWN (same note as pgmres) | (not updated) | True relative residual at termination | |
| restarts completed | Determined by the true relative residual at termination, as in pgmres | True relative residual at termination |
The iteration count is counted as the number of restarts times (the total number of basis vectors built). If is not a multiple of , the last restart solves the least-squares problem with only the remaining columns (the solution equals that of GMRES with that iteration count). Since the basis is built in blocks of , the SpMV and preconditioner for the unused basis vectors of the last block (at most ) are executed in addition (not counted as iterations). The iteration count when the limit is reached is exactly . 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 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 of Arnoldi, but as a diagonal element of the upper triangular factor of the QR factorization becoming nearly 0 (rank deficiency). After the QR factorization of each block (the basis vectors in the first block; in later blocks, the basis vectors orthogonalized against of the previous blocks), PARCEL compares the diagonal element of each column of with the norm of that column (including the components removed against the previous blocks), and regards the first column where it is times or less (including 0 or non-finite) as rank deficient. is the larger of a value determined by the unit roundoff of the arithmetic precision of the QR factorization ( for classical and modified Gram-Schmidt, for Cholesky QR) and the fluctuation due to the unit roundoff of the data precision of the basis. If both precisions are the same, it is the former. After the rank-deficient column, 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, of each column is compared with the norm of the column; if it is 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 , the least-squares problem is solved with the first 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 becomes ill-conditioned). If there is no valid column, it ends with DIVERGED_BREAKDOWN as in the table.
With AUTO (default), only when and the QR factorization is Cholesky QR, the orthonormal basis is not formed explicitly, and the solution update uses the product of the basis and () instead of . With EXPLICIT, 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 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.
- is obtained from the Cholesky factorization of the Gram matrix. The Gram matrix (in the first block, the inner products of the basis vectors; in later blocks, the inner products and of the new basis vectors and the previous basis ) is formed by aggregating local values with collective communication: once in the first block and twice in later blocks.
- The diagonal elements of the Cholesky factorization are the square roots of the absolute values of the radicands (the process does not stop if they become negative or 0).
- Rank deficiency is detected, as for Cholesky QR when is formed, by the ratio of the diagonal element of to the column norm. The threshold is the larger of with the unit roundoff of the arithmetic precision of the QR factorization and with the unit roundoff of the coarsest of the storage precisions of the basis.
- The lines written by rank 0 on a breakdown start with
pcagmres (Q = implicit) :.
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 (), from it computes (; when the spectrum of the preconditioned matrix is computed) and the Rayleigh quotient , and sets ( 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 () and is done at the end of every iteration. If , it divides by ; if both are 0, . The residual ( in the 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 , , , non-finite | DIVERGED_NANORINF | The last finite estimate (0 at ) | NaN | ||
| exactly 0 () | DIVERGED_BREAKDOWN | (0 at ) | (NaN for ) | ||
| non-finite | DIVERGED_NANORINF | NaN | |||
| CONVERGED_RTOL | |||||
| None of the above in iterations | DIVERGED_ITS | The last |
The returned as the eigenvector has the same direction as and is not normalized. in the table is normalized for and is the initial vector for . becomes exactly 0 when lies in the null space, or when all elements underflow at low precision; the normalization that forms would then divide by 0, so the iteration stops. When stopped on a non-finite value or , 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 and 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 ); use ks_arnoldi in that case.
2.7 inverse_power
In the mode (the spectrum of the preconditioned matrix is not computed), the preconditioner 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. only speeds up the convergence of the inner iteration; the returned eigenvalue is the eigenvalue of regardless of . In the mode, the inner pgmres solves and returns the internal variable (without the final multiplication by ). Then is the Rayleigh quotient of at and converges to the eigenvalue of of smallest magnitude. The returned eigenvector is the right eigenvector of . As in the power method, is built once from with the preconditioner settings. When 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 (), the inner linear solver solves ( in the mode) from the initial guess , and and are computed (for the whole method, see the algorithm in the User Guide). 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 (; 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 (0 at ) | NaN | ||
| or non-finite | DIVERGED_NANORINF | NaN | |||
| The solution of the inner linear solver exactly 0 | DIVERGED_BREAKDOWN | (NaN for ) | |||
| or non-finite | DIVERGED_NANORINF | NaN | |||
| CONVERGED_RTOL | |||||
| None of the above in iterations | DIVERGED_ITS |
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 as it is, so the inner linear solver must converge more tightly than the outer .
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 .
2.8 ks_arnoldi
is the operator to which the Arnoldi process is applied, and a Ritz pair is an approximate eigenpair of (symbols). For the whole method, see the algorithm in the User Guide. In shift-invert mode, (or ) 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 ( is the initial vector). If is 0 or non-finite, is replaced by the default initial vector of the power method (built from the global row numbers; rank 0 reports this). In column , is orthogonalized against , the coefficients are (), the norm after orthogonalization is , and . is the matrix with the elements .
The orthogonalization is done by CGS2 [6], which applies the classical Gram-Schmidt method twice (, repeated twice, and the sum of the coefficients gives ; 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 at a restart is done within the basis , without allocating a second basis (for types not involving double-double and ; otherwise a second basis of columns is allocated).
The convergence check is done once in each restart, after the Arnoldi decomposition has been extended to columns. The eigenpairs of are sorted in descending order of , and for the first Ritz pairs , the estimate ( is the -th unit vector) of the relative residual with respect to is compared with . For a complex conjugate pair, the norm of the two components (real and imaginary) is used. Ritz pairs with are counted as not satisfying the check. In shift-invert mode, the check is done on (before the transformation). It converges when all estimates are or less. Otherwise the real Schur decomposition of is reordered to bring the Ritz values of large to the front, the Schur vectors (; it can be because a complex conjugate pair is kept together) are kept, and the next restart begins. The Arnoldi decomposition is brought back to columns with applications of in the first cycle and in later cycles. The results are as follows.
| Condition | State | Residual |
|---|---|---|
| or 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 |
| residual estimates (no random direction in the basis) | CONVERGED_RTOL | Maximum of the residual estimates |
| Same (random directions in the basis), and the true residuals also | CONVERGED_RTOL | Maximum of the true residuals |
| Same (random directions in the basis), and a true residual exceeds | DIVERGED_BREAKDOWN | Maximum of the true residuals |
| Invariant subspace (below) confirmed by true residuals | 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 | 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 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 (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 restarts).
If becomes times or less (or 0) of the norm of before orthogonalization, , the Krylov subspace is regarded as invariant (an invariant subspace) and . The residual estimates of the Ritz pairs then become 0, but with a low-precision basis, after orthogonalization can become 0 through cancellation or underflow, giving a false invariant subspace, so it is handled as follows.
- If the effective dimension is or more, the true residuals (; about additional applications of ) are computed for the Ritz pairs of largest of the leading block of . If all are or less, the extension of the Arnoldi decomposition and the restarts stop at the effective dimension , with CONVERGED_RTOL. The residual is the maximum of these true residuals.
- If this cannot be confirmed (the effective dimension is below , or a true residual exceeds ), the process does not stop: a random vector built from the global row number, the restart number and the column number is orthogonalized against by CGS2 to give , and the Arnoldi decomposition continues up to with ( becomes block upper triangular). The random vector depends only on the row numbers, so it does not depend on the number of MPI partitions. At most 3 random directions are inserted in one Arnoldi process.
- With random directions in the basis, blocks with zero residual estimates remain, so even when the residual estimates satisfy , convergence is accepted only after confirmation by the true residuals as in (A). Otherwise the state is DIVERGED_BREAKDOWN.
- If more than 3 random directions would be needed, or a random vector almost vanishes in the orthogonalization (its norm after orthogonalization is times or less of that before; the space spanned by is exhausted), the process stops at that effective dimension, and since it cannot be confirmed by the true residual, the state is DIVERGED_BREAKDOWN. It is also DIVERGED_BREAKDOWN if the effective dimension is below .
If the run ends with an effective dimension below , the missing eigenvalues and eigenvectors are returned as 0 (rank 0 reports this).
The eigendecomposition of 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 ( 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 ), the state is DIVERGED_BREAKDOWN. The sort by places NaN last. Rank 0 writes the intermediate decisions and the reasons for stopping on lines starting with [KS].
The output is pairs in descending order of (the first are checked for convergence; Output of Eigenvalues and Eigenvectors). In shift-invert mode, descending corresponds to closest to first. Ritz values for which in the inverse transformation of shift-invert are returned as the eigenvalue .