Hi Shahram,

are you sure you need to compute the inverse of the matrix. In case you only need to solve a linear system associated with matrix A the CPU time is lower.

Is it possible to take advantage of the structure of the matrix?

You can use LU decomposition and then you will have to solve a set of linear equations. 

First of all, 500x500 is not really a "big" matrix. It sounds like you were using global approximation with RBF, which, in general leads to a dense and ill-conditioned system matrix making it difficult to invert. This is a well known issue and here is what you can do about it:

(1) You can use Morre-Penrose pseudoinverse to invert the matrix. See [1]

(2). If you are using Gaussian RBF ( or other RBF), you can replace them with polyharmonic (PHS) radial basis functions. The condition number will be significantly reduced and you could easily invert the A matrix. Changing from Gaussian RBF to PHS is likely to reduce the accuracy which can be further improved by adding polynomials.[2]

(3) You can see our recent paper [3][4], where I have used a Hybrid-Gaussian cubic RBF to deal with the ill-conditioning problem in the global RBF approximations. You can also see the LOOCV approach to optimize the shape parameter.

-------------------------------------

[1] http://link.springer.com/article/10.1007/s40819-016-0272-6

[2] https://amath.colorado.edu/sites/default/files/2014/09/1925991153/Paper_04.pdf

[3] https://arxiv.org/pdf/1512.07584v3.pdf

[4] https://arxiv.org/pdf/1606.03258v3.pdf