search

bitshifter / glam-rs

A simple and fast linear algebra library for games and graphics
Apache License 2.0
1.53k stars 156 forks source link

eigenvalues and eigenvectors #321

Open droundy opened 2 years ago

droundy commented 2 years ago

It would be nice to have methods to compute the eigenvalues and eigenvectors of matrices.

bitshifter commented 2 years ago

Out of curiosity, what do you want to use them for? I have not seen eigenvalues and eigenvectors used in the context of game dev that I can recall. I don't mean to question adding them, I just like to understand the use case of features before adding them.

droundy commented 2 years ago

I'm doing an animation drawing program not a game, and I'm computing the moment of inertia tensor to get a first guess as to the relative orientation of two frames. See https://github.com/droundy/sketch/blob/main/src/tween.rs#L205

EmiOnGit commented 1 year ago

Is this still relevant? I've implemented the methods myself in the past for this crate whenever I needed them and would be open to give it a try.

However, I feel like implementing methods for calculating the Eigenpair might be not as simple as it might seem.

Talking points

1) Eigenvalues can be complex.

Currently, glam doesn't have a implementation for complex numbers (which it shouldn't IMO). A possible solution would be to only return the real Eigenvalues and ignore the complex ones.

2) Efficient implementations are not as simple simple.

The Eigenpair implementation for 2x2 shouldn't be a big problem, 3x3 on the other hand might get ugly. Most people might know the method of finding and solving the characteristic polynomial (analytic approach). This sadly has proven to be numerical unstable in some cases. For a 3x3 matrix QR (or QL) decomposition or using householder reflections seem to be the goto standard.

3) How long do we iterate?

QR (and I think househoulder too) is implemented iterative. It is possible to find a upper bound for the error but we might want to agree on a error we allow for optimization reasons.

4) What do we do in case of a wrong input.

How do we respond to a 0 or close-to-0 matrix? Sure we could panic but this would be unpractical, considering that the user would need to make sure that the matrix is allowed.

5) Real and complex (1 and 3)

We might end up with 'slightly complex' eigenvalues through numerical errors. Would we map them to a real number with the risk of returning eigenvalues that shouldn't be returned or do we make sure to only return real eigenvalues with the risk of loosing some through numerical errors.