eigenvalues and eigenvectors

[droundy]

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

[bitshifter]

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]

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]

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.

[bitshifter]

Making a similar comment to what I made on #589.

Sorry it's taken me a long time to get to this issue. It raises a lot of questions that I hadn't really thought about, but it's made me think about the scope of what I want to support in glam and that this is probably out of scope. Looking at comparable game math libraries in Godot, Unity 3D or Unreal Engine, their math libraries don't support calculating eigenvectors and eigenvalues. It also introduces a need for a complex number type, which glam doesn't currently have and I think they would also be out of scope.

I think the best approach would be to create a separate crate (e.g. glam-eigen) which adds traits for calculating eigenvalues and eigenvectors, and adds num-complex as a dependency for its complex type implementation and implement these traits on glam types.

I would be happy to add supporting methods to glam like the trace method added here.

[squaaawk]

Sounds good. I figured this type of algorithm would be out of scope, but wanted to make sure. I've created an (at-the-moment empty crate) here where I'll implement the eigenvalue and eigenvector algorithms soon.