# Towards a composable abstraction of hierarchical methods for matrix-vector product acceleration

Antoine Gicquel, Olivier Coulaud, Bérenger Bramas

► To cite this version:

Antoine Gicquel, Olivier Coulaud, Bérenger Bramas. Towards a composable abstraction of hierarchical methods for matrix-vector product acceleration. COMPAS 2025 - Conférence francophone d'informatique en Parallélisme, Architecture et Système, Jun 2025, Bordeaux, France. hal-05184758

HAL Id: hal-05184758

https://inria.hal.science/hal-05184758v1

Submitted on 24 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Towards a composable abstraction of hierarchical methods for matrix-vector product acceleration

Antoine Gicquel - Olivier Coulaud, Bérenger Bramas

CONCACE - Univ. Bordeaux, Inria, Univ. Strasbourg, ICube, France

<figure><img src="image_2.png" /></figure>

## Context

* We focus on accelerating the **matrix-vector product**

$$ y = Ax \quad (*) $$

where $A \in \mathbb{R}^{N \times N}$ is a **dense rank-structured** matrix (i.e., $A$ can be subdivided into tiles such that **off-diagonal tiles** have **low numerical ranks**).

* In this case, **hierarchical methods** reduce the complexity of $(*)$ from $O(N^2)$ to $O(N \log N)$ and even $O(N)$ with **controlled accuracy**.

* **Applications:**

* $N$-body problems (particle simulations, astrophysics,...)

* Discretization of non-local operators (BEM, VIM,...)

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

## Background (hierarchical methods)

* **State-of-the-art:**

* There exist **multiple** hierarchical methods:

* FMM (Fast Multipole Method)

* $H^*$ matrices (i.e., $H, H^2 + \text{variants like HSS, HODRL, BLR...}$)

* All of these methods rely on **similar core components**.

* Few attempts of **unification**.

* Each method redefines its own algorithm for the **hierarchical matrix-vector product**.

* **Classification of hierarchical methods** ($H^*$ matrices and FMM):

<figure><img src="image_6.png" /><figcaption>Analytical compression (FMM)</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Algebraic compression ($H^*$)</figcaption></figure>

This illustration was inspired by [C. Ashcraft, A. Buttari, and T. Mary, 2021] and [R. Yokota and L. A. Barba, 2011].

## Objectives and contributions of this work

* Unify all **hierarchical methods** under a **unique composable abstraction**.

* Design of a single **generic algorithm** for a **fast hierarchical matrix-vector product** (suitable for **efficient parallelization**).

## Composable abstraction of hierarchical methods

<figure><img src="image_8.png" /></figure>

* **Reordering and partitioning:**

* **Subdivide** matrix $A$ into tiles $\{A_{i,j}^{(\ell)}\}$ at different levels $\ell$.

* **Admissibility criterion:**

* Determines which tiles $A_{i,j}^{(\ell)}$ are approximated (or admissible).

* **Approximation strategy:**

* Approximates the admissible tiles $A_{i,j}^{(\ell)} \approx \hat{V}_i^{(\ell)} \hat{A}_{i,j}^{(\ell)} \hat{W}_j^{(\ell)}$.

* **Basis mutualization:**

* Factorizes the approximation bases $\hat{V}_i^{(\ell)}$ and $\hat{W}_j^{(\ell)}$.

## Generic algorithm for the hierarchical matrix-vector product

<figure><img src="image_9.png" /></figure>

## Experiments and early results

* Working implementation of a **sequential** prototype.

* **Numerical validations** within the `composyx` library:

* ✓ Validation for the FMM (via the `ScalFMM` library).

* ✓ Validation for the $H$-matrices.

* **Reproducible experiments** with `guix`.

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /></figure>

## Parallelization

* Extend **composability** to the parallelization of the algorithm:

* Use abstractions of recurring **parallelization patterns** (skeletons).

* Efficient **task-based** parallelization (using recent work on the parallelization of **tiled matrix multiplication**).

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>