I have a 3x3 covariance matrix (so, real, symmetric, dense, 3x3), I would like it's principal eigenvector, and speed is a concern. Is there a fast algorithm for this specific problem? I've seen algorithms for calculating all the eigenvectors of a real symmetric matrix, but those routines seem to be optimized for large matrices, and I don't care about the non-principal eigenvectors anyway. I've also seen the power method for calculating the principal eigenvector of a real matrix, but again, that method seems to me to be inefficient for small matrices. Maybe I'm over-stating the gains that I could get from knowing that my matrix is small?
3
-
3$\begingroup$ How fast does it need to be? Are you willing to trade accuracy for performance, and if so, how much? $\endgroup$– Bill BarthCommented Jun 6, 2013 at 18:24
-
$\begingroup$ I am willing to trade accuracy for performance, but I don't have a good answer to the "how much" question just yet. I'll think about it, and look into approximations. Thanks! $\endgroup$– anjruuCommented Jun 7, 2013 at 12:22
-
1$\begingroup$ I'm still interested in the how fast is enough part, too. Do you need to do hundreds, thousands, billions, trillions of these, etc? Is there a hard real-time requirement like you need to do 10,000 per frame at 60Hz? $\endgroup$– Bill BarthCommented Jun 8, 2013 at 3:49
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
There's this paper specialized for 3x3 matrices that gets very technical:
http://pages.cs.wisc.edu/~sifakis/project_pages/svd.html
There is code for it, but it's not simple at all. I would just stick to the power method, and write a specialized loop-unrolled matrix-vector multiplication routine, and call it a fixed number of times. If you can bound the maximum eigenvalue, you can probably just do re-normalization every $n$ iterations, instead of every iteration, which should save a lot of time.
Alternatively, you can try the Jacobi eigenvalue algorithm, which is extremely simple, and you have only 3 off-diagonal elements to annihilate, so it should not require many iterations to converge. The problem is that this won't get you the eigenvector, so you'd have to do a separate post-processing step for that, like with a rank-revealing QR factorization, which is somewhat complex.
$\begingroup$
$\endgroup$
A Google search returns many relevant links for this problem since it is a common problems in mechanics. A simple algorithm for symmetric and real 3x3 matrices is presented on Wikipedia:
http://en.wikipedia.org/wiki/Eigenvalue_algorithm#3.C3.973_matrices
$\begingroup$
$\endgroup$
1
From geometrical tools (www.geometrictools.com)
http://www.geometrictools.com/Documentation/EigenSymmetric3x3.pdf I hope this helps
-
2$\begingroup$ This document can now be found here: geometrictools.com/Documentation/RobustEigenSymmetric3x3.pdf $\endgroup$ Commented Jan 26, 2023 at 18:52