1

I'm trying to solve a llsq problem of the form Ax = b. I have some huge matrices where 

size(A) = 26181 13090
size(b) = 26181 1

b has sparsity ~26% and A is nearly dense. From the mldivide docs, it seems as though A\b runs a special algorithm if b is sparse.

However, currently, solving is taking upwards of 30 minutes (I've manually terminated after this time, so I don't know how long it actually takes).

Looking for suggestions on how to speed up this computation.

Carpetfizz
  • 8,707
  • 22
  • 85
  • 146
  • 1
    Is b actually sparse type or just a normal vector with a lot of zeros? – ThP Sep 27 '18 at 06:33
  • I believe ~8GB should be enough to solve these matrices as if they are dense. With nearly dense A you aren't saving meaningful amount of memory anyway. – Zizy Archer Sep 27 '18 at 06:35

1 Answers1

1

As I cannot comment yet, I will write some suggestions here.

  1. Sparsicity: In case that you declared your matrix A or vector b as sparse, undo it. Calculus on sparse systems is slower than dense calculus for matrices with a percentage of non 0 entries higher than ~20% (don't quote me here, just approx). This not just applies to solving but also for multiplications and all other things. Link to sparse questions, SO

  2. Backslash operator The backslash operator analyzes the matrix before solving it. Depending on the attributes, it uses a different solver (LU, Cholesky, ...). This way it is almost always the quickest and most comfortable solution. When the matrix is sparse, the backslash operator starts a different routine, checking different properties first. Check the schemes presented on the Matlab documentation for the backslash operator (bottom).

The only way to solve a large problem quicker than the backslash operator is using an iterative solver. These solvers (eg. CG - Conjugate Gradient Method) have a computational effort that is linearly dependent on the square root of the size of the matrix. They are extremely efficient on large matrix systems, but slower on small ones. They also don't provide an exact solution, but the residuals can be set very low, granting an almost right solution. The disadvantages of most iterative solvers is that they require your matrix to fulfill certain criteria. In the case of CG your matrix has to be positive definite and symmetric (as an example). I am afraid, that in your case probably non of these iterative solver will help :/

I hope that I could clarify this a bit and wish you good luck!

Pablo Jeken Rico
  • 569
  • 5
  • 22