21
$\begingroup$

Solving linear equations can be reduced to a matrix-inversion problem, implying that the time complexity of the former problem is not greater than the time complexity of the latter. Conversely, given a solver of $N$ linear equations and $N$ unknown variables with computational cost $F(N)$, there is a trivial implementation of matrix inversion using the linear solver with overall computational cost equal to $N F(N)$.

However, the resulting algorithm is not optimal for matrix inversion. Indeed, the time complexity of linear solvers is not smaller than $N^2$, whereas the time complexity of matrix inversion is not bigger than $N^{2.375}$, as implied by the Coppersmith–Winograd algorithm.

Thus, my question is as follows. Given any solver of linear equations, is there some algorithm for inverting matrices that uses the linear solver and with the same time cost up to some constant? In other words, does a linear-solver with time cost $N^\alpha$ induce a matrix-inversion algorithm with cost $N^\alpha$? This question comes from the observation that the most efficient known linear solvers come from matrix-inversion algorithms.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Solving over what? $\endgroup$
    – joro
    Commented Dec 8, 2015 at 12:37
  • $\begingroup$ What is your question? $\endgroup$
    – Alm
    Commented Dec 8, 2015 at 13:56
  • 1
    $\begingroup$ Are you solving over the reals, the rationals, integers or something else? $\endgroup$
    – joro
    Commented Dec 8, 2015 at 13:58
  • 2
    $\begingroup$ solving over reals. $\endgroup$
    – Alm
    Commented Dec 8, 2015 at 14:16

2 Answers 2

Reset to default
16
$\begingroup$

A linear solver with optimal complexity $N^2$ will have to be applied $N$ times to find the entire inverse of the $N\times N$ real matrix $A$, solving $Ax=b$ for $N$ basis vectors $b$. This is a widely used technique, see for example Matrix Inversion Using Cholesky Decomposition, because it has modest storage requirements, in particular if $A$ is sparse. The Coppersmith–Winograd algorithm offers a smaller computational cost of order $N^{2.3}$, but this improvement over the $N^3$ cost by matrix inversion is only reached for values of $N$ that are prohibitively large with respect to storage requirements. An alternative to linear solvers with a $N^{2.8}$ computational cost, the Strassen algorithm, is an improvement for $N>1000$, which is also much larger than in typical applications.

So I would think the bottom line is, yes, linear solvers are computationally more expensive for matrix inversion than the best direct methods, but this is only felt for very large values of $N$, while for moderate $N\lesssim 1000$ the linear solvers are faster and have a much reduced storage requirement than direct matrix inversion.

Improve this answer
$\endgroup$
5
  • $\begingroup$ But Cholesky decomposition does not have $N^2$ complexity when applied for solving linear equations. The computational time of solving linear equations or inverting matrices has the same identical power law by using the decomposition. This puzzles me. I am wondering if the two problems are essentially equivalent in the end. $\endgroup$
    – Alm
    Commented Dec 8, 2015 at 15:46
  • $\begingroup$ @AlbertoMontina --- Cholesky decomposition solves the first linear equation with $N^3$ cost, the remaining $(N-1)$ linear equations each with $N^2$ cost (because the factorization can be reused), so the total cost for matrix inversion via Cholesky decomposition is order $N^3$, as worked out in the paper to which I have linked --- or have I misunderstood your question? $\endgroup$
    – Carlo Beenakker
    Commented Dec 8, 2015 at 17:54
  • 1
    $\begingroup$ I just commented your first line "A linear solver with optimal complexity $N^2$...". It seemed that you were referring to Cholesky decomposition, which is not optimal. I find curious that an algorithm for solving linear equations has the same computational cost when applied for inverting a matrix. In the case of the decomposition, this comes because you can use it multiple times, as you said. But is there some smart way that uses the linear solver as a black-box for solving efficiently the inversion. $\endgroup$
    – Alm
    Commented Dec 8, 2015 at 17:59
  • 1
    $\begingroup$ my phrasing was not accurate, the complexity $N^2$ is after the factorization (which has to be done only once) $\endgroup$
    – Carlo Beenakker
    Commented Dec 8, 2015 at 18:02
  • 1
    $\begingroup$ It sounds like OP is interested in the theoretical big-O-complexity problem. It is true that these algorithms are not usable in practice, but I believe that the question still stand on its own (and it is a good MO question). $\endgroup$
    – Federico Poloni
    Commented Dec 12, 2015 at 12:18
3
$\begingroup$

It depends what you mean by "solver of linear equations".

If by "solver of linear equations" you mean it can also compute a basis for the kernel of a matrix, then they are indeed equivalent. The equivalence can be shown in two steps:

  1. Computing kernel is equivalent to matrix multiplication. Theorem 16.18 in Bürgisser-Clausen-Shokrollahi.

  2. Matrix multiplication is equivalent to matrix inversion, see, e.g., Prop 16.6 in Bürgisser-Clausen-Shokrollahi (ibid.).

On the other hand, if you mean "Given $A,b$, it outputs an $x$ such that $Ax=b$, if one exists, and otherwise says NO", then the equivalence between this and matrix inversion (equivalently, from a complexity perspective, matrix multiplication) I believe is an open question, e.g. see the last slide here.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .