1
$\begingroup$

I know the best algorithm to solve a linear system in $\mathbb{R}$ with $n$ variables is Coppersmith-Winograd's algorithm, which has a complexity of $$ O\left(n^{2.376}\right). $$ How much easier is it to simply determine whether the same system has any solution?

More precisely, given a system of $m$ equations and $n$ unknowns, what is the complexity of establishing whether it has any solution?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Whether or not Coppersmith-Winograd is the "best" algorithm depends on your circumstances, of course. CW and algorithms like it are usually considered impractical due to high constant factors. Strassen's algorithm is more common in practice.

But since computational complexity is what you are interested in, CW was beaten quite recently.

As far as we know, calculating the determinant of a matrix, or eigenvalue estimation, or anything else that could be used to determine if a matrix is singular or not are at least as complex as matrix multiplication.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Does "As far as we know" mean that someone has given a reduction from matrix multiplication to determining whether it has a solution? Or is it just a commonly held "feeling"? $\endgroup$
    – j_random_hacker
    Commented Jan 17, 2019 at 13:33
  • $\begingroup$ Thanks for your answer. I'm also curious about what @j_random_hacker asked. Is there any reference for this claim? $\endgroup$
    – Gio
    Commented Jan 18, 2019 at 14:37
  • $\begingroup$ Yes. See Bunch & Hopcroft, "Triangular Factorization and Inversion by Fast Matrix Multiplication". apps.dtic.mil/dtic/tr/fulltext/u2/754790.pdf Essentially, if two matrices of order $n$ can be multiplied in $M(n) = \Omega(n^2)$ time, then triangular factorisation, inversion, and determinant calculation can be performed in $O(M(n))$ time. $\endgroup$
    – Pseudonym ♦
    Commented Jan 21, 2019 at 13:20

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.