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.


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

  • 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, 2016 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. Mar 16, 2016 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, 2016 at 8:21
  • Depends how sparse it is. If the bandwidth is $O(\sqrt{N})$ then it would be tough indeed.
    – Svetoslav
    Mar 16, 2016 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, 2016 at 11:07

1 Answer 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.

  • 1
    And what exactly is the library you recommend? Mar 17, 2016 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. Mar 17, 2016 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. Mar 17, 2016 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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