GNN-Powered Learned Preconditioners for Linear Systems

Sammanfattning

The rapid growth of Artificial Intelligence has increased the demand for parallelized computational infrastructure, which has intensified the interest in finding optimization methods for solving linear systems that integrate seamlessly into such infrastructures. The applications include scientific computing, finance, wireless communication (e.g., MIMO detection), etc. In wireless communication, low-latency solutions are critical (millisecond scale), which calls for very efficient solvers. Existing methods rely heavily on matrix inverses, which scale poorly with increased system dimensions and are not parallelizable, which limits the latency and potential to be usedin parallelized computational infrastructure. This thesis instead proposes a hybrid approach that merges iterative solvers, the Neumann series, and Graph Neural Networks (GNNs) to make the solver parallelizable and have better scaling capabilities. We propose using the gradient descent algorithm as the iterative solver, which, for ill-conditioned systems, convergence is prohibitively slow, especially in low-latency environments. To combat this, we precondition the linear system, where the optimal preconditioner is the inverse of the Hessian of the objective function. In this thesis, we propose to use the Neumann series to estimate this inverse, using a neurally-enhanced seed matrix from a GNN to accelerate convergence. While this approach will not have lower inherent complexity than the exact solvers, it does offer full parallelizability, as it only consists of matrix multiplications; therefore, it has the potential to be more computationally efficient on parallelized computationinfrastructure. The method demonstrates consistent improvements: an 80-90% reduction in the condition number over the non-conditioned system (with order 3 Neumann series) and a 30-70% reduction over the naive methods of choosing the seed matrix. However, the performance of the model degrades for ill- conditioned systems (κ > 103), requiring much higher-order Neumann approximations to yield acceptable results (order > 255). While the proposedmodel provides a good starting point for finding a parallelizable solver, more work is needed to determine the practical feasibility and overcome the performance degradation for ill-conditioned systems.