But for general systems no such improvement is known!
Conjugate gradient [1]} runs in time \(\tilde{O}(\text{nnz}(A))\) , when \(\kappa (A) = \text{poly}\log n\) , whereas when \(\kappa (A) = \text{poly}(n)\)  this algorithm gives no improvement over the algorithm for general matrices.
