Source-linked AI summary
Comparison of Algebraic Block Multi-Coloring and Leiden Methods for Parallel Preconditioning in the ICCG Method
Tomohiro Suzuki
TL;DR
ICCG preconditioning is bottlenecked by sequential forward and backward substitutions, while ABMC requires problem-dependent block tuning. The paper evaluates Leiden-based graph blocking with modularity and CPM for parallel ICCG preconditioning, and finds CPM-based Leiden comparable to finely tuned ABMC. The approach reduces explicit block-parameter selection but remains dependent on a resolution parameter and can produce non-uniform blocks.
Problem
Sequential dependencies limit parallel ICCG preconditioning, while ABMC requires problem-dependent block-size or block-count tuning.
Method
The study partitions sparse-matrix adjacency graphs with Leiden using modularity and CPM, then applies the resulting blocks to parallel ICCG preconditioning and compares them with ABMC.
Results
CPM-based Leiden delivers ICCG execution performance comparable to finely tuned ABMC while suppressing giant blocks with a single resolution parameter.
Takeaways & Limitations
LeidenCP offers automated blocking that avoids explicitly prescribing the number of blocks while retaining competitive ICCG performance.
Takeaways & Limitations
Leiden is not entirely parameter-free, and modularity can produce uneven or giant blocks that degrade load balancing and execution time for certain matrices.
Abstract
from arXiv · showhide
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.
1 Introduction
ICCG preconditioning is difficult to parallelize because forward and backward substitutions have sequential dependencies and can suffer from poor cache locality. This study evaluates Leiden-based automated blocking against ABMC, finding CPM-based Leiden performance comparable to tuned ABMC.
- Motivation: Forward and backward substitutions create a major multicore parallelization bottleneck through recursive dependencies.These substitutions account for a significant portion of execution time in each ICCG iteration.
- Motivation: Multi-coloring enables parallel processing of independent vertex sets but can degrade spatial locality through discontinuous memory access and frequent cache misses.The constraint preventing adjacent nodes from being processed simultaneously may limit performance gains on some matrices.
- Existing approach: ABMC improves locality by grouping unknowns into blocks and coloring the blocks, but requires the number of blocks or block size to be specified beforehand.Its configuration must be selected through problem-dependent empirical tuning.
- Proposed approach: Leiden determines block structures by optimizing graph-partitioning quality functions without explicitly prescribing the number of blocks a priori.The study applies block multi-coloring to Leiden partitions and evaluates convergence, execution time, and cache efficiency.
- Results: Across 32-core evaluations, Leiden with the CPM delivers ICCG performance comparable to finely tuned ABMC while suppressing giant blocks using a single resolution parameter.The framework evaluates modularity and CPM for their effects on block structures, cache efficiency, and solver performance.
2 Overview of ABMC Method
ABMC combines block-level coloring with sequential processing within blocks to balance parallelism and data locality. Its performance depends strongly on a problem-specific block-size choice.
- Block construction: ABMC constructs graph-based blocks by grouping strongly connected nodes until each block reaches a prescribed size.The blocks are formed from the nonzero pattern of the coefficient matrix.
- Block coloring: Block-level coloring assigns distinct colors to mutually dependent blocks, enabling parallel forward and backward substitutions across independent blocks.Unknowns within each block remain sequentially processed.
- Performance rationale: Sequential processing within blocks preserves data locality and can enhance cache efficiency and preconditioner quality.Preconditioner quality refers to how closely the IC(0)-based preconditioning matrix approximates the original coefficient matrix.
- Parameter trade-off: ABMC performance requires problem-dependent tuning because larger blocks typically improve cache efficiency and convergence, whereas smaller blocks increase parallelism.The optimal configuration depends heavily on the specific sparse linear system.
3 Overview of Leiden Method
Leiden refines community partitions to ensure internal connectivity and can use modularity or CPM to generate blocks from sparse-matrix graphs. The study evaluates these partitions for ICCG parallel preconditioning.
- Leiden algorithm: Leiden adds a refinement phase that subpartitions communities to guarantee high internal connectivity before graph aggregation.This procedure is repeated within a multilevel optimization framework.
- Quality functions: Modularity compares within-community edges with expectations from a degree-preserving random null model.Its resolution parameter is γMD.
- Quality functions: CPM evaluates within-community edge density against a constant threshold and penalizes possible vertex pairs in each community.This penalty suppresses giant communities, while γCP controls the edge-density boundary.
- Application and evaluation: The resulting Leiden partitions are used for ICCG block multi-coloring and evaluated by block counts, block-size distributions, color counts, iterations, and execution time.The comparison examines how the two quality functions affect parallel preconditioning outcomes.
4 Test Matrices and Experimental Environment
The evaluation uses eight real symmetric positive definite SuiteSparse matrices from diverse application domains on a 32-core AMD EPYC system. ICCG experiments use IC(0), OpenMP, and repeated-run averages under a specified residual criterion.
- Test matrices: Eight real symmetric positive definite matrices from SuiteSparse represent CFD, structural, thermal, circuit, and grid-based applications.The matrices cover diverse problem domains and characteristics.
- Hardware and software: The computational system uses an AMD EPYC 7543 processor with 32 cores, per-core L1 and L2 caches, and a shared 256 MB L3 cache.The machine has 128 GB of DDR4 RAM.
- Hardware and software: The ICCG implementation is written in C++ with Intel oneMKL 2025.2 and OpenMP parallelization of parallelizable loops.OpenMP is used to parallelize solver loops.
- Experimental protocol: Convergence requires ∥r∥2/∥b∥2 ≤ 1.0 × 10^-8 with b set to an all-ones vector.Execution time and iteration counts are averaged over 10 independent runs.
5 Performance Evaluation Using the ABMC Method
ABMC performance depends strongly on matrix-specific block-count tuning, with execution time shaped by the interaction between ICCG iterations and L2 cache efficiency. Across the tested matrices, favorable locality did not always yield short runtimes.
- Evaluation setup: ABMC evaluation used optimized block counts and measured average execution time, ICCG iterations, and L2 cache efficiency across the test matrices.The execution results were plotted for optimized nb configurations, while L2 cache metrics were collected with Linux perf.
- Block-count sensitivity: The optimal number of blocks nb varies significantly by matrix, confirming that ABMC configuration is highly problem-dependent.The appropriate setting depends on nonzero structure and local connectivity patterns, not only matrix size or ANZR.
- Performance factors: Execution time reflects a complex interplay between ICCG iteration count and cache efficiency rather than either factor alone.High L2 hit rates can improve locality, while large iteration counts or poor locality can still dominate runtime.
- Cache efficiency: High L2 hit rates of 0.84 or higher occur for several low- to moderate-ANZR matrices, indicating improved memory access locality from block partitioning.The cited matrices include parabolic fem, apache2, ecology2, thermal2, and G3 circuit.
- Cache efficiency: Hook 1498 has the lowest L2 hit rate, 0.69, making insufficient intra-block data locality its primary ABMC bottleneck.Its high execution time is associated with a high-ANZR workload and poor cache locality.
- Cache efficiency: Apache2 and ecology2 use five block colors and attain L2 hit rates of 0.85 and 0.86, respectively, but ecology2 needs substantially more ICCG iterations.These results show that favorable cache behavior alone does not guarantee short execution time when convergence is poor.
- Practical limitation: ABMC requires careful per-matrix optimization of nb to exploit its capabilities, creating a practical deployment challenge.The study identifies this strict parameter-selection requirement as motivation for automated blocking.
6 Performance Evaluation Using Leiden Method
The evaluation compares Leiden-based blocking with optimized ABMC for ICCG preconditioning, examining partition structure, execution performance, load balance, and cache efficiency. LeidenCP generally mitigates oversized-block overhead more effectively than LeidenMD, while quality-function choice creates matrix-dependent trade-offs.
- Evaluation setup: LeidenMD and LeidenCP denote Leiden blocking based on modularity and CPM maximization, respectively, and are compared with optimized ABMC results.The evaluation also summarizes Leiden-generated block counts and block colors for each matrix.
- Execution performance: LeidenMD matched or slightly beat ABMC on four matrices but was slower on four others, with thermal2 showing major slowdown despite nearly identical iteration counts.The thermal2 degradation is associated with oversized-block sequential overhead, block-size imbalance, or parallel load imbalance rather than convergence behavior.
- Execution performance: LeidenCP reduced execution time versus LeidenMD for most matrices, although LeidenMD was faster than LeidenCP for G3 circuit.Thus, finer CPM partitioning is beneficial in several cases but not universally advantageous.
- Block structure: LeidenMD generated fewer blocks and approximately 5 to 7 colors, whereas LeidenCP produced finer partitions with approximately 6 to 10 colors.CPM increased parallel execution units without a proportional increase in coloring-related synchronization overhead.
- Load balance: For thermal2, LeidenCP reduced the Gini coefficient from 0.89 to 0.25 and Bmax/Bavg from 13.7 to 2.13, while maintaining Bmax/Bavg around 2 or lower elsewhere.The CPM function suppresses excessively large communities and reduces sequential processing overhead within blocks.
- Cache efficiency: LeidenMD achieved L2 hit rates of at least 0.87 on four matrices and improved Hook 1498 from 0.69 with ABMC to 0.78.LeidenCP had lower cache efficiency than LeidenMD across all matrices, yet execution depends on cache efficiency together with block size, colors, load balance, and iterations.
7 Sensitivity Analysis of Resolution Parameters
Resolution parameters control Leiden partition granularity and influence block balance, iteration counts, and execution time. CPM-based Leiden produces balanced structures across a practical parameter range, while modularity-based tuning is more matrix-sensitive.
- LeidenMD resolution sensitivity: γMD controls LeidenMD partition granularity: larger values generally produce smaller communities and more blocks.
- LeidenMD resolution sensitivity: Higher γMD values subdivide oversized blocks in thermal2, Hook 1498, and Geo 1438, reducing execution-time bottlenecks for these matrices.
- LeidenMD resolution sensitivity: Finer LeidenMD partitions do not consistently improve performance because execution time depends on iterations, block size, intra-block sequential work, and load balance.
- LeidenMD resolution sensitivity: Modularity-based tuning can optimize selected matrices but frequently remains less competitive than LeidenCP because modularity does not directly tailor block sizes for parallel preconditioning.
- LeidenCP resolution sensitivity: As γCP increases, LeidenCP generally creates more blocks while keeping block colors within about 6–10 for most matrices.
- LeidenCP resolution sensitivity: Thermal2's block-size Gini coefficient decreases from 0.32 to 0.20 as γCP rises from 5.0 × 10−4 to 2.0 × 10−3, while most other matrices remain below approximately 0.17.
- LeidenCP resolution sensitivity: The baseline γCP = 1.0 × 10−3 lies within a practical range yielding balanced blocks and competitive ICCG performance, despite non-monotonic parameter effects.
8 Conclusion and Future Work
The study concludes that Leiden-based blocking reduces advance block-configuration requirements, with LeidenCP delivering competitive ICCG performance and limiting oversized blocks. Its practical benefit depends on amortizing blocking cost, and future work targets broader quality functions and faster preprocessing.
- Conclusion: The Leiden framework automatically generates ICCG preconditioning blocks and is evaluated against conventional ABMC.
- Conclusion: LeidenCP suppresses giant blocks and achieves execution performance comparable to finely tuned ABMC using one resolution parameter.
- Conclusion: Increasing γMD can reduce execution time for specific matrices, especially those with severe block-size imbalance or high ANZR values.
- Conclusion: LeidenCP avoids explicitly prescribing the block count and reduces problem-dependent parameter selection, although it is not entirely parameter-free.
- Practical scope: For isolated solves, LeidenCP's higher blocking cost may offset reduced ICCG time; reuse across right-hand sides or time steps improves its suitability.
- Future work: Future work will examine alternative quality functions, parallel quality-function maximization, and structural reordering such as Rabbit Ordering.