Comparison of Algebraic Block Multi-Coloring and Leiden Methods for Parallel Preconditioning in the ICCG Method

Comparison of Algebraic Block Multi-Coloring and Leiden Methods for Parallel Preconditioning in the ICCG Method

arXiv:2609.00561v1 [cs.DC] 1 Sep 2026

Tomohiro Suzuki Department of Interdisciplinary Research, Division of Engineering University of Yamanashi Takeda 4-3-11, Kofu, Yamanashi 400-8511 Japan stomo@yamanashi.ac.jp lar, the incomplete Cholesky-conjugate gradient (ICCG) method is widely used in large-scale finite element analysis and fluid simulations. In the computational process of the ICCG method, forward and backward substitutions are utilized to apply the preconditioner based on incomplete Cholesky factorization. These substitutions account for a significant portion of the execution time in each iteration. However, they possess an inherent sequentiality, where each element depends recursively on previously computed values. Such sequential dependencies present a major bottleneck for parallelization in multicore environments. Techniques that eliminate these sequential dependencies and rearrange matrix elements for parallel execution are referred to as parallel preconditioning. A representative approach is the multi-coloring method. In this method, an adjacency graph is constructed from the nonzero structure of a sparse matrix and colored such that adjacent vertices have distinct colors. The matrix is then reordered to place vertices of the same color contiguously, enabling parallel processing of independent vertex sets. However, the multi-coloring method imposes a constraint that prevents adjacent nodes from being processed simultaneously. Because these adjacent nodes are originally located close to each other in memory, this constraint leads to discontinuous memory access, thereby degrading spatial locality. Consequently, despite the improved degree of thread-level parallelism, frequent cache misses can occur. On modern CPU architectures that feature hierarchical caches, this approach may fail to deliver sufficient performance gains for certain matrices. To mitigate this issue, block multi-coloring methods have been proposed, with a typical example being the algebraic block multi-coloring (ABMC) method [1]. The ABMC method groups n unknowns into approximately nb blocks with a target block size s = ⌈n/nb ⌉ and subsequently performs coloring at the block level. This approach preserves parallelism while improving memory access locality by processing unknowns sequentially within each block. In this manner, the ABMC method aims to simultaneously achieve high parallelism and enhanced cache efficiency. In recent years, the analysis of large-scale networks has gained significant attention in computer science [2– 5]. These networks inherently exhibit community struc-

