# A Randomized Parallel Algorithm with Run Time O(n2) for Solving an n × n System of Linear Equations

@article{Fliege2012ARP, title={A Randomized Parallel Algorithm with Run Time O(n2) for Solving an n × n System of Linear Equations}, author={J{\"o}rg Fliege}, journal={ArXiv}, year={2012}, volume={abs/1209.3995} }

In this note, following suggestions by Tao [2], we extend the randomized algorithm for linear equations over prime fields by Raghavendra [1] 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× n matrix A in time O(n), with probability one. Note that we do not assume that A is symmetric.

#### Topics from this paper

#### 2 Citations

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

- Mathematics, Computer Science
- ArXiv
- 2014

The authors' algorithms are quadratically faster than exhaustive search and almost quadrally faster than an algorithm for an inequality version of the problem by Impagliazzo, Lovett, Paturi and Schneider (arXiv:1401.5512). Expand

Learning from Large-Scale Distributed Health Data : An Approximate Logistic Regression Approach

- 2013

Research in healthcare is increasingly depending on the access to and analysis of large distributed datasets. Coupled with the exponential rate at which data is being generated, the need for parallel… Expand

#### References

SHOWING 1-2 OF 2 REFERENCES

A Randomized Algorithm for Linear Equations over Prime Fields

- Unpublished manuscript, available at http://www.eecs.berkeley.edu/~prasad/linsystems.pdf Last accessed
- 2012

Comment made at http://rjlipton.wordpress.com/2012/08/09/a-new-way-to-solve-linear-equations

- Last accessed
- 2012