# Faster eigenvector routine for non-symmetric matrices with real eigensystem?

I have non-symmetric real-valued matrices with real-valued eigensystems. How to compute eigenvectors efficiently?

Using scipy.linalg.eig (which calls dgeev) is 3-4 times slower than scipy.linalg.eigh (=>dsyevd) and 2x slower than scipy.linalg.svd (=>gesdd), but neither SVD nor hermitian eigenvalue decomposition are appropriate here. I'm guessing the need to support complex valued storage is responsible for extra overhead. Is there a faster routine to use for matrices which have real-valued eigenvalue decomposition?

• Not sure if relevant, but these matrices are obtained from blocks of a covariance matrix like this – Yaroslav Bulatov Nov 13 '20 at 22:29
• You might try finding the real Schur decomposition of your matrix and looking to the diagonal for the eigenvalues, but I'm afraid that you'll find apparent complex eigenvalues (showing up as 2x2 blocks) due to round-off error. This would avoid storing complex matrices, but might not be any faster. – Brian Borchers Nov 14 '20 at 0:43
• Indeed, scipy.linalg.schur seems to be similar speed to scipy.linalg.eig – Yaroslav Bulatov Nov 14 '20 at 0:58
• Note that Schur decomposition routines can produce a complex or real result (In MATLAB, schur(A,'real') vs. schur(A,'complex') Using the 'real" option might make it a bit faster. – Brian Borchers Nov 14 '20 at 3:29
• The scipy routine has an option "output='real'" to do the real Schur decomposition. – Brian Borchers Nov 14 '20 at 3:43

Multiplying and dividing by $$(AC)^{-1}$$ you can rewrite $$D_1 = C^{-1}BAC (C^{-1}BAC+I)^{-1},$$ so your computation is equivalent to finding the eigenvalues $$\mu_i$$ of $$M = C^{-1}BAC$$ and then computing $$\lambda_i = \frac{\mu_i}{\mu_i + 1}$$ for each of them. Clearly the eigenvalues of $$M$$ are equal to those of $$BA$$. If $$A=LL^T$$ is a Cholesky factorization then those are equal to the eigenvalues of $$L^TBL$$, which is symmetric. Bingo.
For eigenvectors, the same computation shows that if $$v$$ is an eigenvector of $$L^TBL$$ then $$(L^TC)^{-1}v$$ is an eigenvector of $$M$$, and hence of $$D_1$$.
• @YaroslavBulatov You make a call to chol and one to eigh with this solution. – Federico Poloni Nov 17 '20 at 19:43