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 $A x = 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.
 Publication:

arXiv eprints
 Pub Date:
 September 2012
 arXiv:
 arXiv:1209.3995
 Bibcode:
 2012arXiv1209.3995F
 Keywords:

 Mathematics  Numerical Analysis;
 Computer Science  Data Structures and Algorithms