This forum has been archived. All content is frozen. Please use KDE Discuss instead.

EigenSolver Performance

Tags: None
(comma "," separated)
twood
Registered Member
Posts
17
Karma
0

EigenSolver Performance

Mon Mar 18, 2013 2:58 pm
Hello,
I have a project that involves taking the matrix exponential of both 3x3 and 6x6 matrices in a loop. These matrices are real, non-symmetric, but have fairly good condition numbers. I was hence looking for a faster way of computing the matrix exponential, and am willing to trade off some accuracy.

In Matlab calculating the matrix exponential via eigenvalues/vectors is much faster than via the Pade approximation (see expmdemo3). The calculation is:
Code: Select all
[V,D] = eig(A);
E = V * diag(exp(diag(D))) / V;

I translated this to Eigen in the following way:
Code: Select all
template<typename MatrixType>
inline const MatrixType FastExp(const MatrixType& A)
{
   typedef EigenSolver<MatrixType> solver;
   solver s(A);
   const typename solver::EigenvectorsType &vecs = (s.eigenvectors());
   typename solver::EigenvectorsType vals;
   vals.diagonal() = s.eigenvalues().array().exp();
   return (vecs * (vecs.transpose().partialPivLu().solve(vals)).transpose()).real();
}

Unfortunately, performance is the opposite way round to Matlab, with this method being about 3 times slower than via the MatrixExponential in unsupported. If I profile the function most of the time is spent in the EigenSolver computation. I've tried reducing the maxIterations, but the smallest number that gives meaningful results (5) makes no difference to the runtime.

Is there something I'm doing wrong here? Or is the performance of EigenSolver really not great for small matrices?
User avatar
ggael
Moderator
Posts
3447
Karma
19
OS

Re: EigenSolver Performance

Mon Mar 18, 2013 9:43 pm
Make sure your compiled with optimizations enabled. And how does it compare to MatLab? It might be the case that Pade approximation is slow with MatLab because MatLab is not a compiled language, while the eigen-decomposition solution makes call to optimized Intel MKL.
twood
Registered Member
Posts
17
Karma
0

Re: EigenSolver Performance

Wed Mar 20, 2013 2:02 pm
Thanks Gael. With optimisations enabled with Eigen, I get the following performance for this (including generating random matrices inside the loop):

Matlab, Pade, 3x3 = 56 us, 6x6 =35 us
Matlab, Eigenvectors, 3x3 = 21 us, 6x6 23 us

Eigen, Pade, 3x3 = 0.7 us, 2 us
Eigen, Eigenvectors, 3x3 = 2.5 us, 6x6 17 us

So in all cases Eigen is faster, and I agree that Matlab's interpreted nature is likely slowing down their Pade implementation (the expm file is pure Matlab). Otherwise I can't explain the fact that expm is slower for 3x3 matrices than 6x6!

Unfortunately this also suggest that I can't get my exponentials any faster, which is a shame.
User avatar
ggael
Moderator
Posts
3447
Karma
19
OS

Re: EigenSolver Performance

Wed Mar 20, 2013 4:49 pm
Yes, actually it makes sense to me that Pade approximations are faster for this task, and the results sounds pretty fast already. anyway, have you profiled this version to identify the bottleneck?

Also, don't forget your machine has more than 1 core... If you're looking for a 2x-4x speedup, multi-threading your application might be enough.
twood
Registered Member
Posts
17
Karma
0

Re: EigenSolver Performance

Thu Mar 21, 2013 9:22 pm
Yes, I have profiled the program and unfortunately there are two bottlenecks - the matrix exponentials and a matrix solve.

It is already multi-threaded, and running on a 24 core machine ;)


Bookmarks



Who is online

Registered users: Bing [Bot], Google [Bot], Sogou [Bot]