BandPC: Learning Residual-Band Preconditioner Combinations for Flexible Conjugate Gradient Solvers

The gist: BandPC proposes a datadriven framework that leverages graph neural networks (GNNs) to predict multi-stage preconditioning strategies for the flexible conjugate gradient (FCG) method.

Introduction and Motivation

Solving large-scale sparse linear systems is a fundamental task in scientific computing and industrial simulation, with applications ranging from finite element structural analysis [1] and computational fluid dynamics [2] to geophysical electromagnetic inversion [3]. The Conjugate Gradient (CG) algorithm is a well-established iterative solver for sparse symmetric positive definite (SPD) linear systems of the form Ax=b. However, CG exhibits slow convergence for ill-conditioned matrices, making preconditioning essential for practical performance [6]. Designing robust and generalizable preconditioners remains a longstanding challenge [7]. A key observation from the investigation is that different stages of the iterative convergence process impose different requirements on the preconditioner. In the early stages, when residuals are large, stronger and more aggressive preconditioners with effective smoothing properties are preferable. As convergence proceeds and residuals decrease, lightweight preconditioners become sufficient and more computationally efficient. The Flexible Conjugate Gradient (FCG) method naturally supports this idea, as it allows a different preconditioner to be used at each iteration without sacrificing convergence guarantees.

BandPC Framework

Motivated by this observation, the paper proposes a residual-band preconditioning strategy that partitions the solving process into multiple residual-defined stages, each assigned a distinct preconditioner. With five candidate preconditioners distributed over three stages, it defines a structured search space of 125 candidate combinations. BandPC is defined as a Graph Neural Network (GNN)-based framework that represents a sparse matrix as a graph and efficiently predicts a promising preconditioner sequence for unseen matrices. The main contributions include:

1. Proposing a residual-band preconditioning strategy that partitions the iterative solving process into multiple residual-defined stages, each assigned a distinct preconditioner [3].

2. Introducing a soft-labeling mechanism for training data generation where multiple near-optimal combinations are retained and their scores are renormalized into a label distribution [3].

3. Introducing a hierarchical feature representation that integrates node-level attributes, edge-level algebraic coupling strengths, and global matrix statistics to capture localized topology and macro-scale numerical characteristics [3].

4. Proposing a GNN architecture that achieves high-precision performance ranking for diverse preconditioner combinations [3].

Methodology

The problem is formulated as a supervised distribution-learning problem over candidate preconditioner combinations, where the FCG iteration is partitioned into three non-overlapping residual bands based on the residual norm k k 2 r Ax b = 0 at iteration k [3]. For each interval i I, a preconditioner Pi is selected from the candidate set P None Jacobi IC BlockJacobi AMG = (None, Jacobi, BlockJacobi, IC(0), AMG) [3]. This results in a total of 125 possible preconditioner combinations denoted as 1 2 3 P = (P i, P j, P k). The performance of each combination Pi is quantified by a score i s calculated as: log(1/ if the system is solved successfully, 0 if the solver times out or fails) [3].

The matrix-to-graph representation interprets a sparse matrix as the adjacency matrix of a graph, where row/column indices correspond to nodes and off-diagonal nonzeros are mapped to edges [6]. Node and global features employed in the GNN include local degree profile, diagonal dominance, and global features such as Matrix size, Estimated condition number, 1-norm, Density, Structure variability, Average distance to diagonal, Bandwidth, Number of nonzero diagonals (Table 1) [3]. The GNN architecture uses a dual-path feature extraction framework: a structural path captures complex inter-row dependencies using graph convolutional layers with multi-head attention mechanisms for algebraic coupling strengths [7], and a statistical path extracts global features via an MLP [7]. These two paths converge at a fusion module, which feeds into a deep MLP predictor to generate the predicted Relative Performance Scores for the 125 preconditioner combinations [3].

Results and Evaluation

Experiments were conducted on a hybrid dataset of 1200 sparse symmetric positive definite (SPD) matrices, consisting of 116 real-world SPD matrices from the SuiteSparse Matrix Collection and 1,084 synthetic SPD matrices [4]. The results demonstrate that BandPC achieves the best iteration count and solution time on 41.3% and 33.1% of test matrices, respectively, even when compared with each matrix’s individually best traditional preconditioner [5].

The comparison of predicted combinations with traditional methods showed significant acceleration advantages; for example, for bcsstk36 the optimal combination is P Jacobi, IC(0), IC(0) = (Jacobi, IC(0), IC(0)) [10]. This highlights BandPC's capability to adaptively navigate the complex search space of preconditioning sequences to find the most efficient solution for challenging linear systems [12]. The model's efficacy is further characterized by metrics such as Label Ranking Average Precision (LRAP) and Normalized Discounted Cumulative Gain (NDCG), which measure ranking quality, and Speedup Retention Rate (SRR), which quantifies the practical acceleration efficacy of the proposed method [13]. BandPC consistently ranks among the top two in computational efficiency for the clear majority of cases, with no instances of significant performance degradation [14].

Conclusion

