Yannick Funk, Markus Götz and Hartwig Anzt from the Karlsruhe Institute of Technology, the Helmholtz AI local unit of Energy @ KIT, the Helmholtz Young Investigator Group ‘Fixed-Point Methods for Numerics at Exascale (FiNE)’ and the Innovative Computing Laboratory (ICL) at the University of Tennessee have investigated the usage of deep-learning approaches to predict optimal algorithms for sparse linear systems.

Picture: Yannick Funk (left), Markus Götz (center), and Hartwig Anzt (right)

Solving sparse linear systems is a key task in a number of computational problems, such as data analysis and simulations, and majorly determines overall execution time. Choosing a suitable iterative solver algorithm can significantly improve time-to-completion. We have investigated a deep learning approach designed to predict the optimal iterative solver for a given sparse linear problem. For this, we have identified useful linear system features to drive the prediction process, the metrics we use to quantify the iterative solvers’ time-to-approximation performance and a comprehensive experimental evaluation of the prediction quality of the neural network. Using a hyperparameter optimization and an ablation study on the SuiteSparse matrix collection we have inferred the importance of distinct features, achieving a top-1 classification accuracy of 60% and a top-4-accuracy of 90% from a set of seven solvers.

What are the involved challenges?

The major issue of this study was how to pass the sparse linear systems to a neural network. How do you encode a singular example? As an image? As a graph? Ultimately, a set of hand-crafted features and a multi-layer perceptron proved to be the most efficient approach. In a subsequent ablation study, some of the features that we have expected to be most likely useful have been revealed as redundant - a somewhat surprising find.

What did others do?

Prior work, mainly by Sood et al., have investigated classical machine learning approaches to predict the optimal algorithm for a sparse linear system. Using an elaborate ensemble of classifiers based on support vector machines (SVMs), decision trees (DTs) or k-nearest neighbours algorithm (kNN) they have achieved a top-1 prediction accuracy of up to 87%. This approach is more precise compared to our proposal. However, the massive amount of required computations eat up all benefits from suggesting a better solver. In contrast, our proposed deep learning approach still allows you to profit from a better solver prediction due to a lower inference time.

Why is the optimal prediction of sparse linear solvers important?

Selecting an optimal sparse linear solver algorithm for a computational problem can drastically impact the time-to-solution. If you think of large simulations with billions to trillions of necessary operations this does not only allow to perform more runs in a shorter amount of time, but also a drastically reduced environmental footprint due to reduced power consumption.

Figure: Confusion matrix for full (left), reduced (center) and final (right) feature set.

More information

• Funk, Y., Götz, M. and Anzt, H., 2022. Prediction of Optimal Solvers for Sparse Linear Systems Using Deep Learning. In Proceedings of the 2022 SIAM Conference on Parallel Processing for Scientific Computing (pp. 14-24). Society for Industrial and Applied Mathematics, doi: https://doi.org/10.1137/1.9781611977141.2
• GitHub code & instructions: https://github.com/yannickfunk/MLLAFastestSolver