A Randomized Parallel Algorithm with Run Time $O(n^2)$ for Solving an $n\times n$ System of Linear Equations

Abstract

In this note, following suggestions by Tao, we extend the randomized algorithm for linear equations over prime fields by Raghavendra to a randomized algorithm for linear equations over the reals. We also show that the algorithm can be parallelized to solve a system of linear equations $Ax=b$ with a regular $n\times n$ matrix $A$ in time $O(n^2)$, with probability one. Note that we do not assume that $A$ is symmetric.

Cited by in corpus (1)

• Exact Algorithms for 0-1 Integer Programs with Linear Equality Constraints