Lost on Matrix Inversion

Question

I try to implement some big matrix inversion. My system configuration is Hardware:- Memory: 62.8GiB, Processor: Intel Xeon(R)CPU E5-2670 v3 @2.30GHZ*48 To implement matrix inversion I am using universal Java matrix package. I want to invert a 31000*31000 dimension matrix. It is a Sparse matrix, most of the cell of this matrix is zero. I know that UJMP support sparse and dense matrix. So I am using it. But when I try to invert the matrix it cannot give any output also it cannot throw any error. The process runs for an infinite time without any output. As per my system configuration, there is enough memory space. Then why it did not give any output?

Secondly, If UJMP not working then can anyone suggest me any other sparse matrix package by which I can invert a sparse matrix.

Thirdly, I came to know that LAPACk is a standard software library for numerical linear algebra. I also came to know that BLAS (Basic Linear Algebra Subprograms) are routines that provide standard building blocks for performing basic vector and matrix operations. Are they compatible with Java? I am using Intellj Idea for Java coding.

Last, If LAPACK or BLAS are compatible with Java how could I configure them?

One more discussion Is GPU is helpful for my problem. Actually, my CPU has a huge capacity so I never think about GPU. So, as per my belief, it is not a good option to use GPU. Still, for a second opinion, I discuss this topic.

Answer 1

Normally when you invert a sparse matrix the inverse is dense. This imply to have enough memory to store the inverse, in your case the matrix is not so big for nowdays computers. In double precision (1 cell = 8 byte) you have $$ 31000 \times 31000 \times 8 \text{ byte } = 61504000000 \text{ byte } \approx 7.7 \text{ Gygabyte } $$

Another problem is the time invert a matrix, because it is a very heavy task. For example Matlab inv describe the function so:

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). For sparse inputs, inv(X) creates a sparse identity matrix and uses backslash, X\speye(size(X)).

Scipy linalg.inv recall the getry function of Lapack where:

Purpose =======

DGETRI computes the inverse of a matrix using the LU factorization computed by DGETRF.

This method inverts U and then computes inv(A) by solving the system inv(A)*L = inv(U) for inv(A).

These for show the idea under the inversion functions, for the library UJMP I found problem to acces to the documentation. Note that solve the linaer system related to the action of the inverse is cheaper than calculate the inverse.

However if we wait the time for the inversion we will obtain, in general, a result not so good from to use in numerical calculation. For detail see this question.

For these reason you must valuate what are your goal with the inverse, and if you really need the explicit inverse of the application of the inverse.

---

BLAS & LAPACK

In your case you need sparse BLAS or LAPACK. For an example, not in java, see this nist link.

In this wikipedia page there are some java libraries, I cite some (note I do not use them):

• Matrix Toolkit Java this the gitHub page note the follow

MTJ supports sparse matrix storage but does not provide solvers for sparse matrices. Have a look at Sparse Eigensolvers for Java or consider implementing your own and letting us know about it (e.g. by using the ARPACK backend which comes with netlib-java).

• Parallel Colt interesting project but some outdate

• Commons Apache in the java word Common Apache are a security of durable project. There is an interface for sparse matrix

• Efficient Java Matrix Library for dense case.

• jblas dense blas

---

GPU

Before use gpu I suggest to understand if you need the explicit inverse However gpu not always give you speed up, but is depends by your specif problem. Without information, i.e. in general, you can think to use the gpu for the linear algebra (for example iterative solver). Normally gpu is bounded by memory transfer and it has got less ram of cpu.

---

UPDATE Memory Test

I replicate your test of creation of a matrix in octave. My pc has go 16 GB of ram plus 32 GB of hard disk space dedicate to ram. I use Octave 4.0 from Ubuntu 16.04 repository.

I launch the command

A=zeros(31000)

The ram used before the command 1.4 GB and at the end 8.6 GB, the measures come from monitor of system. So we can consider in line with prediction.

In the middle what happened? In the middle there are one or two minutes of work (to be honest I did not use tic toc functions) by Octave. The memory usage varies during this time.

First the memory usage went to 9 GB quickly at as the same velocity it went to over the 16 GB of RAM and started to use the hard disc ram. After a while the memory ram has decreased and started the moving from hard disc memory to normal ram.

At the end the memory value was correct.

Note that Octave memory error message is like this:

error: memory exhausted or requested size too large for range of Octave's index type -- trying to return to prompt

Thing that you do not see (according with the comment).

I am not sure at 100% but knowing Octave I have an idea. Octave, similar Matlab, has got a memory management by value this is a general approach that it uses. In documentation are explained some techniques that it use to improve performance.

The ram behavior can be compatible with this explanation: during the call of function zeros the matrix of $31000 \times 31000$ elements are created a first time (inside the normal ram). Copied, for some motivation, to the variable A, saved some in normal ram and the surplus in hard disk ram. After the first matrix (the first copy) is deleted and start the migration from the hard disk ram to normal ram, maybe with some cache techniques.

In my opinion you did not found a memory outbound (no messagge) but you were waiting the memory transfers. Obviously you have got a lot of ram memory, but How many free? (I think you need a check about this, remember that in my pc with less memory it runs).

Different the case for UJMP, according with your question:

But when I try to invert the matrix it cannot give any output also it cannot throw any error.

If you arrived to this point the matrix was already created and, I think, you are wait for the inversion task, that is very very heavy (normally never use in numerical analysis).

Answer 2

Several points I want to mention (with an encouragement to other CompSci users that are more familiar with Java specifics to give additional, more Java related answers):

1. The solution of a system of linear equations and inversion of the matrix are two very different things. You almost never should explicitly invert the matrix. One should use one form of the direct or iterative methods to solve the system. Since your matrix is sparse, you should look for the one that takes sparsity into account.
2. UJMP does not seem like an awful choice (unfortunately, I personally never used Java for numerical computing). However, in the brief documentation there I was not able to find a sparse factorization or iterative-based method. For sure, if you construct your matrix as sparse and then use dense.inv(); on it, you should not expect to get a solution in any reasonable time. So, I certainly suggest to spend some time in the UJMP documentation and understand how you are supposed to do a solution to a sparse linear system with it.
3. You can use LAPACK and BLAS under Java and JavaNumerics should give plenty of information on how to use it and set it up.
4. Though direct solvers for sparse linear systems exist and can be efficient, in your case you might look into iterative solvers that would use multiple matrix-vector products (easy for sparse matrices) to converge to a solution.