BLR Preconditioning

Apart from hierarchically semi-separable rank-structured matrices, the sparse multifrontal solver can also use Block Low-Rank (BLR) matrices to compress the fill-in. In the multifrontal method, computations are performed on dense matrices called frontal matrices. A frontal matrix can be approximated as a BLR matrix, but this will only be beneficial (compared to storing the frontal as a standard dense matrix and operating on it with BLAS/LAPACK routines) if the frontal matrix is large enough.

Rank-structured compression is not used by default in the STRUMPACK sparse solver (the default is to perform exact LU factorization), but BLR compression can be turned on/off via the command line:

--sp_compression blr
--sp_compression none

or via the C++ API as follows

void strumpack::SPOptions::set_compression(CompressionType::BLR);
void strumpack::SPOptions::set_compression(CompressionType::NONE);
CompressionType strumpack::SPOptions::compression() const;  // get compression type (none/hss/blr/hodlr)

When BLR compression is enabled, the default STRUMPACK behavior is to use the BLR enabled approximate LU factorization as a preconditioner within GMRES. This behavior can also be changed, see Solve.

However, BLR compression has a considerable overhead and only pays off for sufficiently large matrices. Therefore STRUMPACK has a tuning parameter to specify the minimum size a dense matrix needs to be to be considered a candidate for HSS compression. The minimum dense matrix size for BLR compression is set via the command line via

--sp_compression_min_sep_size int

or via the C++ API as follows

void strumpack::SPOptions::set_compression_min_sep_size(int s);
int strumpack::SPOptions::compression_min_sep_size() const;

The routine set_compression_min_sep_size(int s) refers to the size of the top-left block of the front only. This top-left block is the part that corresponds to a separator, as given by the nested dissection reordering algorithm. This top-left block is also referred to as the block containing the fully-summed variable. Factorization is only applied to this top-left block. Tuning the value for the minimum separator size can have a big impact on performance and memory usage!

The above options affect the use of BLR within the multifrontal solver. There are more, BLR specific, options which are stored in an object of type BLR::BLROptions<scalar>. An object of this type is stored in the SPOptions<scalar> object stored in the StrumpackSparseSolver. It can be accessed via the BLR_options() routine as follows:

strumpack::StrumpackSparseSolver<double> sp;         // create solver object
sp.options().set_compression(CompressionType::BLR);  // enable BLR compression in the multifrontal solver
sp.options().BLR_options().set_leaf_size(256);       // set the BLR leaf size

The compression tolerances can greatly impact performance. They can be set using:

> --blr_rel_tol real (default 0.01)
> --blr_abs_tol real (default 1e-08)

or via the C++ API

> void strumpack::BLR::BLROptions<scalar>::set_rel_tol(real rel_tol);
> void strumpack::BLR::BLROptions<scalar>::set_abs_tol(real abs_tol);
> real strumpack::BLR::BLROptions<scalar>::rel_tol() const;              // get the current value
> real strumpack::BLR::BLROptions<scalar>::abs_tol() const;

Here is a list of all command line options:

# BLR Options:
#   --blr_rel_tol real_t (default 0.0001)
#   --blr_abs_tol real_t (default 1e-10)
#   --blr_leaf_size int (default 128)
#   --blr_max_rank int (default 5000)
#   --blr_low_rank_algorithm (default RRQR)
#      should be [RRQR|ACA|BACA]
#   --blr_admissibility (default strong)
#      should be one of [weak|strong]
#   --blr_BACA_blocksize int (default 4)
#   --blr_verbose or -v (default false)
#   --blr_quiet or -q (default true)
#   --help or -h