1
$\begingroup$

What is the fastest way to compute the inverse of the matrix, whose entries are from file $\mathbb{R}$ (set of real numbers)?

One way to calculate the inverse is using the gaussian elimination method. In this method append more columns(double the number of columns ) to the input matrix and then we try to make last row zero except the last column entry and second last and so on until we get a identity matrix and then we stop and we have a inverse of input matrix. Consider the cost of one multiplication, division and addition is constant. Then total $O(n^2)$ many operations is needed.

Is there any algorithm which is faster than the above algorithm? Please give the algorithm or reference to the algorithm

$\endgroup$
  • $\begingroup$ Beyond wikipedias method collection (and links, you can try and account for memory hierarchy and other aspects of machine architecture - neither of which looks core computer science. $\endgroup$ – greybeard Nov 1 '17 at 13:24
  • 1
    $\begingroup$ Also worth pointing out the standard disclaimer: If you're trying to solve a real-world problem, be aware that inverting a matrix (larger than, say, 4x4) is usually not a good idea. $\endgroup$ – Pseudonym Nov 1 '17 at 23:49
2
$\begingroup$

Gaussian elimination requires $O(n^3)$ operations, not $O(n^2)$.

In general, matrix inversion has the same exponent as matrix multiplication (any matrix multiplication algorithm faster than $O(n^3)$ gives a matrix inversion algorithm faster than $O(n^3)$), see for example P.Burgisser, M.Clausen, M.A.Shokrollahi "Algebraic complexity theory", Chapter 16 "Problems related to matrix multiplication".

$\endgroup$
  • $\begingroup$ I am not getting how matrix multiplication related to matrix inversion $\endgroup$ – Complexity Nov 1 '17 at 14:03
  • 2
    $\begingroup$ Matrix inversion is by definition related to matrix multiplication. But from algorithmic point of view, you can calculate matrix inversion with blockwise inversion method, so for every $\epsilon$ for which exists an matrix multiplication algorithm working in $O(n^{2+\epsilon})$ time there is also a matrix inversion algorithm with same complexity. $\endgroup$ – Szymon Stankiewicz Nov 1 '17 at 20:13

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.