Calculation of the inverse matrix - Number of operations

[mathmari]

Hey!

Let A be a regular ($n\times n$)-Matrix, for which the Gauss algorithm is possible.

If we choose as the right side $b$ the unit vectors $$e^{(1)}=(1, 0, \ldots , 0)^T, \ldots , e^{(n)}=(0, \ldots , 0, 1 )^T$$ and calculate the corresponding solutions $x^{(1)}, \ldots , x^{(n)}$ then the inverse matrix is $A^{-1}=[x^{(1)}, \ldots , x^{(n)}]$.

We can calculate the inverse with $n^3+O(n^2)$ operations. (1 operation = 1 multiplication or division)
If we calculate the solutions $x^{(1)}, \ldots , x^{(n)}$ with the using the LU-decomposition we get $\frac{4}{3}n^3+O(n^2)$ operations, or not?

It is because we apply the the Gauss algorithm which requires $\frac{1}{3}n^3+O(n^2)$ operations, right?

How do we get $n^3+O(n^2)$ ?

Do we have to use an other algorithm here?

 

[I like Serena]

Hey!

Let A be a regular ($n\times n$)-Matrix, for which the Gauss algorithm is possible.

If we choose as the right side $b$ the unit vectors $$e^{(1)}=(1, 0, \ldots , 0)^T, \ldots , e^{(n)}=(0, \ldots , 0, 1 )^T$$ and calculate the corresponding solutions $x^{(1)}, \ldots , x^{(n)}$ then the inverse matrix is $A^{-1}=[x^{(1)}, \ldots , x^{(n)}]$.

We can calculate the inverse with $n^3+O(n^2)$ operations. (1 operation = 1 multiplication or division)
If we calculate the solutions $x^{(1)}, \ldots , x^{(n)}$ with the using the LU-decomposition we get $\frac{4}{3}n^3+O(n^2)$ operations, or not?

Hey mathmari! (Smile)

LU-decomposition is listed here as $\frac 23 n^3 +O(n^2)$, while QR-decomposition with Householder reflections (for numerical stability) is $\frac 43n^3+O(n^2)$. (Nerd)

It is because we apply the the Gauss algorithm which requires $\frac{1}{3}n^3+O(n^2)$ operations, right?

How do we get $n^3+O(n^2)$ ?

Do we have to use an other algorithm here?

That's indeed to get the matrix in row echelon form.
Afterwards we still need to solve it for each of the n unit vectors, which takes $\frac 12 n^3 + O(n^2)$ extra if I'm no mistaken. (Thinking)

 

[S.G. Janssens]

We can calculate the inverse with $n^3+O(n^2)$ operations. (1 operation = 1 multiplication or division)

When comparing operation counts for different methods and from different references, it is perhaps useful (but maybe already known to all participating, in which case I apologize for stating the obvious) that older references sometimes neglect addition (which includes subtraction) because multiplication (which includes division) used to be the determining factor, as it was much slower.

I learned that inversion using Gaussian elimination with back-substitution costs $n^3$ multiplications (exactly) and $n^3 + O(n^2)$ additions. Interestingly, for Gauss-Jordan the count is precisely the same.

(Elimination with back-substitution for one system costs $\frac{n^3}{2} + O(n^2)$ multiplications and $\frac{n^3}{2} + O(n)$ (no typo) additions.)