1
$\begingroup$

I am looking at a MATLAB code that times the backslash operator for several cases. I will list the cases below:

Note: all of these are for m = 5000

1) Z = randn(m,m); A = Z'*Z; b = randn(m,1); tic; x = A\b; toc; elapsed time = 1.0368

2) tic; x= A\b; toc; elapsed time = 1.0303

3) A2 = A; A2(m,1) = A2(m,1)/2; tic; x = A2\b; toc; elapsed time = 2.0361

Note that the times above were obtained years ago and today's MATLAB is significantly faster, but the relative trends are still observed.

FOr each case, I would like to know why the experiment was performed and why is the result the way it is. The first 2 are fairly simple and the elapsed times are approximately the same. But in #3, we see the time double. For #3, the lower left element of the matrix is divided by 2, but any idea why this would result in a two times slower computation?

$\endgroup$

closed as off-topic by Math1000, MCT, colormegone, user251257, Shailesh Apr 2 '16 at 0:57

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is not about mathematics, within the scope defined in the help center." – Math1000, MCT, colormegone, user251257, Shailesh
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ I don't know the internals of Matlab's backslash operator, but it may have something to do with the fact that A is symmetric while A2 is not. $\endgroup$ – Rahul Mar 30 '16 at 21:20
  • $\begingroup$ Hmm you're right. I need to look into what the backslash does. $\endgroup$ – nm17 Mar 30 '16 at 21:21
  • 1
    $\begingroup$ you would have a better chance on mathworks.com/matlabcentral/answers $\endgroup$ – user251257 Apr 1 '16 at 20:06
  • $\begingroup$ I strongly disagree with the closing votes: this question clearly belongs to MSE, since the observed timings are related to the numerical algorithms used, which fall into numerical analysis, which is indeed a field of mathematics. $\endgroup$ – Jean-Claude Arbaut Apr 1 '16 at 21:41
2
$\begingroup$

The algorithm used by the mldivide operator is descried here in Matlab's documentation: http://www.mathworks.com/help/matlab/ref/mldivide.html

The "general" backslash for square matrices would end up using LU decomposition, while for symmetric matrices the Cholesky decomposition is used instead. This decomposition, which is simply a simplification of LU for symmetric matrices, is also twice as fast, which explains your timings.

See https://en.wikipedia.org/wiki/Cholesky_decomposition#Computation

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.