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

2012/09/18 by Fliege, Joerg · 1 citation
Computer Science · #Coding theory and cryptography #Complexity and Algorithms in Graphs #Cryptography and Residue Arithmetic #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Numerical Analysis (math.NA)

paper · pdf · doi:10.48550/arxiv.1209.3995

openalex publication_date 2012/09/18 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

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 × n matrix A in time O(n²), with probability one. Note that we do not assume that A is symmetric.

Cited by

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

Related

• An Asynchronous Parallel Randomized Kaczmarz Algorithm
• On Smale's 17th problem over the reals
• Revisiting Asynchronous Linear Solvers: Provable Convergence Rate\n Through Randomization
• Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems
• Numerical Linear Algebra in Linear Space