Sparse Linear System (Linear System)

From Algorithm Wiki
Jump to navigation Jump to search


In this case, we restrict $A$ to be sparse (i.e. $A$ only has $O(n)$ nonzero entries).

Related Problems

Generalizations: General Linear System

Related: Positive Definite, Hermitian Matrix, Non-Definite, Symmetric Matrix, Toeplitz Matrix, Vandermonde Matrix


$n$: number of variables and number of equations

$m$: number of nonzero entries in matrix

$k$: ratio between largest and smallest eigenvalues

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Harrow (Quantum) 2009 $O(k^{2}*\log n)$ $O(\log n)$ Exact Quantum Time & Space