It depends on the matrix and no universally fast method exists!

In particular its eigenvalue characteristics and rank of the matrix or the pattern of non-zero elements. For sparse and patterned matrix which are usually seen in numerical solutions of PDEs (like FEM and FDM) there are well established methods which are developed over years and some of them are very efficient:

In general, if you want to invert a full matrix of size N X N you have to do O(n3) arithmetic operations (without applying any numerical tricks).

But we have methods for inverting sparse matrix of size N X N which are as efficient as O(N log N) like Thomas Algorithm (see below)

https://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm

If you want more in depth discussion on numerical method s for inverting a matrix, there numerical efficiency and palatalization see these four:

1- Yousef Saad web page:

https://www-users.cs.umn.edu/~saad/teaching.html

2- Works by Roland Freund (UC Dvais Department of Math)

https://www.math.ucdavis.edu/~freund/reprints.html

3- Book by Gene H. Golub of Stanford:

http://web.mit.edu/ehliu/Public/sclark/Golub%20G.H.,%20Van%20Loan%20C.F.-%20Matrix%20Computations.pdf

4- Publications of Z. Bai

https://scholar.google.com/citations?user=soiDQbQAAAAJ&hl=en

I am currently using MATLAB, and the inverse of a matrix say A can be done in two ways :

1. inv(A)

2. A\I ; where I is identity matrix of same size as of matrix A.

But these two procedure works for matrix size of size say 5000 x 5000 (approx)

If the size increases, solution time increases and memory as well. However, the inverse depends on how the matrix element populated, whether it is banded or not, for speed RAM configuration , etc. Even if all these condition meets, still the problem not solved i.e faster and accurate solution.

Dear,

Try to read this:

https://www.researchgate.net/post/Is_there_any_way_to_speed_up_inverse_of_large_matrix

Hi Majeed Ahmed Weli ,

I read most of the comments but mostly researchers talking about the size of matrix ranging between 50 x 50 to max 2000 x 2000. Also they are talking about the population of matrix element, sparse, banded, etc. But none of methodology mentioned about handling large matrix. Though question is about large matrix but answers doesn't converged to the solution of the problem.

Actually, large matrix in an algebric system is almost never inverted. Generally, iterative methods are largely used as they are faster.

However, you can check for possible (incomplete) decomposition methods, that is LU or ILU methods. You can find a lot of literature on such topic in the linear algebra field.

Thanks Filippo Maria Denaro

But i am looking for accurate solution because in the computation inverse of the matrix is to be done in several stages. If one uses iterative method, then it may lead to approximate solution. Accuracy of the solution might be questionable ?

Iterative methods provides asymptotically an exact solution. On the other hand, a numerical inversion has also problems depending on the condition number. You have to manage the methods for your goals. If the matrix is generate by a discretization of a PDE system you are introducing an approximation. So why do you need of an exact inverse instead of using an iterative method?

Approximation is there in discretization of PDE to form a matrix but the solution of the conventional problem are in good agreement to exact solution.

For example

P = A\B , where A and B are square matrix (conditioning is perfect) of size say 50 x 50,

So inverse of solution is very close to exact solution.

However, I am not sure whether any iterative methods can provide closer solution as compared to exact solution of Matrix size above 20000 X 20000.

I am currently solving the problem in MATLAB Software,

According to Mathworks:

inv : performs an LU decomposition of the input matrix (or an LDL decomposition if the input matrix is Hermitian). It then uses the results to form a linear system whose solution is the matrix inverse inv(X)

Therefore , inv in matlab is sufficient to handle matrix size above 20000 x 20000. But it takes time and memory. Here I am looking for faster response and accuracy can be compromised if it is closer to exact solution

It take long time and memory and it can be also an approximate process. To assess the accuracy you can check if the moltiplication with the original matrix provides an identity matrix.

Have a look here https://www-users.cs.umn.edu/~saad/

First of all the matrix is in sparse condition (banded as well), the link is not relevant to my question of handling large matrix. There are software's mentioned in the link https://www-users.cs.umn.edu/~saad/ like

" ILUPACK provides several multilevel ILU preconditioners for general real and complex matrices as well as real and complex symmetric (Hermitian) positive definite systems. ILUPACK exploits inverse-based ILUs which control the growth of the inverse triangular factors. It is an exhaustive package which incorporates the best methods in iterative solvers developed in recent years "

- Not specific to the present problem.

