gko::preconditioner::Isai#

Incomplete Sparse Approximate Inverse preconditioner. Computes a sparse approximation \(M_A \approx A^{-1}\) (or its triangular- / Cholesky-factor variants) directly, so apply is a single sparse matrix-vector product without any triangular solve. Useful when triangular substitution becomes a serial bottleneck on highly-parallel hardware.

template<isai_type IsaiType, typename ValueType, typename IndexType>
class Isai #

Inherits from

The Incomplete Sparse Approximate Inverse (ISAI) Preconditioner generates an approximate inverse matrix for a given square matrix A, lower triangular matrix L, upper triangular matrix U or symmetric positive (spd) matrix B.

Let \( M_A \approx A^{-1} \) denote the approximate inverse of a general matrix \( A \), and similarly \( M_L \approx L^{-1} \), \( M_U \approx U^{-1} \) for lower and upper triangular matrices, and \( M_C \approx C^{-1} \) for the Cholesky factor of an SPD matrix \( B = C^T C \) (the last case is commonly called a Factorized Sparse Approximate Inverse, FSPAI). Applying the preconditioner then computes, depending on the type of the Isai,

\[ M_A\, x, \qquad M_U\, x, \qquad M_L\, x, \qquad \text{or} \qquad M_C^{T}\, M_C\, x, \]
for a given vector \( x \) (which may carry multiple right-hand sides).

The sparsity pattern used for the approximate inverse of \( A \), \( L \) and \( U \) is the same as the sparsity pattern of the respective matrix. For \( B \), the sparsity pattern of \( M_C \) matches the sparsity pattern of the lower triangular half of \( B \).

Note that, except for the SPD case, in general \( \mathrm{ISAI}(A)^T \ne \mathrm{ISAI}(A^T) \).

References

Note

GPU implementations can only handle the vector unit width width (warp size for CUDA) as number of elements per row in the sparse matrix. If there are more than width elements per row, the remaining elements will be ignored.

Template Parameters:

  • IsaiType – determines if the ISAI is generated for a general square matrix, a lower triangular matrix, an upper triangular matrix or an spd matrix

  • ValueType – precision of matrix elements

  • IndexType – precision of matrix indexes

Public Functions

inline std::shared_ptr<const typename std::conditional<IsaiType == isai_type::spd, Comp, Csr>::type> get_approximate_inverse(
) const#

Returns the approximate inverse of the given matrix (either a CSR matrix for IsaiType general, upper or lower or a composition of two CSR matrices for IsaiType spd).

Returns:

the generated approximate inverse

Isai &operator=(const Isai &other)#

Copy-assigns an ISAI preconditioner. Preserves the executor, shallow-copies the matrix and parameters. Creates a clone of the matrix if it is on the wrong executor.

Isai &operator=(Isai &&other)#

Move-assigns an ISAI preconditioner. Preserves the executor, moves the matrix and parameters. Creates a clone of the matrix if it is on the wrong executor. The moved-from object is empty (0x0 with nullptr matrix and default parameters)

Isai(const Isai &other)#

Copy-constructs an ISAI preconditioner. Inherits the executor, shallow-copies the matrix and parameters.

Isai(Isai &&other)#

Move-constructs an ISAI preconditioner. Inherits the executor, moves the matrix and parameters. The moved-from object is empty (0x0 with nullptr matrix and default parameters)

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

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, IndexType>(),
)#

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/index type of this class.

Returns:

parameters

struct parameters_type#

Public Members

bool skip_sorting#

Optimization parameter that skips the sorting of the input matrix (only skip if it is known that it is already sorted).

The algorithm to create the approximate inverses requires the input matrix to be sorted. If it is, this parameter can be set to true to skip the sorting for better performance.

int sparsity_power#

Which power of the input matrix should be used for the sparsity pattern.

The algorithm symbolically computes M^n and uses this sparsity pattern for the sparse inverse. Must be at least 1, default value 1.

size_type excess_limit#

Size limit for the excess system.

For rows with more than 32 nonzero entries, the algorithm builds up an excess system which is solved with sparse triangular solves (for upper or lower ISAI) or GMRES (for general ISAI). If this parameter is set to some m > 0, the excess system is solved as soon as its size supersedes m. This is repeated until the complete excess solution has been computed. Must be at least 0, default value 0.

std::shared_ptr<const LinOpFactory> excess_solver_factory#

Factory for the Excess System solver.

Defaults to using a triangular solver for upper and lower ISAI and to Block-Jacobi preconditioned GMRES for general and spd ISAI.