Recently, there has been a lot of progress on the algorithmic front for finding approximate solutions to restricted classes of linear systems \((A,b)\) . In a breakthrough work, Spielman and Teng [1]} obtained \(\tilde{O}(\text{nnz}(A)\log (1/{\varepsilon }(n)))\) -time algorithms for finding \({\varepsilon }(n)\) -approximate solution to Laplacian systems and Strongly Diagonally Dominant (SDD) systems. This result was followed up by algorithms for more general classes of linear systems such as Connection Laplacians [2]} and Directed Laplacian systems [3]}. This raised the hope that such approximation algorithms could be obtained for more general classes of matrices such as truss stiffness matrices and total variation matrices. Kyng and Zhang [4]} showed that such algorithms for these slightly more general classes would imply approximation algorithms for general linear systems. Therefore, by composing our reduction with theirs, one immediate corollary we get is that solving approximately for these classes of restricted linear systems is as hard as the rank-finding problem.
