Hi All,
Motivated by a previous thread here (
https://listengine.tuxfamily.org/lists.tuxfamily..org/eigen/2017/04/msg00008.html), I was considering how to speed up EigenSolver for small- and medium-sized matrices. My focus was on optimizing RealSchur::computeFromHessenberg(), since it is the major computation burden of EigenSolver::compute().
After some profiling and analysis, I find that the bottleneck of RealSchur is the QR iteration that repeatedly calls applyHouseholderOnTheLeft() and applyHouseholderOnTheRight() on some blocks of the matrix. These two functions come from the Householder transformation functions implemented in Householder/Householder.h.
And this is where we have room for optimization. In RealSchur, the size of Householder reflector is known to be 2 or 3, so we can write some specialized Householder functions to reduce the overhead in the generic implementation. I have created a patch for Householder.h (
https://gist.github.com/yixuan/2d14c0b6bb0b383c5518474d2f6ad141/revisions?diff=split), and some benchmark results on my machine are shown in the plot:
http://i.imgur.com/13lJLyV.png. The -O2 flag was used for all settings.
It can be seen that with AVX enabled, the patched version reduces a visible proportion of running time compared with the current implementation.
If you think this makes sense, I can then submit a PR to Eigen. But before that, the problem I mentioned previously (
https://listengine.tuxfamily.org/lists.tuxfamily.org/eigen/2017/04/msg00021.html) may need to be addressed first.
Thanks.
