Comparison of Algebraic Block Multi-Coloring and Leiden Methods for Parallel Preconditioning in the ICCG Method
Abstract
In the application of incomplete Cholesky preconditioning to the incomplete Cholesky-conjugate gradient (ICCG) method, forward and backward substitutions exhibit sequential dependencies that constitute a major bottleneck for parallelization in multicore environments. To alleviate this bottleneck, the algebraic block multi-coloring (ABMC) method achieves both parallelism and data locality through block-wise coloring. However, ABMC requires the number of blocks to be specified as an input parameter in advance. This study evaluates the Leiden method as an alternative blocking approach for parallel preconditioning in the ICCG method. As a community detection technique that maximizes a quality function for graph partitioning, the Leiden method automatically generates blocks that reflect the matrix structure without requiring the number of blocks a priori. We partition the adjacency graphs of sparse matrices using the Leiden method and utilize the resulting blocks for parallel preconditioning. We implement the Leiden method using modularity and the constant Potts model as quality functions and compare its performance with that of the ABMC method in terms of the number of iterations, execution time, and L2 cache efficiency across eight symmetric positive definite matrices. The experimental results demonstrate that the Leiden method with the constant Potts model achieves performance comparable to that of the ABMC method configured with an optimized number of blocks.
Related
- A comparison of parallel iterative methods for ILU triangular solves
- A unified variational framework for augmented Lagrangian preconditioning of saddle point systems: applications to mixed-dimensional and fictitious domain methods
- A Parallel Algebraic Multigrid Preconditioned Iterative Method Based on an MPI Process Grouping Strategy for Asynchronous Concurrent Execution of the Setup and Solve Phases
- Tolerance Proportionality and Computational Stability in Adaptive Parallel-in-Time Runge-Kutta Methods
- An algebraic comparison of K̂-stability and Kβ-stability
BibTeX
@misc{suzuki2026comparison,
title = {{Comparison of Algebraic Block Multi-Coloring and Leiden Methods for Parallel Preconditioning in the ICCG Method}},
author = {Tomohiro Suzuki},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.00561},
eprint = {2609.00561},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.00561},
}
RIS
TY - UNPB
TI - Comparison of Algebraic Block Multi-Coloring and Leiden Methods for Parallel Preconditioning in the ICCG Method
AU - Tomohiro Suzuki
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.00561
UR - https://arxiv.org/abs/2609.00561
AB - In the application of incomplete Cholesky preconditioning to the incomplete Cholesky-conjugate gradient (ICCG) method, forward and backward substitutions exhibit sequential dependencies that constitute a major bottleneck for parallelization in multicore environments. To alleviate this bottleneck, the algebraic block multi-coloring (ABMC) method achieves both parallelism and data locality through block-wise coloring. However, ABMC requires the number of blocks to be specified as an input parameter in advance. This study evaluates the Leiden method as an alternative blocking approach for parallel preconditioning in the ICCG method. As a community detection technique that maximizes a quality function for graph partitioning, the Leiden method automatically generates blocks that reflect the matrix structure without requiring the number of blocks a priori. We partition the adjacency graphs of sparse matrices using the Leiden method and utilize the resulting blocks for parallel preconditioning. We implement the Leiden method using modularity and the constant Potts model as quality functions and compare its performance with that of the ABMC method in terms of the number of iterations, execution time, and L2 cache efficiency across eight symmetric positive definite matrices. The experimental results demonstrate that the Leiden method with the constant Potts model achieves performance comparable to that of the ABMC method configured with an optimized number of blocks.
ER -