Estimating condition number with Graph Neural Networks

Code

• github.com/inexascale/sparse-kappa
  OfficialIn paper★ 0

Abstract

In this paper, we propose a fast method for estimating the condition number of sparse matrices using graph neural networks (GNNs). For efficient deployment of GNNs, we introduce a graph feature construction with O(nnz + n) complexity, where nnz is the number of non-zero elements in the matrix and n denotes the matrix dimension. We propose two schemes for estimating the matrix condition number using GNNs; one follows by decomposing the condition number and predicts the relatively more computationally intensive part \|A^-1\|, without explicitly forming the inverse, while the other is to predict the whole condition number κ. Our approach can be extended to an arbitrary norm. Extensive experiments are conducted for the estimation of the 1-norm and 2-norm condition numbers, which show that our method achieves a significant speedup over the traditional numerical estimation methods. Our software for GNN condition number estimator is made publicly available at https://github.com/inEXASCALE/sparse-kappa.

Reproductions