# High computational time in using backslash for soving sparse matrix

I built a sparse matrix A at each step as follows:

% 1 < DX < 120000

A = sparse(i,j,s,DX,DX,6*DX)

b = (1, DX)


The problem that I am dealing with is a discretization problem. I have maximum 120000 nodes. Each of these nodes have special characters and I choose only the ones that meet a (previously) defined criteria. The number of these chosen ones is DX and is completely dependent on the physical process.

I am using backslash in x = A\b. But as the size of A could become quite big, the computational time rises drastically (more than 10e5 time steps have DX > 6e4). As far as I know, backslash operation is already well optimized in MATLAB but I would like to know:

1. Would it make sense to use codegen and convert the code to C?

2. Does any one know an alternative method instead of backslash, so that the computational time decreases (maybe an iterative method?)?

• Welcome to SciComp.SE! The obvious question is "implement what?" -- could you add some more details about the problem you are trying solve (PDE (presumably), specific discretization,...); in particular, what is DX? It is very unusual that the size of the matrix changes between time steps, so maybe your modelling is simply wrong. – Christian Clason Jul 16 '15 at 11:56
• The answer to your first question is an emphatic No; the heavy lifting behind backslash is not implemented in Matlab but in one of the (FORTRAN-based and hand-optimized) numerical linear algebra libraries bundled with Matlab. – Christian Clason Jul 16 '15 at 11:58
• Thank you Christian for the answer. The problem that I am dealing is a sort of discretization problem. I have maximum 120000 nodes and each of these nodes are having special charachters and I choose only the ones that meet my criteria. the number of these chosen ones is DX and is completely dependent on the physical process. By saying implement a better idea, I meant clearly an alternative method instead of backslash, so that the compuattional time decreases (maybe an iterative method) – John13 Jul 16 '15 at 12:10
• @John13 Then there's not much that one could say except "try gmres or bicgstab, see if it works (better)". An actually useful answer would be "here's how you can avoid such nasty matrices", but this is impossible without more details about your problem. – Christian Clason Jul 16 '15 at 13:07
• I agree with the general consensus that more details need to be added. Mentioning "a discretization problem" is too vague to give advice about linear solvers. – Geoff Oxberry Jul 17 '15 at 1:29

You can try using one of the iterative solvers that MATLAB provides, as x = A\b works well for many systems, you can run into memory issues causing slowdowns.

Alternately, MATLAB has a number of built in functions for iteratively solving Ax=b for sparse matrices, such as pcq(), bigcg(), cgs(), etc.

Since (I assume) your matrix size and possibly its structure changes from time step to time step you can't, for example, compute an efficient ordering once and then reuse that with e.g. the chol() function to compute a solution.

The backslash operator does incur some slight overhead determining if your matrix is dense/sparse, symmetric, etc. If, for example, your matrix is symmetric, you might improve performance slightly by computing an ordering (e.g. symamd()) and then using that with chol().

If I understand right, you are computing for 1e6 time steps? I don't suppose there is an alternate time integration algorithm you can use that would require fewer time steps?

• Thank you Bill for the answer. you are right, the structure does not changed and I will try to implement the method you explained. Regarding the time steps, I have 2e6 time steps, more or less, in 1e6 of them DX is too big. The time steps is not something that I can modify. They are dependent on the process and the process is already proved! – John13 Jul 17 '15 at 9:53