5
$\begingroup$

The cost of solving a linear system ("exactly") with Gauss Elimination and other similar methods with a few right hand side and where the matrix has no structure is $\mathcal{O}(N^3)$ where $N$ is the system size.

I am wondering about the lower bound for solving a linear system. An obvious lower bound is $\mathcal{\Omega}(N^2)$ (since the information content is $\mathcal{O}(N^2)$). Are there better lower bounds other than $\mathcal{\Omega}(N^2)$ for solving the linear system? Is there a way to prove that the lower bound of $\mathcal{\Omega}(N^2)$ can never be hit for a matrix with no special structure? (assume that we are solving a system with only one/few right hand side).

Also are there other algorithm which solve these system "exactly" whose cost is less than $\mathcal{O}(N^3)$? I am aware of Strassen algorithm which perform matrix multiplications in $\mathcal{O}(N^{\log_27})$. I assume this can be used to solve a linear system in $\mathcal{O}(N^{\log_27})$. (?)

(The system has no special structure. I am not worried about the stability and other numerical intricacies of the method as of now. I would appreciate if someone could point to some work done in this regard.)

Thanks

Improve this question
$\endgroup$
1
  • $\begingroup$ Would it not have dependence on condition number? $\endgroup$
    – Cuhrazatee
    Commented May 10, 2022 at 5:51

2 Answers 2

Reset to default
5
$\begingroup$

Any $O(N^t)$ algorithm for matrix multiplication yields a corresponding $O(N^t)$ algorithm for matrix inversion. There are not any non-trivial lower bounds for matrix multiplication. It is believed that there exist $O(N^{2 + \epsilon})$ algorithms for any $\epsilon > 0$, but as far as I know there are not believed to be $O(N^2)$ algorithms.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ The wikipedia article is very good: en.wikipedia.org/wiki/… $\endgroup$
    – Igor Rivin
    Commented Jan 19, 2011 at 23:28
  • $\begingroup$ Thanks David and Igor. Yes I am aware that solving a system and multiplication of two matrices have the same order of cost. lehigh.edu/~gi02/m242/08linstras.pdf. Anyway I will look if someone else answers this question or provides other useful insights before accepting the answer. $\endgroup$
    – user11000
    Commented Jan 20, 2011 at 1:58
  • $\begingroup$ Also, you should remember that this is for solving/multiplying under the assumption that arithmetic operation is unit cost. This is not true if your are trying to solve equations over $\mathbb{Q}$ or $\mathbb{Z}.$ $\endgroup$
    – Igor Rivin
    Commented Jan 20, 2011 at 4:57
5
$\begingroup$

Let me take this opportunity to make a comment that talks about the upper bound, not the lower.

Actually, let me remind you that it is a common false belief that Gaussian Elimination has $O(n^3)$ complexity. See the nice question with its answers here at cstheory

This misbelief happens because even though GE requires $O(n^3)$ arithmetic operations, if not done properly, there can be massive intermediate coefficient growth, which renders judging the true complexity of GE a difficult task.

You might also enjoy looking here at the near linear time algorithms for solving special linear systems (example for diagonally dominant matrices). For general, non-structured matrices, the situation is less clear.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ Gaussian Elimination over a black-box field $F$ requires $O(n^3)$ arithmetic operations, where an arithmetic operation is defined to be an access to the arithmetic oracle for $F$. In some fields, such as finite fields of fixed size, there is no coefficient growth so this estimate is exactly right. For fields such as $\mathbf R$ or $\mathbf C$, typically one approximates these with floating-point representations. In this case, Gauss Elimination uses $O(n^3)$ flops (but may commit some inaccuracy in the result). $\endgroup$
    – David Harris
    Commented Jan 20, 2011 at 14:30
  • $\begingroup$ Notice that the OP specifically asks for "exact" solution. $\endgroup$
    – Igor Rivin
    Commented Jan 21, 2011 at 15:34
  • $\begingroup$ Good point Igor; somehow I oversaw that in my haste. But I guess then one could argue that if even an inexact solution cannot be done better than in some time, say T, then getting an exact solution should be ever harder. $\endgroup$
    – Suvrit
    Commented Jan 21, 2011 at 17:19

You must log in to answer this question.