Large Sparse Rectangular Over-determined Equation System (to reorder or to not reorder)

I have a sparse rectangular matrix A of size m x n. m > n always. I want to solve this system of equations in a least squares manor. I know that I can use the following:

   x = A\b

1. However, should I form (A'A) and run a reordering algorithm such as amd(), symamd(), or symrcm()?
2. What are the recommended steps to solve this type of equation system efficiently and as fast as possible?

Note I know basic linear algebra but the details of what I should be picking for algorithm or approach are beyond me for this type of problem. Any expert recommendations are welcomed.

Answer 1

[Jason Nicholson]

In spparms.m (version 2015b) there is the following note:

%   Solving rectangular matrices within \ and /:
%      The SuiteSparseQR QR-based solver uses COLAMD.

It seems the that backslash operator is already implementing a reordering. Therefore, a reordering before using the backslash operator is unnecessary.

Answer 2

[Adithya Addanki]

Hi Jason,

Please find the below links that may answer your questions:

http://www.mathworks.com/help/matlab/ref/mldivide.html#zmw57dd0e524586

If A is sparse then MATLAB uses QR solver. Following this information, if you refer to the link down below: http://www.mathworks.com/help/matlab/math/sparse-matrix-operations.html#f6-14516

This gives an overall view of what criteria should the matrix fall into for respective factorization methods adopted.

I hope this helps.

Thank you,

Adithya

[Jason Nicholson]

My conclusion from reading the material you linked is that there is no general reason to use a reordering for a sparse least squares problem. If all I care about is the vector x (rather than rank and condition number), then I should just use:

 x =A\b;

If I cared about checking rank of my problem, I would use:

 [c,R] = qr(A,b);
 x = R\c;

The 2nd method is what the backslash operator does but now I have the R matrix that I can examine for rank deficiency.

Is my understanding correct?

[Jason Nicholson]

After more reading from here, I think that my least squares problem would benefit from a column reordering process. However, I am not sure if MATLAB has the built in tools that I need. I can follow the logic of reducing the fill-in of A*A' by a column reordering listed in the link above. I don't think forming A*A' is advantageous. Instead, operating directly on A seems advantageous.

In summary, your answer has left me just as confused as when I started. I am a little more knowledgeable but still unsure even how to benchmark a reordering and then solving vs. just using the backslash operator. A "How to" or "Best Practices" on large scale least squares is what I think I am looking for.

Answer 3

[Jason Nicholson]

I found the video on SuiteSparse was very helpful. It talked about least square matrix problems and reordering. Tim Davis mentions that amd, colmmd, and metis for reordering of rectangular sparse matrices. Particularly interesting is the slide at about 34minutes shown below. Tim Davis talks about reordering for least squares problem before computing the sparse QR decomposition.

This gives me hope that my problem may benefit from reordering of the matrix A. I will post more after I figure out the commands in MATLAB to do the reordering and solving.