sTiles: An Accelerated Computational Framework for Sparse Factorizations of Structured Matrices

Esmail Abdul Fattah, Hatem Ltaief, Håvard Rue, David E. Keyes

Abstract

The sTiles framework introduces a novel approach to the Cholesky factorization of structured sparse matrices, specifically "block arrowhead" matrices common in Bayesian inference. By integrating dense tile-based algorithms with a tree-reduction scheduling strategy, sTiles achieves significant performance improvements over traditional sparse and dense solvers, with speedups reaching up to 11x against industry-standard libraries.

Introduction

In scientific computing, particularly within spatial and spatiotemporal statistical modeling (such as the INLA framework), researchers frequently encounter block arrowhead matrices. These matrices feature dense clusters of non-zero elements along the diagonal and the final rows and columns, while remaining largely sparse elsewhere.

Arrowhead matrix structure typical in spatial statistics.

Existing linear algebra libraries often struggle with this specific geometry. Sparse solvers fail to exploit the local density of the blocks, resulting in poor hardware utilization. Conversely, dense solvers waste computational cycles and memory on zero elements. Furthermore, the arrowhead structure typically results in a thin dependency graph, creating a sequential bottleneck that limits the effectiveness of multi-core CPU scaling.

The sTiles Methodology

sTiles addresses these challenges by treating structured sparse matrices as a collection of dense tiles. This hybrid approach allows for high arithmetic intensity while maintaining the memory efficiency of sparse representations.

Algorithmic Innovations

  • Compressed Tile Storage: The matrix is partitioned into fixed-size dense blocks ("tiles"). Empty tiles are bypassed, while dense tiles are processed using optimized kernels.
  • Structure-Aware Permutation: The framework utilizes an adaptable Nested Dissection (ND) method to reorder matrices. This preserves the essential arrowhead shape while exposing independent sub-blocks for parallel execution.
  • Tree Reduction for Parallelism: To overcome the sequential constraints of the arrowhead dependency graph, sTiles implements a tree-reduction technique for matrix updates. By restructuring updates into a binary tree, the framework enables multiple processing units to aggregate results concurrently.
Dependency graphs showing the task parallelism and tile-based decomposition.

GPU Acceleration

The heavy computational load of dense tile operations is offloaded to NVIDIA GPUs. sTiles utilizes cuBLAS and cuSOLVER kernels, managed by a static scheduler to maximize throughput on architectures like the NVIDIA A100.

Performance Evaluation

The authors evaluated sTiles using 20 synthetic matrices (ranging from 10k to 1M rows) designed to replicate the computational demands of the INLA framework.

Comparative Results

On CPU platforms, sTiles significantly outperformed established libraries, achieving speedups of:

  • 8.41x over CHOLMOD
  • 9.34x over SymPACK
  • 5.07x over MUMPS
  • 11.08x over PARDISO

The tree-reduction technique alone provided a 20x speedup for update accumulations. When accelerated by an NVIDIA A100 GPU, sTiles delivered a 5x speedup over a 32-core AMD EPYC CPU for 50k-sized matrices and a 2.7x speedup for 1M-sized matrices.

Conclusion

sTiles demonstrates that a "structure-aware" hybrid approach is essential for efficiently factorizing large-scale structured sparse matrices. By combining tile-based processing with hierarchical task scheduling, the framework effectively breaks the parallelization barriers inherent in arrowhead matrices. Future developments will focus on out-of-core memory management and multi-GPU support to further scale these capabilities.

Summary updated

BibTeX
@inproceedings{fattah2025stiles,
  author = {Esmail Abdul Fattah and Hatem Ltaief and Håvard Rue and David E. Keyes},
  title = {{sTiles: An Accelerated Computational Framework for Sparse Factorizations of Structured Matrices}},
  booktitle = {ISC},
  year = {2025},
}
Figure