Technical Summary: Embedding-based Methods for Linear Solver Performance Prediction

Problem Statement

The solution of large, sparse linear systems is a primary performance bottleneck in scientific computing applications, particularly those arising from differential equations. While modern libraries like PETSc offer numerous solver and preconditioner configurations, no single "silver bullet" exists; optimal choices are highly dependent on specific problem instances, matrix properties, and hardware environments (e.g., parallelization, accelerators).

Existing data-driven strategies for solver selection face three main limitations:

1. Dependency on Expensive Features: Many approaches rely on costly numerical features (e.g., spectral information, condition number estimates) that are computationally expensive to compute, negating the benefits of automated selection.
2. Limited Scope: Previous works often restrict their problem sets (e.g., only symmetric positive definite matrices) or fail to generalize across diverse scenarios.
3. Inadequate Evaluation Metrics: Standard classification metrics (e.g., accuracy) treat all misclassifications equally. They fail to distinguish between predicting a sub-optimal but effective solver versus predicting a divergent one, which is critical for practical utility. Furthermore, they often ignore the relative performance ranking of solvers.

Methodology

The authors propose a modular, low-cost embedding-based framework that decouples performance modeling from feature representation and downstream prediction. The pipeline consists of four distinct stages:

1. Feature Selection and Extraction

The framework utilizes a set of inexpensive numerical features (computable in $O(N)$ or $O(nnz)$ time, where $N$ is rows and $nnz$ is non-zeros).

• Selection: The Boruta "all-relevant" feature selection scheme is applied to identify features that perform better than randomly shuffled shadow counterparts.
• Exclusion: Costly features, such as direct condition number estimates, are explicitly excluded to ensure low inference overhead.
• Result: A reduced feature set is derived, containing properties like matrix dimensions, sparsity patterns, and norm statistics, but excluding expensive spectral estimates.

2. Embedding Learning (Offline Phase)

Instead of learning a direct mapping from features to solver performance, the framework learns a low-dimensional performance vector space.

• Data Source: Embeddings are learned solely from observed performance data (scores derived from runtime and residual values) across a training set of matrices and solver configurations.
• Mechanism: Matrices and solvers are treated as tokens in a vocabulary. Using models like Word2Vec (skip-gram with negative sampling) or GloVe, the system learns embeddings where geometric proximity reflects similarity in solver behavior.
• Objective: Effective matrix-solver pairs are mapped to close vectors, while ineffective pairs are separated. This captures complex relationships between matrices and solvers that are not explicitly encoded in numerical descriptors.

3. Projection (Online Phase)

For a new, unseen problem instance $x'$, the framework must map it into the learned embedding space without retraining.

• Linear Combination: The reduced feature vector of the new instance is approximated as a sparse, non-negative linear combination of the training feature vectors ($\hat{f}(x') \approx \alpha \cdot F$).
• Mapping: The same coefficients ($\alpha$) are applied to the corresponding training embeddings ($G$) to generate the projection $\hat{g}(x') = \alpha \cdot G$.
• Constraint: The projection is constrained to non-negative coefficients for interpretability, and standard linear regression is used to achieve sparsity without additional penalization.

4. Prediction

The projected embedding is fed into a downstream predictor to determine solver suitability.

• Algorithm: A simple $k$-nearest neighbors (k-NN) algorithm operates directly in the embedding space.
• Output: The system treats the problem as a multilabel classification task, predicting a subset of promising solvers rather than a single label. This allows for ranking-based evaluation.
• Metrics: Evaluation focuses on user-centric metrics:
  • MAPE (Mean Average Percentage Error): Measures the relative performance gap between the predicted top solver and the optimal solver.
  • nDCG (Normalized Discounted Cumulative Gain) & LRAP: Evaluate the quality of the ranked list of predicted solvers.
  • 1-error: Measures how often the optimal solver is absent from the predicted set.

Key Contributions

1. Decoupled Architecture: The framework explicitly separates the learning of performance-space embeddings from the feature-based projection of unseen matrices. This modularity allows individual components (feature sets, embedding models, predictors) to be exchanged without retraining the entire pipeline.
2. Low-Cost Inference: By relying on inexpensive numerical features and a linear projection step, the method avoids the computational overhead of expensive feature extraction (e.g., spectral analysis) during inference.
3. Multilabel Formulation: The problem is formulated as multilabel classification, enabling the prediction of a set of "good enough" solvers and facilitating the use of ranking metrics (nDCG, LRAP) that better reflect practical solver selection needs.
4. User-Centric Evaluation: The study prioritizes metrics like MAPE and 1-error over simple accuracy, acknowledging that a slightly sub-optimal solver is often acceptable, whereas a divergent solver is catastrophic.

Experimental Results

The framework was evaluated on 621 matrices from the SuiteSparse collection across 101 PETSc solver configurations (including Krylov methods and preconditioners like BoomerAMG, ILU, and ParaSails).

• Performance with Full Features: When including expensive numerical features, the embedding-based approach achieved a 17% increase in top-prediction accuracy over classical feature-based models. It reduced MAPE by 37% and 1-error by 46%.
• Performance with Reduced Features: Even when restricted to the low-cost feature set (excluding expensive spectral estimates), the embedding approach remained competitive with classical models trained on full feature sets.
  • It achieved approximately 24% lower MAPE and 24% lower 1-error compared to classical baselines across a broad range of problems.
  • For the strict "time-residual" score, the reduced embedding model reduced the 1-error from ~90% (Random Forest) to ~58%.
• Robustness: The proposed method failed to predict a convergent solver in less than 10% of cases and consistently outperformed the default PETSc configuration.

Significance and Claims

The paper claims that learned embeddings can effectively replace expensive matrix features for solver selection while maintaining low model complexity. The significance of this work lies in:

• Scalability: The approach offers a scalable alternative to direct feature-based classification by minimizing inference overhead.
• Generalizability: The modular design supports different predictive mechanisms and evaluation criteria, making it adaptable to diverse problem scenarios.
• Practical Utility: By focusing on relative performance and multilabel prediction, the framework aligns more closely with the practical needs of scientific computing users, who often require a "good enough" solution rather than a theoretically perfect one.

The authors note that the effectiveness of the embedding depends on the diversity and coverage of the training data. They suggest that future work could explore nonlinear projection mechanisms and extend the framework to hardware-aware prediction and broader numerical tasks (e.g., least-squares or non-linear solvers).