15
$\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.

$\endgroup$
  • 1
    $\begingroup$ Solving over what? $\endgroup$ – joro Dec 8 '15 at 12:37
  • $\begingroup$ What is your question? $\endgroup$ – Alberto Montina Dec 8 '15 at 13:56
  • 1
    $\begingroup$ Are you solving over the reals, the rationals, integers or something else? $\endgroup$ – joro Dec 8 '15 at 13:58
  • $\begingroup$ solving over reals. $\endgroup$ – Alberto Montina Dec 8 '15 at 14:16
8
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Alberto Montina Dec 8 '15 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 Dec 8 '15 at 17:54
  • $\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$ – Alberto Montina Dec 8 '15 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 Dec 8 '15 at 18:02
  • $\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 Dec 12 '15 at 12:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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