patternMinor
Fastest algorithm for matrix inversion
Viewed 0 times
algorithmforfastestinversionmatrix
Problem
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
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
Solution
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".
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".
Context
StackExchange Computer Science Q#83289, answer score: 4
Revisions (0)
No revisions yet.