2

I'm looking for a tool or library implementing a fast algorithm in C or JAVA for solving the equation $Ax=b$, where $A$ is a $N*N$ sparse matrix with $5$ non-zero diagonals $(-N,-1,0,1,N)$.

my problem is that $N$ is really big ($N$ can get up to $1-5e7$).

I now solve it in matlab but it is really slow so I'm looking for another methods in other languages to do it faster.

update:

Sorry for the lack of information, I'll update my question and try to clarify my problem.

I'm solving numerically the 2D laplace equation on a rectangular domain (the difficulty may arise from the rectangle dimensions - 1 mm*100 nm) with a mixed boundary conditions.

neumann boundary at left and down sides, dirichlet boundary at the upper side, and at the right side the derivative equal to some function.

by using the finite difference method I get the matrix A with 5 diagonals (each point is coupled with its 4 neighbors and itself).

I tried all the built-in functions in matlab for solving linear equations including "bicgstab" with no success (the solution explode).

the backslash operator with a matrix of N*N (where N=5e7) takes about 13 minutes give or take.

here is an example of the matrix where N=36. enter image description here

| improve this question | |
  • How are you solving it in Matlab? How long does it take in Matlab? How many gigabytes of memory does $A$ take up? – littleO Mar 16 '16 at 8:04
  • Have a look at hindawi.com/journals/mpe/2015/232456 It could be of interest. arxiv.org/pdf/1409.4802.pdf gives details about performance. – Claude Leibovici Mar 16 '16 at 8:06
  • In Matlab, I created a sparse matrix $A$ with $5 \times 10^7$ rows, $5 \times 10^7$ columns, and five nonzero diagonals, and I solved $Ax = b$ using the backslash operator in 20 seconds. Is that similar to what you're observing? – littleO Mar 16 '16 at 8:21
  • Depends how sparse it is. If the bandwidth is $O(\sqrt{N})$ then it would be tough indeed. – Svetoslav Mar 16 '16 at 8:52
  • 1
    Hi dor, and welcome on SR! Could you please edit your question and include some details on license/cost requirements (e.g. must it be available for free, must the license allow for commercial use, etc.)? The better you describe your requirements, the closer answers can match. For a guideline, be warmly welcomed to check with What is required for a question to contain "enough information"? Good luck, and fingers crossed! – Izzy♦ Mar 16 '16 at 11:07
-1

The notation is not clear to me, but assuming that the diagonal is zero, the first superdiagonal consists of copies of 1, the second superdiagonal consist of copies of N and that matrix is anti-symmetric, then the matrix A is singular for odd N.

If my original interpretation of the notation is correct, then the matrix B is also singular for odd N.

On the positive side, this is one of the nicest test matrices I have played with in a while.

A=@(N)toeplitz([0 1 N zeros(1,N-3)],[0 -1 -N zeros(1,N-3)]);

B=@(N)toeplitz([0 1 zeros(1,N-3) N],[0 -1 zeros(1,N-3) -N]);

In particular, the reduced row echelon form of B is most entertaining.

| improve this answer | |
  • 1
    And what exactly is the library you recommend? – Thomas Weller Mar 17 '16 at 17:15
  • 1
    @ThomasWeller: There is no recommendation to make. The matrices are singular for odd N. The OP wanted software that could handle any N. That software does not exist. What can be salvaged is a surprisingly nice class of test matrices A=A(N) for which A(2k) has a slowly growing condition number, while A(2k+1) is singular. – Carl Christian Mar 17 '16 at 20:14
  • 1
    I confess I have no clue what OP is talking about. Neither do I have a clue what you're talking about. This site is about software recommendations. If there's no software to recommend, because e.g. a mathematical answer is always 42, then I would say the question is not on-topic and should be closed because it does not show research effort. – Thomas Weller Mar 17 '16 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.