Re: [eigen] Accelerate RealSchur and EigenSolver |
[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]
Benchmark: http://i.imgur.com/13lJLyV.pngPatch: https://gist.github.com/Hi All,Thanks.
Motivated by a previous thread here (https://listengine.tuxfamily.org/lists.tuxfamily.org/eigen/ ), I was considering how to speed up EigenSolver for small- and medium-sized matrices. My focus was on optimizing RealSchur::2017/04/msg00008.html 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/ ), and some benchmark results on my machine are shown in the plot: http://i.imgur.com/13lJLyV.png2d14c0b6bb0b383c5518474d2f6ad1 41/revisions?diff=split . 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/ ) may need to be addressed first.2017/04/msg00021.html yixuan/ 2d14c0b6bb0b383c5518474d2f6ad1 41/revisions?diff=split
Mail converted by MHonArc 2.6.19+ | http://listengine.tuxfamily.org/ |