Questions about operation A\B

In MATLAB, A\B computes a least-squares solution to the system of equations A*x= B.. I'd like to know the specific method MATLAB employs—QR decomposition, SVD decomposition, or another approach—to achieve this.

A = [1 2 0; 0 4 3];
b = [8; 18];
x = A\b

I attempted a similar implementation in C++ using QR decomposition and validated it against 30 data sets. Surprisingly, 29 sets matched MATLAB perfectly, but one exhibited a significant difference. I'm puzzled because if the implementation were flawed, I'd expect inconsistencies across all data.

Answer 1

[Matt J]

See flowchart here,

https://www.mathworks.com/help/matlab/ref/mldivide.html#bt4jslc-6

[lucky]

Thank you for your answer. But I'm still confused. In my test, the dimensions of all A are [33,10], and the dimensions of all b are [33,3]. This means that A is not square, so QR solver will be used.

In C++, I also use QR solver for all tests. The results of 29 items in the test are consistent with matlab, but one item is different. I'm sure I used the same data, and when I decomposed it using SVD, this set of anomalous items came back, but the other items became anomalous again.

// QR
result = A.colPivHouseholderQr().solve(b);

// SVD
result = A.jacobiSvd(Eigen::ComputeThinU | Eigen::ComputeThinV).solve(b);

[Torsten]

There are cases where the solution x is not unique (namely if A has not full rank). But norm(A*x-b) should be equal for all least-squares solutions x.

MATLAB has "lsqminnorm" for these cases.

[lucky]

Yes, I've found it to be a illconditioned matrix indeed. Do you know how MATLAB handles illconditioned matrices in A\B? I aim to achieve the same results in C++.

[Matt J]

You cannot hope to duplicate the results of an ill-conditioned solution. The result can be sensitive to things beyond the user's control, like the CPU architecture.

[lucky]

Thank you for your help.

[Matt J]

You're welcome, but if your question has been resolved, please Accept-click the appropriate answer.

Answer 2

[John D'Errico]

The only time when there would/should ever be any significant difference is if the matrix is singular. And in that case, there would be infinitely many possible solutions, all of which are equally good, or bad.

In the singular case, different methods will result in different characteristic solutions, some of which may be more preferred than others, but the choice of your preference is often problem dependent.

As well, different methods will have different speeds. For example, any solution which depends on the SVD will often be considerably slower on large problems. Other solutions will generate zero coefficients on singular problems, whereas the pseudo-inverse based on the SVD will not tend to do so. (However, there are no circumstances where backslash uses the SVD.)

Again, problem dependent, and your needs and goals may differ on different problems.

[lucky]

Thank you so much for the reminder. Upon analysis, it appears that the abnormality indeed stems from a ill-conditioned matrix. Do you happen to know how MATLAB handles ill-conditioned matrices in A\B? Is it not through QR decomposition, and which method does it employ instead?