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

1 view (last 30 days)
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.

Accepted Answer

Jason Nicholson
Jason Nicholson on 30 Mar 2016
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.

More Answers (2)

Adithya Addanki
Adithya Addanki on 29 Mar 2016
Hi Jason,
Please find the below links that may answer your questions:
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
  2 Comments
Jason Nicholson
Jason Nicholson on 29 Mar 2016
Edited: Jason Nicholson on 29 Mar 2016
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
Jason Nicholson on 30 Mar 2016
Edited: Jason Nicholson on 30 Mar 2016
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.

Sign in to comment.


Jason Nicholson
Jason Nicholson on 30 Mar 2016
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.

Categories

Find more on Sparse Matrices in Help Center and File Exchange

Products

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!