We know that general linear equations can be solved in $O(n^3)$ time with Gaussian elimination (where $n$ is the number of variables), and perhaps there are even faster algorithms. I have a question: for sparse linear equations, whose coefficient matrix has only $O(n)$ non-zero entries, is there an $O(n^2)$ exact algorithm to solve them? Tridiagonal systems can be solved in $O(n)$ time, but it can't be extended; Cholesky factorization is efficient, but can only be applied to positive definite matrices. So, does there exist a general algorithm?



You must log in to answer this question.

Browse other questions tagged .