# Linear equation solving with special sparse coefficient matrix

Given a linear equation system of $n$ equations with unknowns $a_1,a_2,...,a_n\in [0,1]$, where the left hand side of each equation consists of not more than $k$ variables (so there are at least $n-k$ zero terms in each matrix row), what is the fastest way (in terms of time complexity) to solve such a system.

I know that simple equation-by-equation reduction will result in $\mathcal{O}(n^2)$ if I'm not mistaken. But is there a faster way of solving it (ideally linear in $n$, e.g. $\mathcal{O}(kn)$)? Because I'm new to the subject of computational linear algebra I have no idea wether or not this is possible.

EDIT: I should also say that either the coefficients in an equation are all the same and add up to zero (so they basically describe an arithmetic mean, for example $\frac{1}{2}a_1+\frac{1}{2}a_2-a_3=0$) OR the equation consists of a single variable and a value (e.g. $a_5=1$).

• A general bound for $n$ variables makes little sense here, you'd have to tell how many "equations are a single variable" (they can be used in one sweep to cut down the size of the system) and how many non-zero coefficients remain. – vonbrand Feb 21 '16 at 16:42
• The number single-variable-equations can be arbitrarily small, so assume the worst case of only $1$ of this kind. The number of non zero coefficients are therefore in $\mathcal{O}(kn)$. I should also say that I would strongly prefer direct algorithms instead of iterative approximations. – thegentlecat Feb 21 '16 at 16:51

There are iterative methods in which each iteration takes time $O(nnz)$, where $nnz$ is the number of non-zero entries. See for example Chapter 4 of Saad's lecture notes. For the state-of-the-art, consult Section 5 of Lee and Sidford (2013). For special types of matrices, see Lee, Peng and Spielman (2016).
• @DavidRicherby $nnz$ is standard notation, after the matlab function. It appears in papers of Lee and Sidford. – Yuval Filmus Feb 21 '16 at 17:36