Welcome to HODLRlib’s Documentation!

About \(\texttt{HODLRlib}\):

\(\texttt{HODLRlib}\) is a library consisting of fast matrix operations for matrices based on the Hierarchical Off-Diagonal Low-Rank (HODLR) structure. In the current version, the operations available are the matrix multiplication, solve, determinant computation and symmetric factorization.

This software is an optimized implementation and the extension of these articles [1] [2], with the current version showing a substantial increase in speed (a few orders of magnitude) over the timings reported in these articles. The solver has also been extended to matrices not necessarily arising out of kernels and higher dimensions. Low-rank approximation of the appropriate blocks is obtained using rook pivoting. The domain is subdivided based on a KDTree. The solver is fairly general, works with minimal restrictions and has been parallelized using OpenMP

The code is written in C++ and features an easy-to-use interface, where the user provides input through a kernel object which abstracts data of the matrix through a member function getMatrixEntry(int i, int j) which returns the entry at the \(i^{\mathrm{th}}\) row and \(j^{\mathrm{th}}\) column of the matrix.

The current release has the following capabilities:

  • MatVecs: Obtains \(A x\) at a cost of \(\mathcal{O}\left(N\log{N}\right)\)
  • Factorization: Factors the matrix \(A\) into the desired form at a cost of \(\mathcal{O}\left(N\log^2\left(N\right)\right)\)
  • Cholesky-like Symmetric Factorization: Obtains \(A = W W^T\) at a cost of \(\mathcal{O}\left(N\log^2\left(N\right)\right)\)
  • Solve: Solves linear systems \(A x = b\) at an additional cost of \(\mathcal{O}\left(N\log\left(N\right)\right)\)
  • Determinant Computation: Additional Cost of \(\mathcal{O}\left(N\log{N} \right)\)