0
$\begingroup$

I am trying to speed up my code, which many times finds a lowest eigenvalue of a Hermitian (symmetric, real) matrix. Using a small 2x2 matrix as an example, this works:

Energy = Compile[{{matrix, _Real, 2}}, Min[Re[Eigenvalues[matrix]]], {{Eigenvalues[_], _Complex, 1}}];
Energy[{{1, -2}, {-2, 3}}]
-0.236068

I have to use {{Eigenvalues[_], _Complex, 1}} here, otherwise Mathematica skips using the compiled function because of a type mismatch. Function Eigenvalues by default returns a vector of complex eigenvalues.

It should be in principle possible to compile a faster version, since I am only interested in the smallest eigenvalue, using Eigenvalues[matrix, -1], which only solves for one eigenvalue. However, I can't seem to make it to work:

Energy = Compile[{{matrix, _Real, 2}},Eigenvalues[matrix, -1][[1]], {{Eigenvalues[_], _Complex, 1}}];
Energy[{{1, -2}, {-2, 3}}]
During evaluation of CompiledFunction::cfex: Could not complete external evaluation at instruction 1; proceeding with uncompiled evaluation. >>
2 - Sqrt[5]

Where am I making a mistake? Also, is there a room for possible speedup if I somehow convince Mathematica, that I am only using Hermitian matrices and therefore expect only real eigenvalues?

$\endgroup$
1
$\begingroup$

Look at the output of CompilePrint[Energy]:

Needs["CompiledFunctionTools`"];
CompilePrint[Energy]


        1 argument
        1 Real register
        3 Tensor registers
        Underflow checking off
        Overflow checking off
        Integer overflow checking on
        RuntimeAttributes -> {}

        T(R2)0 = A1
        Result = R0

1   T(C1)1 = MainEvaluate[ Hold[Eigenvalues][ T(R2)0]]
2   T(R1)2 = Re[ T(C1)1]
3   R0 = MinRT[ T(R1)2]]
4   Return

The line MainEvaluate[ Hold[Eigenvalues][ T(R2)0]] means that the compiled program still needs to ask the main kernel to compute the Eigenvalues. This means that you gain nothing from compiling here at all. Looking at the list of compilable functions we confirm that Eigenvalues is not there.

Solution

The speediest way I know of finding eigenvalues in Mathematica is simply to give Eigenvalues a machine-number matrix:

Eigenvalues[N @ {{1, -2}, {-2, 3}}, {-1}]

This takes no measurable time on my laptop, while

AbsoluteTiming[Eigenvalues[{{1, -2}, {-2, 3}}, {-1}]]

shows 0.022 seconds. The reason is that Eigenvalues works differently for exact and numerical matrices. For a matrix with exact entries (like {{1, -2}, {-2, 3}}) Eigenvalues will interpolate the characteristic polynomial of the matrix and look for roots of that polynomial. When given a matrix with machine numbers on the other hand, Mathematica uses the very fast ARPACK library, which uses Arnoldi methods to find eigenvalues. I'm not too familiar with ARPACK, but I'm guessing it also specializes to the Lanczos algorithm when the input is Hermitian (see here for more info, e.g. Ctrl+F Eigenvalues)

Give this a go, and if you still need more speed, there are probably other places in the code that is slowing it down. Then we would need more details in order to help you ;)

$\endgroup$
  • $\begingroup$ I regard this as a definitive answer to the question that was asked. I will also raise the issue of what is the underlying goal? Is it to do some sort of quadratic optimization? If so, there might be alternative approaches. $\endgroup$ – Daniel Lichtblau Nov 27 '16 at 15:25
  • $\begingroup$ @DanielLichtblau, thanks for the comment! $\endgroup$ – Marius Ladegård Meyer Nov 27 '16 at 17:20
  • $\begingroup$ You are welcome. I just hope others read and upvote your response, but skip my remark (other than the OP). I'd hate to discourage others, on the off chance that there is more to be said. (I don't think there is, but I've been wrong any number of times on that score.) $\endgroup$ – Daniel Lichtblau Nov 27 '16 at 17:30
  • $\begingroup$ Thank you for a great answer. Indeed, Eigenvalues gains no speedup when compiled. I have a followup question, though. I am still using Compile for the construction of the matrix, whose eigenvalue I'm looking for, and I need to minimize the eigenvalue. This fails because of symbolic evaluation. Since I'm not compiling Eigenvalues, I can't use RuntimeOptions -> {"EvaluateSymbolically" -> False}. What can I do there? $\endgroup$ – lixpas Nov 28 '16 at 10:12
  • $\begingroup$ Extension of the minimal working example above: Matrix = Compile[{a}, {{a^2, -2}, {-2, 3}}]; Energy[a_] := Eigenvalues[Matrix[a], -1][[1]]; FindMinimum[Energy[a], {a, 1}] During evaluation of CompiledFunction::cfsa: Argument a at position 1 should be a machine-size real number. >> {4., {a -> 1.14195*10^-12}} $\endgroup$ – lixpas Nov 28 '16 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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