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

6 次查看（过去 30 天）
Jason Nicholson
Jason Nicholson 2016-3-27
回答： Jason Nicholson 2016-3-30
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.

请先登录，再回答此问题。

采纳的回答

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

更多回答（2 个）

Adithya Addanki
Adithya Addanki 2016-3-29
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
  2 个评论
Jason Nicholson
Jason Nicholson 2016-3-29
编辑：Jason Nicholson 2016-3-29
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 2016-3-30
编辑：Jason Nicholson 2016-3-30
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.

请先登录，再进行评论。

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

类别

在 Help Center 和 File Exchange 中查找有关 Sparse Matrices 的更多信息

标签

产品

Community Treasure Hunt

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

Start Hunting!

Translated by