gko::solver::Ir#

Iterative refinement. Approximately solves the residual equation \(A e = r\) with an inner solver, then updates the iterate with the relaxation factor \(\alpha\). With \(\alpha = 1\) this is classical iterative refinement; with \(\alpha \ne 1\) and the identity inner solver it is Richardson iteration.

Each inner solve starts from a zero initial guess by default (inner_initial_guess = initial_guess_mode::zero); initial_guess_mode::rhs starts it from the residual instead, which can save inner iterations when the eigenvalues of \(A\) are close to 1 but makes IR diverge when they are far from 1.

template<typename ValueType = default_precision>
class Ir #

Inherits from

  • public gko::LinOp

  • public gko::solver::EnableSolverBase<Ir<default_precision>>

  • public gko::solver::EnableIterativeBase<Ir<default_precision>>

  • public gko::solver::EnableApplyWithInitialGuess<Ir<default_precision>>

  • public gko::Transposable

Iterative refinement (IR) is an iterative method that uses another coarse method to approximate the error of the current solution via the current residual. Moreover, it can be also considered as preconditioned Richardson iteration with relaxation factor = 1.

Let \( x_k \) be the approximation of the solution of \( A x = b \) after \( k \) iterations and let \( x \) denote the exact solution. The residual and the error of \( x_k \) are

\[ r_k = b - A x_k, \qquad e_k = x - x_k, \]
and they are linked by the residual equation \( A e_k = A x - A x_k = b - A x_k = r_k \). Knowing \( e_k \) exactly would give the exact solution in a single update \( x = x_k + e_k \). Instead of solving \( A e_k = r_k \) exactly, IR approximates \( e_k \) by \( \tilde e_k \) using a cheap inner solver, applies that correction with a relaxation factor \( \alpha \),
\[ x_{k+1} = x_k + \alpha \tilde e_k, \]
and repeats the process with the updated iterate. Written with the names used below, \( x_k \) is solution, \( r_k \) is residual and \( \tilde e_k \) is error:

solution = initial_guess
while not converged:
    residual = b - A solution
    error = solver(A, residual)
    solution = solution + relaxation_factor * error

With relaxation_factor equal to 1 (default), the solver is Iterative Refinement, with relaxation_factor equal to a value other than 1, the solver is a Richardson iteration, with possibility for additional preconditioning.

Assume \( \alpha = 1 \) and that solver has accuracy \( c \), i.e. \( \| e_k - \tilde e_k \| \le c \| e_k \| \). Then iterative refinement converges with a convergence rate of \( c \): from \( e_k - \tilde e_k = (x - x_k) - \tilde e_k = x - x_{k+1} \) it follows that \( \| x - x_{k+1} \| \le c \| x - x_k \| \).

Unless otherwise specified via the solver factory parameter, this implementation uses the identity operator (i.e. the solver that approximates the solution of a system \( A x = b \) by setting \( x := b \)) as the default inner solver. It leaves the residual unchanged, \( \tilde e_k = r_k \), so the iteration reduces to the Richardson iteration \( x_{k+1} = x_k + \alpha r_k \), which converges for every initial guess if and only if \( | 1 - \alpha \lambda | < 1 \) holds for every eigenvalue \( \lambda \) of \( A \).

References

Template Parameters:

ValueType – precision of matrix elements

Public Functions

virtual std::unique_ptr<LinOp> transpose() const override#

Returns a LinOp representing the transpose of the Transposable object.

Returns:

a pointer to the new transposed object

virtual std::unique_ptr<LinOp> conj_transpose() const override#

Returns a LinOp representing the conjugate transpose of the Transposable object.

Returns:

a pointer to the new conjugate transposed object

inline bool apply_uses_initial_guess() const override#

Return true as iterative solvers use the data in x as an initial guess.

Returns:

true as iterative solvers use the data in x as an initial guess.

inline std::shared_ptr<const LinOp> get_solver() const#

Returns the solver operator used as the inner solver.

Returns:

the solver operator used as the inner solver

void set_solver(std::shared_ptr<const LinOp> new_solver)#

Sets the solver operator used as the inner solver.

Parameters:

new_solver – the new inner solver

Ir &operator=(const Ir&)#

Copy-assigns an IR solver. Preserves the executor, shallow-copies inner solver, stopping criterion and system matrix. If the executors mismatch, clones inner solver, stopping criterion and system matrix onto this executor.

Ir &operator=(Ir&&)#

Move-assigns an IR solver. Preserves the executor, moves inner solver, stopping criterion and system matrix. If the executors mismatch, clones inner solver, stopping criterion and system matrix onto this executor. The moved-from object is empty (0x0 and nullptr inner solver, stopping criterion and system matrix)

Ir(const Ir&)#

Copy-constructs an IR solver. Inherits the executor, shallow-copies inner solver, stopping criterion and system matrix.

Ir(Ir&&)#

Move-constructs an IR solver. Preserves the executor, moves inner solver, stopping criterion and system matrix. The moved-from object is empty (0x0 and nullptr inner solver, stopping criterion and system matrix)

Public Static Functions

static parameters_type parse(
const config::pnode &config,
const config::registry &context,
const config::type_descriptor &td_for_child = config::make_type_descriptor<ValueType>(),
)#

Create the parameters from the property_tree. Because this is directly tied to the specific type, the value/index type settings within config are ignored and type_descriptor is only used for children configs.

Parameters:

  • config – the property tree for setting

  • context – the registry

  • td_for_child – the type descriptor for children configs. The default uses the value type of this class.

Returns:

parameters

struct parameters_type #

Inherits from

  • public gko::solver::enable_iterative_solver_factory_parameters<parameters_type, Factory>

Public Members

std::shared_ptr<const LinOpFactory> solver#

Inner solver factory.

std::shared_ptr<const LinOp> generated_solver#

Already generated solver. If one is provided, the factory solver will be ignored.

ValueType relaxation_factor#

Relaxation factor for Richardson iteration

initial_guess_mode default_initial_guess#

Default initial guess mode. The available options are under initial_guess_mode.

initial_guess_mode inner_initial_guess#

Initial guess of the inner solver for each correction A * d = residual, if the inner solver uses an initial guess: initial_guess_mode::zero (scale-invariant) or initial_guess_mode::rhs (the residual). Starting from the residual can save inner iterations when the eigenvalues of A are close to 1, but makes IR diverge when they are far from 1. initial_guess_mode::provided is not supported.