CODEWITHSUNDEEP
matlablinear-regressionlinear-algebranumerical-methods
Carpetfizz
Carpetfizz

Reputation: 9149

MATLAB linear least squares with sparse b

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.

Upvotes: 1

Views: 204

Answers (1)

Pablo Jeken Rico
Pablo Jeken Rico

Reputation: 579

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!

Upvotes: 1

Related Questions