# Faster Eigenvalues with lower precision goal

I compute all eigenvalues of a large matrix, and I decide that the speed is more important than the precision. Then the question is, can I speed up Eigenvalues[] by setting a lower precision goal?

For example, consider a real symmetric random $100\times 100$ matrix:

 In[1]:=  A = # + Transpose[#] &@RandomReal[{-1, 1}, {100, 100}];


and compute

 In[2]:=  Do[Eigenvalues[A], {10}]; // AbsoluteTiming
Out[2]=  {0.019001,Null}


In real computation I may use a matrix much larger than $100\times 100$, and the computation would take much longer time than $0.019$ seconds. I want to speed up the computation. Can I set a lower precision goal, say 3, so that Eigenvalues[] runs fuster? So I tried

 In[3]:=  Do[Eigenvalues[SetPrecision[A, 3]], {10}]; // AbsoluteTiming
Out[3]=  {12.358707,Null}


The precision of the results is 3, but the computation took 12.36 seconds. This is not what I want.

Is there a clever way to speed up Eigenvalues[] by setting precision goal to be 3?

-
This about lowering bitwidth might be related, though no real solution is presented there. –  István Zachar Sep 6 '13 at 7:19

By default the computation will be done in machine precision, without precision tracking. I believe this is the fastest method you can get without some form of packing that places multiple values in a single machine float, which I know little about.

Once you use SetPrecision you are engaging the arbitrary precision engine with precision tracking, which is by nature much slower than machine precision calculations.

Please see this answer and the posts it links to for a better explanation of Mathematica's arbitrary precision engine and syntax. Quoting from the referenced tutorial:

Mathematica distinguishes two kinds of approximate real numbers: arbitrary-precision numbers, and machine-precision numbers or machine numbers. Arbitrary-precision numbers can contain any number of digits, and maintain information on their precision. Machine numbers, on the other hand, always contain the same number of digits, and maintain no information on their precision.

As discussed in more detail below, machine numbers work by making direct use of the numerical capabilities of your underlying computer system. As a result, computations with them can often be done more quickly. They are however much less flexible than arbitrary-precision numbers, and difficult numerical analysis can be needed to determine whether results obtained with them are correct.

-
Good point. Then SetPrecision is different from setting a precision goal. However, it is still reasonable to expect some parameters like recursion limit or precision goal that speed up. –  9527 Sep 6 '13 at 6:45
@9527 I believe that to have a precision goal the arbitrary precision engine will need to be active as without it precision is not tracked. As for tuning parameters of the algorithm itself I don't know. –  Mr.Wizard Sep 6 '13 at 6:48
@9527 I see now that the link in Nasser's answer has information about the Method option of Eigenvalues, which I admit I've never used. It is for the old version 5.2 however and I don't know what has changed since them. –  Mr.Wizard Sep 6 '13 at 7:04
I see. It seems the default method LAPACK is not an iterative method. So parameters like Tolerance or PrecisionGoal may not work. –  9527 Sep 6 '13 at 7:49

Update: re-run the tests for 10 times each, to get better average readings. (and also corrected a coding error)

Conclusion: Default and $MachinePrecision are fastest. (hard to see any difference, did 10 times per each). So if you want fast, just use Default. This page talks more about eigenvalue computation in Mathematica and the use of Lapack and under what condition etc.... code: a = RandomReal[{-1, 1}, {100, 100}]; b = c = a + Transpose[a]; r = First@Last@Reap@Do[ b = SetPrecision[b, i]; Sow[{i, First @ AbsoluteTiming @ Do[Eigenvalues[b], {10}]}], {i, 30} ]; Grid[Join[ {{"Precision", "Timing (sec)"}}, r, {{$MachinePrecision, b = SetPrecision[b, MachinePrecision];
First @ AbsoluteTiming @ Do[Eigenvalues[b], {10}]}},

{{Infinity, b = SetPrecision[b, Infinity];
First @ AbsoluteTiming @ Do[Eigenvalues[b], {10}] }},

{{Default, First @ AbsoluteTiming @ Do[Eigenvalues[c], {10}]}}
],

Frame -> All, Spacings -> {.5, .4}]

ListLinePlot[r, Mesh -> True, MeshStyle -> Red, Frame -> True,
FrameLabel -> {{"CPU (sec)", None},
{Precision, "eigenvalue CPU vs. Precision"}}, GridLines -> Automatic,
GridLinesStyle -> LightGray]


-
I couldn't resist making a bigger plot :) i.stack.imgur.com/fKckc.png –  Rahul Narain Sep 6 '13 at 5:06
Thanks for your nice codes. I got similar results using your code. Setting lower precision computes faster. The problem is, if I set A = RandomReal[{-1, 1}, {100, 100}];A = A + Transpose[A]; and compute Eigenvalues[A];//AbsoluteTiming without setting any precision, I got about 0.002 seconds. Once I set SetPrecision[A, $MachinePrecision], which seems to change nothing, but we would get about 1.4 seconds, according to your table. In fact, setting any precision reduces the speed dramatically. Also, whether to put SetPrecision command inside the loop does not affect the speed. – 9527 Sep 6 '13 at 5:16 @9527 when I do not use any SetPrecision on A, then CPU is just a little more than$MachinePrecision. Updated table above. –  Nasser Sep 6 '13 at 5:42
The entries in your table for $MachinePrecision and "Default" are not actually using machine-precision arithmetic, because A already has its precision set by the last time you ran A = SetPrecision[A, i]. You can check this using MachineNumberQ. To get a machine-precision version of A, you need to use N[A] instead. – Rahul Narain Sep 6 '13 at 6:01 Actually it turns out that SetPrecision[#, MachinePrecision] returns machine-precision numbers, while SetPrecision[#,$MachinePrecision] doesn't. –  Rahul Narain Sep 6 '13 at 6:06