4
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ How fast does it need to be? Are you willing to trade accuracy for performance, and if so, how much? $\endgroup$ – Bill Barth Jun 6 '13 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$ – anjruu Jun 7 '13 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 Barth Jun 8 '13 at 3:49
3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

From geometrical tools (www.geometrictools.com)

http://www.geometrictools.com/Documentation/EigenSymmetric3x3.pdf I hope this helps

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.