Calculate Inverse of a Large Matrix Faster than Gaussian Elimination

[eddiechai2003]

Homework Statement

Is there an iterative method to calculate an inverse of a large matrix faster than a direct method (like Gaussian elimination, or inverse of LU, etc...) ?

Homework Equations

The Attempt at a Solution

I tried the Gauss-Seidel iterative method to inverse a matrix, but unfortunately, it takes longer than a direct method.

 

[Count Iblis]

You can also try Newton-Raphson. Consider first computing the reciprocal of a real number. Given y we want to compute x = 1/y. This amounts to solving the equation:

1/x - y = 0

Newton-Raphson then gives:

x_{n+1} = x_{n} - (1/x_{n} - y)/(-1/x_{n}^2) =

x_{n} + x_{n}[1 - y x_{n}]

This algorithm doesn't contain any divisions itself, so it is a true division algorithm. In case of matrices you can simply take y to be a matrix and start to iterate with some trial inverse x_{0}. Certain conditions have to be met for convergence. But it is clear that if the above algorithm converges, then that means that the second term tends to zero, so the term in the square brackets will then tend to zero, and thatmeans that x_{n} will apprach the inverse of y.

 

[eddiechai2003]

Hello Count Iblis,

I tried your solution, but it doesn't converge if I randomly choose the value of x_{0}.

What are the conditions for convergence? And how to 'find' the proper x_{0}?

Thanks.

 

[Count Iblis]

I found this article:

http://comet.lehman.cuny.edu/vpan/pdf/201.pdf

 

[minger]

There are many methods, as inverting matrices is the heart of any FEA solver. Looking through the ANSYS theory reference, aside from a direct solver there is a sparse direct solver which as you mentioned decomposes the matrix into an upper and lower triangular marix. The rest of mostly copy and pasted.

The frontal (or wavefront) solution procedure is discussed by Irons(17) and Melosh and Bamford(25). The number of equations which are active after any element has been processed during the solution procedure is called the wavefront at that point. The method used places a wavefront restriction on the problem definition, which depends upon the amount of memory available for a given problem. Many thousand DOFs (degrees of freedom) on the wavefront can be handled in memory on some currently available computers. Wavefront limits tend to be restrictive only for the analysis of arbitrary 3-D solids. In the wavefront procedure, the sequence in which the elements are processed in the solver (the element “order”) is crucial to minimize the size of the wavefront.
\sum^L_{j=1} K_{kj}u_j = F_k
To eliminate a typical equation, i=k, the equation is first normalized to:
\sum^L_{j=1} \frac{K_{ij}}{K_{ii}}u_j = \frac{F_i}{K_{ii}}
Then rewrite
\sum^L_{j=1} K_^*{ij}u_j = F^*_i
Where
K^*_{ij} = \frac{K_{ij}}{K_{ii}}
F^*_{ij} = \frac{F_{i}}{K_{ii}}
Where Kii is known as the pivot term.

There are also several iterative solvers. There are several conjugate gradient methods along with a few others. I would try and get some research on FEA solvers and you should find many ways to solve linear combinations of equation.