In this paper, we proposed BandPC, a GNN-based framework for learning residual-band preconditioner combinations in flexible conjugate gradient solvers. Experiments on synthetic SPD problems and SuiteSparse matrices demonstrate that BandPC achieves the best iteration count and solution time on 41.3% and 33.1% of test matrices, respectively, even when compared with each matrix’s individually best traditional preconditioner [5]. These results indicate that learned multi-stage preconditioner scheduling can effectively accelerate flexible CG solvers. Future work will extend BandPC to non-SPD systems, incorporate preconditioning construction and switching costs into the objective, explore adaptive band boundaries, and investigate more efficient label generation and larger preconditioner libraries [14].

--- Page 1 ---

BandPC: Learning Residual-Band Preconditioner Combinations for Flexible Conjugate Gradient Solvers D. M. LI a, b, c, d a. School of Civil Engineering and Architecture, Wuhan University of Technology, Wuhan, 430070, China b. Embodied Physical Intelligence Center in Civil Engineering, Wuhan University of Technology, Wuhan, 430070 China c. Key Laboratory of Low-Altitude Technology and Smart Urban Renewal Department of Housing and Urban-Rural Development of Hubei Province Wuhan University of Technology, Wuhan, 430070 China d. Sanya Science and Education Innovation Park of Wuhan University of Technology Sanya, 572000 China Abstract:The conjugate gradient (CG) method is a classical iterative solver for sparse symmetric positive definite (SPD) linear systems, but its convergence strongly depends on the spectral properties of the system matrix. Preconditioning can improve these properties; however, designing preconditioners that generalize across diverse and irregular sparsity patterns remains challenging. We propose BandPC (Band Preconditioner Combinations where “Band” denotes residual-norm bands), a datadriven framework that leverages graph neural networks (GNNs) to predict multi-stage preconditioning strategies for the flexible conjugate gradient (FCG) method. BandPC partitions the FCG iteration into three residual-norm-based bands and defines a structured search space of 125 candidate combinations over five classical preconditioners. By exploiting FCG’s ability to switch preconditioners across iterations, BandPC learns to map matrix structure directly to a promising preconditioner sequence. To improve training and generalization, we introduce a soft-labeling mechanism that retains near-optimal combinations and normalizes their scores into a label distribution, together with a hierarchical feature representation that captures node-level attributes, edge-level algebraic coupling strengths, and global matrix statistics. Experiments on a hybrid benchmark of synthetic SPD problems and diverse matrices from the SuiteSparse Collection show that BandPC achieves the best iteration count and solution time on 41.3% and 33.1% of test matrices, respectively, even when compared with each matrix’s individually best traditional preconditioner. Key words:BandPC; Flexible Conjugate Gradient; Preconditioner Combinations; Residual-Norm Bands; Graph Neural Networks; Sparse Linear Systems

--- Page 2 ---

1 Introduction Solving large-scale sparse linear systems is a fundamental task in scientific computing and industrial simulation, with applications ranging from finite element structural analysis [1] and computational fluid dynamics [2] to geophysical electromagnetic inversion [3]. Existing solution techniques fall into two broad categories: direct methods and iterative methods. Direct methods, which rely on matrix factorizations such as LU or Cholesky decomposition, offer high numerical accuracy, but their prohibitive computational complexity and memory requirements severely limit scalability in large-scale settings. Iterative methods, by contrast, refine an initial guess through successive approximations and are therefore more widely adopted in practice, especially when approximate solutions satisfy the required accuracy [4, 5]. The Conjugate Gradient (CG) algorithm is a well-established iterative solver for sparse symmetric positive definite (SPD) linear systems of the form Ax=b. However, CG exhibits slow convergence for ill-conditioned matrices, making preconditioning essential for practical performance [6]. Despite the importance of preconditioners, designing robust and generalizable ones remains a longstanding challenge [7]. Effective preconditioning must be tailored to the sparsity structure of the matrix, whereas neural network-based preconditioners are often restricted to narrow problem domains with relatively uniform sparsity patterns.

1. Bold header: Enhanced Preconditioner Scheduling for FCG

The improved AI system can predict a promising preconditioner sequence by partitioning the FCG iteration into three non-overlapping residual bands based on the residual norm, directly exploiting the observation that different stages of the iterative convergence process impose different requirements on the preconditioner.

2. Bold header: Robust Training via Soft-Labeling

The system will mitigate overfitting by introducing a mechanism where multiple near-optimal preconditioner combinations are retained, and their scores are renormalized into a label distribution, which is defined by retaining indices where 0 ≤ 0.9 max(i, j) s ≥ 1 (Equation 3).

3. Bold header: Comprehensive Feature Integration for GNNs

The hierarchical feature representation will be enhanced by explicitly integrating node-level attributes, edge-level algebraic coupling strengths, and global matrix statistics, allowing the GNN to capture both localized topology and macro-scale numerical characteristics for more discriminative embeddings.

4. Bold header: High-Precision Ranking Metrics

To better characterize practical acceleration, the system will use novel metrics like Speedup Retention Rate (SRR), defined as the ratio of the solving time achieved by the GNN-predicted combination to that of the ground-truth optimal combination, formally measuring how much of the theoretically achievable speedup is retained.

5. Bold header: Adaptive Solver Selection Integration

The system can be extended to jointly select solvers and preconditioners by utilizing a GAT architecture that projects "edge features via learnable transformation matrices and subsequently concatenates with the corresponding node features, enabling the model to jointly leverage both structural and value-level information of the sparse matrix."