You have your problem and there is a large literature about the tools to work on it. If you are just asking for a single instruction that provides in matlab the inversion then continue to use it. But you are on the wrong way.

Sparse matrices are typical consequence of discretization of elliptic PDE. There is a large literature about that. There are many tool you can use. And HPC is the key to work faster.

We recently work on that Article SParC-LES: Enabling large eddy simulations with parallel spa...

You have to decide if your goal is the inversion of the matrix or gained the solution of your algebric system.

Filippo Maria Denaro : I never told i need the solution in matlab, my question is in a generalized way, how to handle large matrix inversion. I shared the current scenario of my problem. It can be done by some novel algorithm, or might be some literature's available which I may not be aware off. Nevertheless, Thanks for your suggestions.

Manish Kumar Dubey : You need to first define your goal. Why do you need to invert large matrix ? To solve some algebraic equation .. right ?

Or simply inverting a matrix for the sake of it ?

That's what Filippo Maria Denaro is trying to say to you. We "never" invert a large matrix numerically as it is computationally very expensive (O(n^3)). Instead, people solve the large matrix system by using iterative solver.

So, to give the answer of your question : There is no good way to handle large matrix inversion using direct inversion. Use iterative solvers instead.

It depends on the matrix and no universally fast method exists!

In particular its eigenvalue characteristics and rank of the matrix or the pattern of non-zero elements. For sparse and patterned matrix which are usually seen in numerical solutions of PDEs (like FEM and FDM) there are well established methods which are developed over years and some of them are very efficient:

In general, if you want to invert a full matrix of size N X N you have to do O(n3) arithmetic operations (without applying any numerical tricks).

But we have methods for inverting sparse matrix of size N X N which are as efficient as O(N log N) like Thomas Algorithm (see below)

https://en.wikipedia.org/wiki/Tridiagonal_matrix_algorithm

If you want more in depth discussion on numerical method s for inverting a matrix, there numerical efficiency and palatalization see these four:

1- Yousef Saad web page:

https://www-users.cs.umn.edu/~saad/teaching.html

2- Works by Roland Freund (UC Dvais Department of Math)

https://www.math.ucdavis.edu/~freund/reprints.html

3- Book by Gene H. Golub of Stanford:

http://web.mit.edu/ehliu/Public/sclark/Golub%20G.H.,%20Van%20Loan%20C.F.-%20Matrix%20Computations.pdf

4- Publications of Z. Bai

https://scholar.google.com/citations?user=soiDQbQAAAAJ&hl=en

This situation normally arise when you particularly solve a FEM problem with large mesh to test the convergence study. Secondly, if you solved a problem of circular/annular plate, cylindrical shell,etc which is normally very stiffer compared to beam or plate problem. Therefore it require higher number of elements to converge to a solution.

Manish Kumar Dubey : You don't invert a matrix for solving larger FEM problems. Krylov subspace solvers like GMRES or PBiCG are generally used. Refer some manual of available FEM softwares.

Thank you Kaveh Zamani

The information provided by you is very helpful in solving my problem.

Anant Diwakar : Exactly the similar idea shared by Kaveh Zamani .

If the objective is to solve an algebraic equation of a large FEM problem, normally we do not compute the inverse of the matrix explicitly. What is generally done is a LU factorization approach, Subspace methods, Multi-frontal methods or an iterative solution approach. There are various packages available that can handle matrix solutions very easily like SuperLU, MUMPS etc.

A survey of available direct solvers for sparse matrices can be found in the attached paper.

One of the best way to solve for inverse of a large matrix is using iterative method.

I'll recommend Maple Software.

The jth column of A^{-1} is the solution of Ax=e_j (the jth unit vector). I dont know of a general method better than solving N linear systems with the same coefficient matrix by normal methods. If you want A^{-1} to solve a linear system, its much better to solve it 1x with the real RHS. Also if A is sparse (e.g., from a local PDE discretization), A^{-1} will usually be full so memory requirements go way up. The general rule is "don't" - just solve Ax=b.

You can try it in MATLAB. Please see the example:

%%%% program

a= rand(1000,1000); % taking a 1000x1000 matrix

tic

b = inv(a);

toc

%%%%

%%Elapsed time is 0.114644 seconds.

Can you please tell me the size of matrix @ Manish Kumar Dubey .

Depending on where the data for your large matrix comes from, data imprecision can make accurate inversion of an inaccurate matrix seem foolish.