2
$\begingroup$

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$).

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – vonbrand
    Commented Feb 21, 2016 at 16:42
  • $\begingroup$ 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. $\endgroup$
    – thegentlecat
    Commented Feb 21, 2016 at 16:51

1 Answer 1

Reset to default
3
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ @DavidRicherby $nnz$ is standard notation, after the matlab function. It appears in papers of Lee and Sidford. $\endgroup$
    – Yuval Filmus
    Commented Feb 21, 2016 at 17:36
  • 4
    $\begingroup$ Oh, OK. Man, that's terrible notation. $\endgroup$
    – David Richerby
    Commented Feb 21, 2016 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.