Linear equation solving has also been studied in the case of sparse linear systems. We know of \(O(\text{nnz}(A)n)\)  time algorithms for solving a linear system \((A \in \mathbb {R}^{O(n) \times n}, b)\)  where \(\text{nnz}(A)\)  denotes the number of non-zero entries of \(A\) , that use Conjugate Gradient Descent [1]}, so that when the sparsity of \(A\)  is \(\tilde{O}(n)\) , these algorithms run in time \(\tilde{O}(n^2)\) . Our reduction (discussed above), preserves the sparsity of the original matrix \(A\)  and thus reduces the exact problem over sparse linear systems to the approximate problem over sparse ones. We start with an analogous conjecture to Conjecture REF  for finding the rank of a sparse matrix:
