# Eigenvalue algorithms for small matrices

I want to write a numerical library (in C++) that provides the eigenvalues of small matrices ($$3\times3$$$$20\times20$$) for my line of work.

I read a little bit of literature and the consensus is basically that for symmetric matrices using a householder transformation to get them into Hessenberg form, for which there exist efficient algorithms, is the most efficient way to get all the eigenvalues. Also, using a Schur decomposition should be feasible.

But what efficient algorithms are out there for non-symmetric small matrices? Are there better ways than just using QR? Or what can be specifically improved in a shifted QR algorithm to make it more efficient for small matrices? Are there algorithms (thinking about something like the power method) that are extremely efficient for small matrices when we're just interested in one eigenvalue?

I found Eigenvalues of Small Matrices question which strongly suggests that calculating the roots of the characteristic polynomial doesn't cut it even for small matrices (which was to be expected).

Unfortunately, I haven't found a post that deals with non-symmetric matrices.

• For symmetric matrices, you'd use a tridiagonal form, not a Hessenberg form, that is for non-symmetric problems. Commented Jul 31 at 15:11
• The QR algorithm (aka Francis's algorithm) with shifts is the standard approach. Commented Jul 31 at 15:59

You cannot beat the algorithms that are implemented in the widely used LAPACK library. You will spend weeks or months reading up on the best algorithms, implementing them, and optimizing them, and get something that is still less robust, less accurate, and slower than what LAPACK has. Use LAPACK.

• lapack and blas have significant overhead that absolutely is possible to beat for small matrices Commented Aug 1 at 17:18
• For $3\times 3$, I will believe this. For $20\times 20$, I'm doubtful. Commented Aug 1 at 19:57

I definitely agree that using LAPACK (reference Netlib or a vendor-optimized variant) is a good initial choice. You'll get numerically stable Housholder reductions inside the QR method with handling of tricky corner cases (non-symmetric eigenvectors are inherently unstable). But your question also suggests that you might want to look at other places. Unfortunately, Eigen does not have non-symmetric case but it would've been a great match for your C++ code with expression templates to optimization small matrix cases. If you choose to implement a simple power method then Eigen may be worth a look to get your code inlined for the small dimensions. Keep in mind that the power method likes well separated eigenvalues and tends to be poor in delivering orthogonal eigenvectors. Yousef Saad books are always a good place to start (disregard "large problems" in the title and focus on the numerical issues to avoid).

Correction: I missed the non-symmetric eigensolvers in Eigen 3.4: real and complex. They're based on JAMA which in turn results in EISPACK. This may mean slower code for large matrices but may do just fine for the smaller ones.

New contributor
luszczek is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
• Can you please elaborate waht you mean by "Eigen does not have non-symmetric case"? AFAIK, libeigen finds eigenvalues for unsymmetric matrices, too. Commented 2 days ago
• Yes, you're correct. I took a second look at their "catalogue" page and, even though some information is missing, clicking through reveals that Eigen 3.4 can compute eigenvalues of non-symmetric matrices in both real and complex domains. Commented 12 hours ago