Adaptive perturbations improve solving linear systems with less computation

From smoothed analysis to backward error: The power of adaptive perturbations

Data Structures and Algorithms

Summary

Solving systems of linear equations is crucial in computing but can sometimes take a lot of time. The authors show that when solving these systems, carefully changing (or perturbing) the input data based on the original problem helps solve it more efficiently than just adding random noise. They prove that random changes alone need many steps, but adaptive tweaks require fewer. They also find that the structure of the data can change how hard it is to solve these equations.

What this means in practice

  • For numerical linear algebra developers: Optimize algorithms that solve linear systems by using adaptive perturbations to reduce computational steps and improve backward error guarantees.
  • For scientific computing engineers: Enhance simulation software that relies on solving linear systems efficiently by incorporating matrix structure-aware techniques to lower computation costs.

A theory result. No direct application yet.

Authors

Michał Dereziński, Michael W. Mahoney, Raphael A. Meyer, Christopher Musco

Abstract

Smoothed analysis has become a central tool in theoretical computer science, often allowing for significant improvements to worst-case running times if we settle for a solution to a small random perturbation of the problem instance. This is closely related to the classical concept of backward error in numerical analysis, which allows an algorithm to return a solution to an arbitrary perturbation of the problem. Despite the qualitative similarity of these concepts, we show that they can exhibit large quantitative differences. Notably, we prove that, while a linear system with any $n \times n$ matrix $A$ can be solved to backward error $ε$ using $O(\log(n) / ε)$ matrix-vector products with $A$, any algorithm that solves a random $ε$-sized perturbation of $A$ requires $Ω(n)$ matrix-vector products. This means that a useful perturbation for solving a linear system in backward error must be adaptive to the input. Interestingly, however, randomness is still essential: we show that any deterministic method that attains small backward error for all linear systems provably requires $Ω(n)$ matrix-vector products, resulting in the first separation between randomized and deterministic algorithms in a natural computational model for solving linear systems. Finally, we show that matrix structure can significantly affect backward error complexity. For example, we show a deterministic $O(1/ε)$ matrix-vector product algorithm for symmetric linear systems.