Entrywise Approximation for Matrix Inversion and Linear Systems

This talk explores fast algorithms for entrywise approximation of matrix inverses and solutions to linear systems in diagonally dominant matrices—objects closely connected to random walk quantities such as hitting and escape probabilities in graphs. These quantities can vary exponentially with the matrix dimension; hence, under norm-based error guarantees, recovering small entries requires exponentially small error parameters, leading to prohibitively high running times. For example, a direct application of existing Laplacian solvers and fast matrix multiplication approaches requires $\Omega(mn^2)$ and $\Omega(n^{\omega+1})$ bit operations, respectively, where $m$ is the number of nonzero entries, $n$ is the matrix size, and $\omega$ is the matrix multiplication exponent. We study this problem in two distinct settings—when the input numbers are given in floating-point and fixed-point representations—and present algorithms with improved running times in both cases.