HODLR & HODBF Preconditioning

HODLR, or Hierarchically Off-Diagonal Low Rank, is a rank-structured format that is similar to HSS, but simpler. It uses the same weak admissibility, i.e, all off-diagonal blocks are low rank, but it does not use nested bases. Compared to HSS, HODLR theoretically has worse asymptotic complexity, but the algorithms might be faster in practice for medium sized problems.

HODBF stands for Hierarchically Off-Diagonal Butterfly. HODBF is like HODLR except that it uses Butterfly decomposition instead of low rank. The HODBF format was specifically developed for dealing high frequency problems.

For a description of the HODBF format and its use in the sparse multifrontal solver see: https://arxiv.org/abs/2007.00202

STRUMPACK's HODLR code uses an external library, which can be found here: https://github.com/liuyangzhuan/ButterflyPACK

See the Installation and Requirements instructions for how to configure and compile STRUMPACK with support for HODLR.

HODLR compression in the sparse solver can be turned on/off via the command line:

--sp_compression hodlr
--sp_compression none    (disable compression)

or via the C++ API as follows

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

In order to enable HODBF compression one should set the compression type to HODLR, and additionally set

--hodlr_butterfly_levels l

where l is the number of levels in the HODLR hierarchy for which butterfly compression is to be used (instead of low-rank). A value of 1 means only the largest off-diagonal blocks are compressed using butterfly. To enable butterfly compression on all levels, simply use a large enough value, for instance 100.

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

However, HODLR 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 compression. The minimum dense matrix size for 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 above options affect the use of HODLR within the multifrontal solver. There are more, HODLR specific, options which are stored in an object of type HODLR::HODLROptions<scalar>. An object of this type is stored in the SPOptions<scalar> object stored in the StrumpackSparseSolver. It can be accessed via the HODLR_options() routine as follows:

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

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

--hodlr_rel_tol real (default 0.01)
--hodlr_abs_tol real (default 1e-08)

or via the C++ API

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

---

Other options are available. See the documentation of HODLROptions<scalar> for more detailed information.