2
$\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

Improve this question
$\endgroup$
2
  • $\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, 2017 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, 2017 at 23:49

1 Answer 1

Reset to default
3
$\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".

Improve this answer
$\endgroup$
2
  • $\begingroup$ I am not getting how matrix multiplication related to matrix inversion $\endgroup$
    – Complexity
    Nov 1, 2017 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, 2017 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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