This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.

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 multicoloring (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. Keywords: algebraic block multi-coloring (ABMC) method, incomplete Cholesky-conjugate gradient (ICCG) method, Leiden method, parallel preconditioning

1

Introduction

Iterative solvers for sparse linear systems are fundamental tools in numerical linear algebra. In particu0 This work was supported by the Japan Society for the Promotion of Science KAKENHI under grant number 25K15136.

1

2

tures, where vertices within the same group are densely connected. Community detection has emerged as a key technique for identifying such natural divisions within a network. Among various approaches, the Louvain method [6] aims to extract substructures that maximize modularity [7], a metric that quantifies the density of internal edges relative to external connections. The Leiden method [8] enhances the Louvain method by guaranteeing connectivity within communities, thereby yielding higher-quality partitions. Furthermore, the Leiden method accommodates alternative quality functions beyond modularity; for instance, the constant Potts model (CPM) [9] evaluates community quality based on the exact number of internal edges and vertices. This concept of identifying densely connected groups provides a powerful guideline for restoring data locality in sparse matrix computations. Specifically, by extracting communities from an adjacency graph and treating them as blocks, strong data dependencies can be confined within individual blocks, leaving inter-block connections relatively sparse. The conventional ABMC method performs blocking based on a pre-specified number of blocks or block size. Selecting the optimal configuration requires empirical trial and error, which is a practical drawback. In contrast, the Louvain and Leiden methods determine the block structure organically through the optimization of a quality function, without explicitly prescribing the number of blocks a priori. However, unlike ABMC, qualityfunction-based methods do not explicitly control individual block sizes. This absence of explicit control can lead to non-uniform block sizes, potentially causing performance degradation due to load imbalance. To address this trade-off, this study applies block multi-coloring to the block structures obtained via both the ABMC and Leiden methods for parallel preconditioning. We then comprehensively evaluate the impacts of these methods on the convergence behavior of the ICCG method, parallel execution time, and cache efficiency. The main contributions of this study are summarized as follows:

Overview of ABMC Method

The ABMC method [1] extends the block multi-coloring method, originally developed for structured grids, to general sparse matrices. First, an undirected graph is constructed from the nonzero pattern of the coefficient matrix. Nodes with strong connectivity are subsequently grouped into the same block. In this blocking process, a seed node is selected from the unassigned nodes, and its neighboring nodes are added to a candidate set until the block reaches a prescribed size. Next, coloring is performed at the block level, where blocks with mutual dependencies are assigned distinct colors. Consequently, blocks of the same color become independent, enabling parallel forward and backward substitutions to be executed on a block-by-block basis for each color. Conversely, the unknowns inside each block are processed sequentially, thereby preserving data locality. This combination enhances both cache efficiency and the quality of the preconditioner. Here, the quality of the preconditioner refers to how closely the preconditioning matrix constructed via the incomplete Cholesky factorization with zero fill-in, or IC(0), approximates the original coefficient matrix. The ABMC method requires the block size as an input parameter, which significantly influences the performance of the ICCG method. A larger block size typically improves cache efficiency and convergence behavior, whereas a smaller block size increases the degree of parallelism. Because the optimal configuration depends heavily on the specific problem, determining it requires problem-dependent tuning.

3

Overview of Leiden Method

The Leiden method [8] was developed as an advanced community detection technique to address the architectural limitations of the Louvain method. In the Louvain method, the resulting communities can be weakly connected internally or even disconnected. The Leiden method overcomes this structural drawback by introducing a refinement phase. Specifically, after the quality function is optimized through the local movement of vertices, the Leiden method applies a refinement phase to the resulting partition. During this phase, communities are subpartitioned to guarantee high internal connectivity before the aggregated (contracted) graph is constructed. This multi-stage procedure is then repeated iteratively. Consequently, the Leiden method inherits the fast multilevel optimization framework of the Louvain method while successfully ensuring connectivity within the extracted communities. Various quality functions, such as modularity and the CPM [9], can be employed within the Leiden method. Modularity [7] quantifies the difference between the actual number of edges within communities and the expected number of such edges in a random null model that preserves the degree distribution. It is formally de-

• We propose a Leiden-based automated blocking framework for ICCG preconditioning, which reduces the need for problem-dependent parameter tuning. • We evaluate modularity and the CPM as quality functions, analyzing their impacts on block structures, cache efficiency, and solver performance across 32-core execution. • Through performance evaluations in a 32-core CPU environment, we demonstrate that the Leiden method with the CPM suppresses the formation of giant blocks and delivers ICCG execution performance comparable to that of the finely tuned ABMC method using only a single resolution parameter. 2

fined as Q=

X

1 2m i,j

Aij − γMD

ki kj 2m

DDR4 RAM, configured as eight 16-GB modules. The operating system was Ubuntu 22.04 LTS. The ICCG method was implemented in C++, with Intel oneMKL 2025.2 utilized as the BLAS library. Parallelizable loops within the solver were parallelized using OpenMP. For the linear system Ax = b, the right-hand-side vector b was configured as a vector of all ones. The convergence criterion was defined by the relative residual norm satisfying ∥r∥2 /∥b∥2 ≤ 1.0 × 10−8 , where r denotes the residual vector. Both the execution time and the number of iterations were evaluated as averages over 10 independent runs.

 δ(ci , cj ),

(1)

Average execution time [s]

where Aij is the (i, j)th element of the adjacency matrix, ki is the degree of vertex i, m is the total number of edges, γMD is the resolution parameter, and ci denotes the community to which vertex i belongs. The function δ(ci , cj ) equals 1 if vertices i and j belong to the same community and 0 otherwise. Maximizing this metric yields a partition where edges are densely concentrated within communities and relatively sparse between them. In contrast, the CPM does not rely on a null model derived from a random graph. Instead, it evaluates Performance Evaluation Using the edge density within communities against a constant 5 threshold scaling factor γCP . The CPM quality function the ABMC Method to be maximized is formulated as Fig. 1 shows the execution results of the ICCG method X
H= ei − γCP n2i , (2) with the ABMC method used for parallel preconditioni ing. In the evaluation of the ABMC method, block partitioning was performed according to the procedure where ei denotes the number of edges within community described in Section 2, followed by block-level coloring i and ni denotes the number of vertices in community utilizing the greedy coloring algorithm [11]. The figure i. Thus, the CPM can be interpreted as a metric that presents scatter plots illustrating the relationship berewards intra-community edges while penalizing the totween the average execution time and the average numtal number of possible vertex pairs within each commuber of iterations of the ICCG method across the test nity. This penalty effectively suppresses the formation matrices. of giant communities. Consequently, the parameter γCP serves as a critical threshold that dictates the boundary for edge densities both inside and outside communities. Hook_1498 In this study, we apply the block (community) partiEmilia_923 20.0 tions obtained via these two distinct quality functions to parallel preconditioning for the ICCG method. We then comprehensively evaluate the impacts of these quality 15.0 functions on the resulting number of blocks, block-size distribution, number of block colors, number of ICCG 10.0 thermal2 iterations, and parallel execution time. Geo_1438 G3_circuit

ecology2

5.0

4

Test Matrices and Experimental Environment

apache2

parabolic_fem

0.0 500

1000

1500

2000

Average no. of iterations

This section describes the test matrices and the computational setup used in our evaluation. We selected eight real, symmetric positive definite matrices from the SuiteSparse Matrix Collection [10]. These matrices satisfy the basic requirements for applying the CG method and are appropriate test problems for ICCG with IC(0) preconditioning. As summarized in Table 1, these matrices originate from diverse application domains, including computational fluid dynamics (CFD), structural analysis, thermal analysis, circuit simulation, and grid-based problems, and cover a wide range of average nonzeros per row (ANZR = nz /n). The hardware and software specifications of the computational environment utilized in our experiments are as follows. The system featured an AMD EPYC 7543 processor with 32 cores, 64 KB of L1 cache per core, 512 KB of L2 cache per core, and a shared 256 MB of L3 cache. The main memory consisted of 128 GB of

Figure 1: Scatter plot of average execution time versus average number of iterations for ABMC-based ICCG The ABMC method employs the number of blocks nb , or equivalently the block size s = ⌈n/nb ⌉, as a critical runtime parameter that significantly influences the performance of the ICCG method. To investigate this dependency, we evaluated the execution time of the ICCG method for nb values of 32, 64, 128, 256, 512, and 1024. Table 2 summarizes the optimal value of nb that achieved the shortest ICCG execution time for each test matrix, along with the corresponding number of block colors nc . The execution results obtained using these optimized nb configurations are plotted in Fig. 1. To evaluate L2 cache efficiency during the execution of the ICCG method, we collected the following hardware 3

Table 1: Characteristics of sparse test matrices Matrix Size (n) Nonzeros (nz ) ANZR Problem type parabolic fem 525,825 3,674,625 6.99 CFD apache2 715,176 4,816,870 6.74 Structural Emilia 923 923,136 40,373,538 43.74 Structural 999,999 4,995,991 5.00 2D/3D ecology2 thermal2 1,228,045 8,580,313 6.99 Thermal 1,437,960 60,236,322 41.89 Structural Geo 1438 Hook 1498 1,498,023 59,374,451 39.64 Structural 1,585,478 7,660,826 4.83 Circuit simulation G3 circuit

Table 2: Best-performing nb values and corresponding nc values for ABMC-based ICCG for tested matrices Matrix nb nc parabolic fem 256 6 apache2 128 5 Emilia 923 64 8 128 5 ecology2 thermal2 1,024 6 128 8 Geo 1438 Hook 1498 512 11 G3 circuit 512 10

Table 3: L2 cache efficiency of ABMC-based ICCG Matrix Rhit Rmiss parabolic fem 0.85 0.075 apache2 0.85 0.060 Emilia 923 0.79 0.040 0.86 0.052 ecology2 thermal2 0.88 0.061 0.74 0.049 Geo 1438 Hook 1498 0.69 0.10 G3 circuit 0.84 0.077

the observation in [1] that the optimal configuration is highly problem-dependent. The performance profiles plotted in Fig. 1 and summarized in Table 3 reveal that the execution time is dictated by a complex interplay between the number of iterations and cache efficiency. For instance, low to moderate ANZR matrices such as parabolic fem, apache2, ecology2, thermal2, and G3 circuit achieve high L2 hit rates of 0.84 or higher, demonstrating that block partitioning successfully enhances memory access locality. Although thermal2 achieves a high L2 hit rate, its execution time increases because it requires an exceptionally large number of ICCG iterations. Conversely, structured matrices with high ANZR values, such as Emilia 923, Geo 1438, and Hook 1498, incur massive computational workloads per iteration. While Geo 1438 mitigates this workload through a remarkably small number of iterations (≈ 500), Emilia 923 and Hook 1498 exhibit increased execution times. Particularly for Hook 1498, the L2 hit rate (0.69, which is the lowest value among all matrices) acts as the primary bottleneck, indicating that the ABMC blocking fails to achieve sufficient intra-block data locality for this specific matrix structure. For grid-like or stencil-based matrices, the ABMC method also achieves favorable cache behavior. For example, apache2 and ecology2 both require only five block colors and achieve high L2 hit rates of 0.85 and 0.86, respectively. However, their convergence behavior differs: ecology2 requires a substantially larger number of ICCG iterations than those for apache2, which leads to a longer execution time despite its high L2 hit rate. These results indicate that favorable cache behavior alone does not guarantee short execution time when

performance events utilizing the Linux perf tool: • l2 cache accesses from dc misses (L2access ) • l2 cache hits from dc misses (L2hit ) • l2 cache misses from dc misses (L2miss ) Based on these metrics, the L2 hit rate and L2 miss rate were respectively defined as L2hit , L2access L2miss Rmiss = . L2access Rhit =

(3)

Following the evaluation methodology established in [1], this study focuses exclusively on L2 cache efficiency. Because the L3 cache on the target AMD EPYC processor is shared among multiple cores within a core complex (CCX), L3 metrics are heavily affected by inter-thread contention. In contrast, L2 metrics provide a more direct and reliable indicator of the core-level data locality achieved by the preconditioning algorithms. Table 3 summarizes the measured L2 cache efficiency profiles for the ABMC method. We now discuss the performance of the ICCG method with parallel preconditioning using the ABMC method across the eight test matrices. First, as demonstrated in Table 2, the optimal number of blocks nb varies significantly depending on the matrix. This variation indicates that the appropriate number of blocks in the ABMC method is determined not only by the matrix size or ANZR but also by the underlying nonzero structure and local connectivity patterns, strongly supporting 4

the convergence behavior is poor. Table 4: nb values determined by Leiden-based blocking In summary, these diverse performance profiles unand corresponding nc values for tested matrices derscore that the runtime parameter nb must be careLeidenMD LeidenCP fully optimized for each individual matrix to fully exMatrix nb nc nb nc ploit the capabilities of the ABMC method. This strict parabolic fem 101 5 2,277 6 requirement for problem-dependent parameter selection apache2 69 5 2,253 8 poses a critical practical challenge when deploying the Emilia 923 39 7 448 9 ABMC method in production environments, highlightecology2 144 6 6,366 6 ing the necessity of an automated blocking framework. thermal2 1,099 5 6,404 6

6

Geo 1438 Hook 1498 G3 circuit

Performance Evaluation Using Leiden Method

Next, we evaluate the performance of the ICCG method with the Leiden method used for block partitioning in parallel preconditioning. For the Leiden method, we utilized the igraph community leiden simple function implemented in igraph version 1.0.1 [12]. The two quality functions to be maximized are modularity and the CPM. The resolution parameter for modularity, γMD , was set to its default value of 1.0. The resolution parameter for the CPM, γCP , was configured as 1.0×10−3 , which demonstrated high performance in preliminary experiments. The generated blocks were colored utilizing the greedy coloring algorithm and then applied to the parallel preconditioning to evaluate the execution performance of the ICCG method. Unlike the ABMC method, the Leiden method inherently generates blocks of non-uniform sizes, meaning that the block ordering can also affect the overall performance. To optimize data reference locality, this study sorts the blocks in descending order of size, assigning smaller indices to larger blocks. This reordering places the unknowns of larger blocks with strong internal connections into contiguous index ranges, thereby concentrating the nonzero elements near the main diagonal and improving cache reuse during forward and backward substitutions.

ABMC

Hook_1498

LeidenCP

Average execution time [s]

30.0

thermal2

20.0

Geo_1438

10.0 G3_circuit

ecology2

apache2

0.0

parabolic_fem

500

1000

1500

5 6 5

721 779 9,777

8 10 7

Fig. 2 presents the execution performance of the ICCG method with the Leiden method used for parallel preconditioning. Here, LeidenMD and LeidenCP denote the Leiden method based on modularity maximization and CPM maximization, respectively; these terms are used hereafter to distinguish between the two variants. For comparison, the optimized results of the ABMC method from Fig. 1 are also plotted, with data points corresponding to the same matrix connected by lines. Table 4 summarizes the number of blocks generated by the Leiden method for each matrix, along with the corresponding number of block colors. As demonstrated in Fig. 2, the execution performance differs significantly between LeidenMD and LeidenCP. For LeidenMD, execution times comparable to or slightly shorter than those of the ABMC method were obtained for parabolic fem, apache2, ecology2, and G3 circuit. These matrices are characterized by relatively low to moderate ANZR values and grid-like or sparse graph structures, for which the coarse communities generated by modularity maximization do not necessarily cause severe sequential bottlenecks. In contrast, for Emilia 923, Geo 1438, Hook 1498, and thermal2, the execution times of LeidenMD were longer than those achieved by the ABMC method. In particular, for thermal2, the execution time increased significantly even though the average number of iterations remained almost identical to that of the ABMC method. This discrepancy indicates that under the LeidenMD partitioning, the severe performance degradation arises not from the convergence behavior itself, but rather from blocksize imbalance, an increase in sequential processing overhead within massive blocks, or parallel load imbalance. LeidenCP reduced the execution time for most matrices compared with LeidenMD. In particular, for Emilia 923, thermal2, Geo 1438, and Hook 1498, LeidenCP achieved distinctly shorter execution times than those of LeidenMD. As detailed in Table 4, this performance gain is driven by the fact that the CPM function produces finer block partitions than those obtained with modularity maximization. Consequently, the sequential processing overhead caused by oversized blocks is effectively mitigated. However, for G3 circuit, LeidenMD exhibits a shorter execution time than that of LeidenCP, demonstrating that finer partitioning via the CPM is not univer-

Emilia_923

LeidenMD

37 46 116

2000

Average no. of iterations

Figure 2: Scatter plot of average execution time versus average number of iterations for Leiden- and ABMCbased methods

5

sally advantageous. Therefore, when employing the Leiden method for parallel preconditioning in the ICCG method, the choice of the quality function has a critical impact on the execution performance. This impact is determined by the complex trade-offs among the number of blocks, the block-size distribution, the number of block colors, and data locality. Table 4 shows that LeidenMD generates fewer blocks than those for the optimal configurations of the ABMC method, except for ecology2 and thermal2. For example, Emilia 923, Geo 1438, and Hook 1498 are partitioned into only 39, 37, and 46 blocks, respectively, which are significantly smaller than the best nb values for the ABMC method. Additionally, the number of block colors remains restricted to approximately 5 to 7. From the standpoint of synchronization costs alone, this small number of block colors should be advantageous. However, as detailed later in Table 5, a smaller number of blocks naturally leads to larger individual blocks, thereby increasing the sequential processing within each block. Consequently, a reduced number of block colors does not automatically guarantee a shorter execution time. In contrast, LeidenCP generates significantly more blocks than those for LeidenMD across the test matrices, resulting in much finer partitions. Nevertheless, the number of block colors remains relatively small, approximately 6 to 10 in most cases. This result indicates that CPM-based partitioning increases the number of parallel execution units without causing a proportional increase in the synchronization overhead associated with block coloring. A key advantage of deploying the Leiden method as a blocking mechanism for parallel preconditioning is that it avoids explicitly prescribing the number of blocks or block sizes. However, the method is not entirely parameter-free, because the resolution parameter of the quality function, such as γMD or γCP , still influences the resulting block structure. Moreover, the resulting block sizes are inherently non-uniform, which can lead to load imbalance during parallel execution. To quantify this structural non-uniformity, this study introduces the Gini coefficient [13] as an evaluation index for block-size imbalance. Given the block sizes denoted by s1 , s2 , . . . , snb , the Gini coefficient G is defined as follows: Pnb Pnb |si − sj | i=1  j=1P . G= (4) nb si 2(nb )2 n1b i=1

acterize block-level imbalance and color-level workload imbalance, respectively. For the ABMC method, Bmax /Bavg is 1.00 for all matrices because the ABMC method explicitly controls the number of blocks and generates nearly uniform block sizes. However, the color-wise workload is not perfectly uniform, as indicated by Cmax /Cavg values larger than 1.00. This result shows that even when block sizes are uniform, the workload assigned to each color can still be imbalanced. For LeidenMD, the degree of block-size imbalance depends strongly on the matrix. The most severe case is thermal2, for which the Gini coefficient is 0.89 and Bmax /Bavg reaches 13.7. This extreme block-size imbalance explains the poor parallel efficiency of LeidenMD for this matrix, despite its small number of colors. In contrast, LeidenCP substantially reduces the blocksize imbalance for thermal2, decreasing the Gini coefficient from 0.89 to 0.25 and Bmax /Bavg from 13.7 to 2.13. For the other matrices, LeidenCP maintains Bmax /Bavg around 2 or lower. These results demonstrate that the CPM function effectively suppresses the formation of excessively large communities and mitigates the sequential processing overhead within individual blocks. For the Leiden-based methods, the values of Cmax /Cavg remain moderate for all matrices, mostly between 1.1 and 1.7. This indicates that the colorwise workload imbalance is not as severe as the blocksize imbalance observed for LeidenMD, especially for thermal2. Therefore, the main performance bottleneck of LeidenMD is attributed primarily to oversized blocks rather than to color-wise load imbalance alone. Table 6 lists the calculated L2 cache efficiency during the execution of the ICCG method. The results demonstrate that LeidenMD achieves high L2 hit rates overall; in particular, for parabolic fem, ecology2, thermal2, and G3 circuit, the L2 hit rates reach 0.87 or higher. These results indicate a cache efficiency comparable to or even higher than that of the ABMC method. For Hook 1498, the L2 hit rate improves from 0.69 for the ABMC method to 0.78 for LeidenMD. This improvement indicates that LeidenMD extracts sets of vertices with strong internal connections within the nonzero structure as relatively massive blocks, thereby preserving data locality within individual blocks. On the other hand, LeidenCP exhibits lower L2 hit rates and higher L2 miss rates than those of LeidenMD across all matrices. This degradation is driven by the fact that the CPM function subdivides the blocks, which A value of G = 0 represents a perfectly uniform distri- increases the number of block boundaries and consebution, whereas G → 1 indicates an extremely uneven quently reduces continuous data reuse. However, despite its lower cache efficiency, LeidenCP achieves shorter exdistribution. Table 5 summarizes the load imbalance statistics of ecution times than those of LeidenMD for several matrithe representative blockings used in the performance ces, as shown in Fig. 2. This result indicates that ICCG comparison. In addition to the Gini coefficient of block performance is governed not only by cache efficiency, but sizes, the table shows the maximum block size, Bmax , also by the trade-offs among block size, intra-block sethe ratio of the maximum block size to the average block quential workload, number of block colors, parallel load size, Bmax /Bavg , and the ratio of the maximum color- balance, and number of iterations. wise node count to the average color-wise node count, Table 7 presents the average execution time of the Cmax /Cavg . Bmax is included to show the absolute size blocking process for each method, including file input of the largest sequential block, and the two ratios char- and output overhead. Because no significant difference 6

Table 5: Load imbalance statistics of representative blockings; Bmax /Bavg denotes the ratio of the maximum block size to the average block size and Cmax /Cavg denotes the ratio of the maximum color-wise node count to the average color-wise node count Matrix parabolic fem

apache2

Emilia 923

ecology2

thermal2

Geo 1438

Hook 1498

G3 circuit

Method ABMC LeidenMD LeidenCP ABMC LeidenMD LeidenCP ABMC LeidenMD LeidenCP ABMC LeidenMD LeidenCP ABMC LeidenMD LeidenCP ABMC LeidenMD LeidenCP ABMC LeidenMD LeidenCP ABMC LeidenMD LeidenCP

nb 256 101 2,277 128 69 2,253 64 39 448 128 144 6,366 1,024 1,099 6,404 128 37 721 512 46 779 512 116 9,777

nc 6 5 6 5 5 8 8 7 9 5 6 6 6 5 6 8 5 8 11 6 10 10 5 7

G 0.00 0.04 0.05 0.00 0.14 0.14 0.00 0.17 0.16 0.00 0.08 0.10 0.00 0.89 0.25 0.00 0.13 0.16 0.00 0.19 0.16 0.00 0.15 0.13

Table 6: L2 cache efficiency of Leiden-based ICCG Matrix parabolic fem apache2 Emilia 923 ecology2 thermal2 Geo 1438 Hook 1498 G3 circuit Matrix parabolic fem apache2 Emilia 923 ecology2 thermal2 Geo 1438 Hook 1498 G3 circuit

Bmax 2,055 6,295 407 5,588 16,639 594 14,424 42,474 4,138 7,813 12,480 275 1,200 15,354 409 11,235 55,883 3,668 2,926 51,547 3,576 3,097 23,447 332

Bmax /Bavg 1.00 1.21 1.76 1.00 1.61 1.87 1.00 1.79 2.01 1.00 1.80 1.75 1.00 13.7 2.13 1.00 1.44 1.84 1.00 1.58 1.86 1.00 1.72 2.05

Cmax /Cavg 1.83 1.41 1.41 1.17 1.35 1.51 1.13 1.34 1.37 1.25 1.54 1.41 1.40 1.42 1.43 1.19 1.11 1.25 1.44 1.67 1.68 1.48 1.55 1.34

Table 7: Average block generation time of ABMC and Leiden-based blocking method

LeidenMD Rhit Rmiss 0.87 0.060 0.86 0.051 0.80 0.039 0.87 0.052 0.90 0.050 0.78 0.040 0.78 0.037 0.88 0.044 LeidenCP Rhit Rmiss 0.73 0.20 0.74 0.17 0.72 0.086 0.72 0.18 0.83 0.10 0.71 0.090 0.71 0.088 0.74 0.16

Matrix parabolic fem apache2 Emilia 923 ecology2 thermal2 Geo 1438 Hook 1498 G3 circuit

ABMC [s] 1.32 1.35 9.04 1.29 3.89 15.2 15.4 4.51

Leiden [s] 3.48 4.58 17.9 4.81 8.20 29.5 28.8 8.95

tive community detection. However, the ABMC results reported in this study represent a tuned baseline, because they correspond to the best performance among multiple candidate values of the number of blocks nb . Although ABMC has a lower blocking cost per trial, obtaining such a configuration may require several trial runs. In contrast, LeidenCP generates the block structure once using a fixed γCP without explicitly prescribing nb , thereby reducing the problem-dependent block-count tuning burden. For a single isolated solve where the optimal ABMC parameter is already known, the higher blocking cost of LeidenCP may offset the reduction in ICCG execution time. LeidenCP may also be less advantageous for highly dynamic problems in which the matrix structure changes frequently, because the blocking cost cannot be effectively amortized across multiple solves. Thus, LeidenCP is particularly suitable when the same matrix or preconditioner can be reused, such as in mul-

was observed between the blocking times of LeidenMD and LeidenCP, the average of these two configurations is reported. For ABMC, the blocking time depends on the number of blocks nb ; therefore, the table reports the blocking time corresponding to the nb value that yields the shortest ICCG execution time for each matrix. The measurements show that the blocking cost of the Leiden-based methods is consistently higher than that of ABMC, reflecting the algorithmic cost of itera7

tiple right-hand-side problems or time-step simulations, where the blocking cost can be amortized over multiple solves.

γMD=1.0

Average execution time [s]

Sensitivity Analysis of Resolution Parameters

In the main experiments, we used γMD = 1.0 for LeidenMD and γCP = 1.0 × 10−3 for LeidenCP. These two parameters belong to different quality functions, and their numerical values are not directly comparable. For LeidenMD, the standard setting γMD = 1.0 often produces coarse partitions with a small number of blocks. Because such coarse partitions can limit parallelism and increase the sequential processing overhead within large blocks, we also evaluated larger values, namely γMD = 2.0, 4.0, 8.0, and 16.0, to examine the effect of finer modularity-based partitions. For LeidenCP, we varied γCP from 5.0 × 10−4 to 2.0 × 10−3 , corresponding to one half to twice the baseline value γCP = 1.0 × 10−3 . This range was chosen to evaluate local robustness around the baseline setting, rather than to perform an exhaustive parameter search or to claim the universal optimality of a single parameter value.

7.1

Hook_1498

γMD=4.0

30.0

7

Emilia_923

γMD=2.0 γMD=8.0

thermal2

γMD=16.0

20.0

Geo_1438

10.0 ecology2

G3_circuit apache2

0.0

parabolic_fem

500

1000

1500

2000

2500

Average no. of iterations

Figure 3: Scatter plot of average execution time versus average number of iterations for LeidenMD-based ICCG with various resolution parameter values time, higher values degrade both the number of iterations and solver execution. These variations demonstrate that finer block partitioning does not straightforwardly improve performance, because the execution time remains highly sensitive to the complex balance among the number of iterations, block size, intra-block sequential workload, and parallel load balancing. For LeidenMD, these findings confirm that while adjusting γMD can optimize the execution time for specific matrices, it frequently fails to achieve performance competitive with that of LeidenCP. This limitation arises from the mathematical definition of modularity, which evaluates the divergence from the expected number of edges based on the global degree distribution. Consequently, simply increasing γMD does not necessarily yield block sizes or load balancing tailored for parallel preconditioning in the ICCG method. Compared with modularity, the CPM is better suited to extracting localized connectivity structures from sparse-matrix graphs because it evaluates community density using a fixed, size-independent threshold. Moreover, the quadratic resolution term in Eq. (2) penalizes large communities, thereby suppressing oversized blocks and reducing block-size imbalance. These properties contribute to the competitive performance of LeidenCP. However, because the CPM includes the resolution parameter γCP , its sensitivity to this parameter must also be examined.

Effect of γMD

The resolution parameter γMD in LeidenMD controls the granularity of the partitions obtained via community detection. In general, a larger value of γMD yields smaller communities, thereby increasing the total number of blocks nb . As shown in Table 4, the number of blocks generated by LeidenMD under the default configuration tends to be smaller than those for the optimal configurations of the ABMC method. Increasing γMD can potentially generate finer blocks and mitigate the degree of load imbalance. Fig. 3 illustrates the performance of the ICCG method when the block structures obtained by varying γMD from 1.0 to 16.0 are applied to the parallel preconditioning. In terms of execution time, the test matrices exhibit distinct responses to higher γMD values. For matrices characterized by severe initial block-size imbalances, such as thermal2, Hook 1498, and Geo 1438, increasing γMD subdivides excessively oversized blocks into finer ones, thereby eliminating the computational bottlenecks associated with prolonged sequential processing within individual blocks. Consequently, the overall execution time is markedly reduced, achieving a speedup of approximately 2.16 times for thermal2 at γMD = 16.0. In contrast, for parabolic fem, apache2, ecology2, and G3 circuit, further block refinement yields negligible effects and causes performance saturation. Because sufficient parallel concurrency is already achieved at the default resolution (γMD = 1.0), smaller blocks likely degrade data locality and lower cache efficiency, thereby offsetting the minor gains in parallelism. Meanwhile, Emilia 923 exhibits a non-monotonic performance trend. While γMD = 2.0 reduces the execution

7.2

Effect of γCP

For LeidenCP, we evaluate how the CPM resolution parameter γCP affects the block structure and ICCG performance. Table 8 summarizes the corresponding block statistics. Fig. 4 shows the relationship between the average execution time and the average number of iterations for various values of γCP . From Table 8, as γCP increases, the number of blocks nb generally increases for all test matrices, indicating that larger γCP values yield finer partitions. However, 8

Table 8: Sensitivity of LeidenCP block statistics to γCP ; each entry is shown in the form nb /nc /G, where nb is the number of blocks, nc is the number of block colors, and G is the Gini coefficient of block sizes γCP 5.0 × 10−4 7.5 × 10−4 1.0 × 10−3 1.25 × 10−3 1.5 × 10−3 2.0 × 10−3 parabolic fem 1,418 / 6 / 0.04 1,868 / 6 / 0.04 2,277 / 6 / 0.05 2,672 / 6 / 0.05 2,995 / 6 / 0.05 3,687 / 6 / 0.05 apache2 1,185 / 6 / 0.12 1,718 / 7 / 0.14 2,253 / 8 / 0.14 2,809 / 8 / 0.14 3,311 / 8 / 0.14 4,164 / 8 / 0.14 Emilia 923 253 / 9 / 0.17 356 / 10 / 0.17 448 / 9 / 0.16 532 / 9 / 0.15 627 / 10 / 0.16 794 / 10 / 0.16 ecology2 3,941 / 6 / 0.09 5,227 / 6 / 0.10 6,366 / 6 / 0.10 7,370 / 6 / 0.10 8,371 / 6 / 0.10 10,134 / 6 / 0.10 thermal2 4,368 / 6 / 0.32 5,448 / 6 / 0.28 6,404 / 6 / 0.25 7,335 / 6 / 0.24 8,165 / 6 / 0.22 9,749 / 6 / 0.20 405 / 9 / 0.16 581 / 9 / 0.16 721 / 8 / 0.16 853 / 9 / 0.15 980 / 9 / 0.16 1,224 / 9 / 0.16 Geo 1438 Hook 1498 440 / 9 / 0.15 622 / 9 / 0.15 779 / 10 / 0.16 921 / 9 / 0.16 1,077 / 9 / 0.16 1,354 / 9 / 0.16 G3 circuit 6,065 / 7 / 0.13 8,020 / 7 / 0.13 9,777 / 7 / 0.13 11,363 / 7 / 0.13 12,828 / 7 / 0.13 15,681 / 7 / 0.13 Matrix

value γCP = 1.0 × 10−3 is not an isolated or exceptional setting. Rather, it lies within a practical range for which LeidenCP produces balanced block structures and competitive ICCG performance. These observations support the robustness of the CPM-based blocking approach with respect to moderate changes in γCP .

γCP=5e−4

Hook_1498

γCP=7.5e−4 γCP=1e−3

Average execution time [s]

γCP=1.25e−3

20.0

γCP=1.5e−3 γCP=2e−3

Emilia_923

thermal2

10.0

Geo_1438

G3_circuit

8

ecology2

apache2

0.0

In this study, we proposed a blocking framework for parallel preconditioning in the ICCG method that utilizes the Leiden method, a high-performance community detection algorithm that optimizes graph-partitioning quality functions. We then comprehensively evaluated its performance in comparison with the conventional ABMC method. Unlike the ABMC method, the Leiden method eliminates the requirement to specify the number of blocks or block sizes in advance, offering the distinct advantage of automatically extracting natural community structures inherent to the matrix nonzero structure. However, the blocks generated via community detection are not universally suitable for parallel preconditioning. Specifically, when modularity is employed as the quality function, uneven block sizes and the presence of giant clusters severely degrade parallel load balancing, thereby increasing the execution time for certain matrices. Conversely, LeidenCP successfully suppresses the formation of excessively oversized blocks. As a result, the structural imbalance in block sizes is minimized, yielding superior execution times compared to those of LeidenMD across the majority of test matrices. Through experiments with various values of the resolution parameter γMD for LeidenMD, we confirmed that increasing this parameter mitigates load imbalance and reduces the execution time for specific configurations. This optimization effect is particularly significant for matrices characterized by severe block-size discrepancies and those derived from structured problems with high ANZR values. Importantly, while the ABMC method requires the number of blocks to be specified as an input parameter and its optimal value strongly depends on the matrix properties, LeidenCP avoids prescribing the number of blocks explicitly. The sensitivity analysis of γCP showed that the baseline value used in the main ex-

parabolic_fem

0

1000

2000

Conclusion and Future Work

3000

Average no. of iterations

Figure 4: Scatter plot of average execution time versus average number of iterations for LeidenCP-based ICCG with various resolution parameter values

the number of block colors nc remains within a relatively narrow range. For most matrices, nc stays between 6 and 10 throughout the tested range of γCP . This indicates that increasing γCP refines the block partition while keeping the number of block colors, and hence the synchronization overhead, relatively small. The Gini coefficient of block sizes also remains moderate over the tested range of γCP . For example, parabolic fem, apache2, ecology2, Emilia 923, Geo 1438, Hook 1498, and G3 circuit maintain Gini coefficients below approximately 0.17. Although thermal2 exhibits larger imbalance than those of the other matrices, its Gini coefficient decreases from 0.32 to 0.20 as γCP increases from 5.0 × 10−4 to 2.0 × 10−3 . These results indicate that the CPM resolution term effectively suppresses the formation of excessively large blocks over a range of γCP values. The ICCG performance in Fig. 4 further shows that the performance of LeidenCP is not determined solely by the number of generated blocks. Finer partitions can improve load balance by reducing oversized blocks, but excessive refinement may also reduce intra-block data locality and change the quality of the preconditioner. Consequently, the execution time and the number of iterations do not necessarily vary monotonically with γCP . Nevertheless, the results show that the baseline 9

periments lies within a practical range that yields balanced block structures and competitive ICCG performance. Thus, LeidenCP avoids explicitly prescribing the number of blocks, thereby reducing the burden of problem-dependent parameter selection, although it is not entirely parameter-free. The practical advantage of LeidenCP depends on how the blocking cost is amortized. For a single isolated solve, especially when the optimal value of nb for ABMC is already known, the higher blocking cost of LeidenCP may offset its reduction in ICCG execution time. Therefore, as indicated by the preprocessing-cost analysis, LeidenCP is particularly suitable for applications in which the same matrix or preconditioner can be reused, such as multiple right-hand-side problems or time-step simulations. In future work, we plan to evaluate clustering formulations based on quality functions other than modularity and the CPM. We also intend to investigate accelerated block generation frameworks by parallelizing the quality-function maximization process [14]. Additionally, we will explore integrating fast structural reordering methods, such as Rabbit Ordering [15], into our blocking pipeline to further optimize data locality and solver convergence.

[8] V. A. Traag, L. Waltman, and N. J. van Eck, “From Louvain to Leiden: Guaranteeing well-connected communities,” Scientific Reports, vol. 9, no. 1, p. 5233, Mar. 2019. [9] V. A. Traag, P. Van Dooren, and Y. Nesterov, “Narrow scope for resolution-limit-free community detection,” Phys. Rev. E, vol. 84, no. 1, p. 016114, Jul. 2011. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevE.84.016114 [10] T. A. Davis and Y. Hu, “The university of Florida sparse matrix collection,” ACM Trans. Math. Softw., vol. 38, no. 1, Feb. 2011. [11] Y. Saad, Iterative Methods for Sparse Linear Systems: Second Edition, ser. Other Titles in Applied Mathematics. Society for Industrial and Applied Mathematics, 2003. [12] G. Csardi and T. Nepusz, “The igraph software package for complex network research,” InterJournal Complex Systems, vol. 1695, 2006. [13] F. Cowell, Measuring Inequality. sity Press, 2011.

Oxford Univer-

[14] J. Zeng and H. Yu, “Parallel Modularity-Based Community Detection on Large-Scale Graphs,” in 2015 IEEE International Conference on Cluster Computing, 2015, pp. 1–10.

References

[1] T. Iwashita, H. Nakashima, and Y. Takahashi, “Algebraic Block Multi-Color Ordering Method for [15] J. Arai, H. Shiokawa, T. Yamamuro, M. Onizuka, Parallel Multi-Threaded Sparse Triangular Solver and S. Iwamura, “Rabbit Order: Just-in-Time Parin ICCG Method,” in 2012 IEEE 26th Internaallel Reordering for Fast Graph Analysis,” in 2016 tional Parallel and Distributed Processing SympoIEEE International Parallel and Distributed Prosium, 2012, pp. 474–483. cessing Symposium (IPDPS), 2016, pp. 22–31. [2] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener, “Graph structure in the web,” Computer Networks, vol. 33, no. 1, pp. 309–320, 2000. [3] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’ networks,” Nature, vol. 393, no. 6684, pp. 440–442, Jun. 1998. [4] A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999. [5] M. Girvan and M. E. J. Newman, “Community structure in social and biological networks,” Proceedings of the National Academy of Sciences, vol. 99, no. 12, pp. 7821–7826, 2002. [6] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” Journal of Statistical Mechanics: Theory and Experiment, vol. 2008, no. 10, p. P10008, 2008. [7] A. Clauset, M. E. J. Newman, and C. Moore, “Finding community structure in very large networks,” Phys. Rev. E, vol. 70, no. 6, p. 066111, Feb. 2004. 10

Related documents

• Sample Efficient Generative Optimization for Molecular Design#366280
• Initialisation Determines the Basin: Efficient Codebook Optimisation for Extreme LLM Quantization#2622
• Learning Metamaterial Eigenmodes with Wavelet-Encoded Fourier Neural Operators#985490
• Crossmatch RAVE DR5 and UCAC4#934074
• Hybrid gradient descent method for galactic modelling using the enhanced newtonian dynamics framework#655219