Re: [eigen] Accelerate RealSchur and EigenSolver |

[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]

*To*: eigen@xxxxxxxxxxxxxxxxxxx*Subject*: Re: [eigen] Accelerate RealSchur and EigenSolver*From*: Ian Bell <ian.h.bell@xxxxxxxxx>*Date*: Thu, 20 Apr 2017 10:49:35 -0600*Dkim-signature*: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=8CqI2YjVoOvYesBe0IVT7A+st3yE98gYvMXJZaXkPlM=; b=mfz+2orAfoJBPFct/to7tvz9S8ZMDP4SMFS6GUiVoDWojMzliTv2RTbjGlp45dtaj5 lPLRUf96+7IkddkZ4HJe82rgobSPVrG1HKKBLKM+YtmoIFCZ26X8dEOPV39k0lZ6UQpc /tIqTC16K1+AhJ5f5dQ65K2HPo7h5WDOg+ECqpSxhVVHA5kVCfMt7wQyPrxlLT/teGEF iyjDXOTxKI82ri+7MEzPiJyx5XYvg6GsQgMvrDyfCGBNCtkgPB1gGsoCRLCEy/PgJtZ5 opJ1oIcX3anteOO1crdY7SWXULtk7YD2ztKkdZXAiZBiOeRxST+dWGQetKFjIs5oJzH2 JJLw==

I'm the one that filed the original note about the Hessenberg stuff, and I was able to get it "working", but not without some issues, that should probably be addressed here.

1) I did the decomposition with:schur.computeFromHessenberg(Abalanced, Eigen::MatrixXd::Zero(Abalanced.rows(), Abalanced.cols()), false);

const Eigen::MatrixXd &T = schur.matrixT();

Eigen::Index j = 0;

for (int i = 0; i < T.cols(); ++i) {

if (i+1 < T.cols()-1 && std::abs(T(i+1,i)) > DBL_EPSILON){

// Nope, this is a 2x2 block, keep moving

i += 1;

}

else{

// This is a 1x1 block, keep this (real) eigenvalue

roots(j) = T(i, i);

j++;

}

}

roots.conservativeResize(j-1);

On Mon, Apr 17, 2017 at 2:39 PM, Yixuan Qiu <yixuanq@xxxxxxxxx> wrote:

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

**References**:**[eigen] Accelerate RealSchur and EigenSolver***From:*Yixuan Qiu

**Messages sorted by:**[ date | thread ]- Prev by Date:
**[eigen] Matrix-matrix multiplication is slow compared to openBlas** - Next by Date:
**[eigen] Eigen lib 3.2.6** - Previous by thread:
**[eigen] Accelerate RealSchur and EigenSolver** - Next by thread:
**[eigen] Eigen lib 3.2.6**

Mail converted by MHonArc 2.6.19+ | http://listengine.tuxfamily.org/ |