dimforge / dimforge/nalgebra

Trait bounds for common matrix operations are more restrictive than their definition requires

Open
#1,044 6 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
4.8k
Forks
565
PR merge metrics
No merged PRs in 30d

Description

I'm writing a computer algebra system that uses `nalgebra::base::Matrix` as a generic matrix/vector type. Matrix coefficients can be arbitrary symbolic expressions, implying that they are not necessarily elements of any pre-determined algebraic structure. I would still like to perform **formal** operations like matrix multiplication and exponentiation (with integer exponents), as well as compute standard properties like the determinant and trace.

By definition of the matrix product and Leibniz determinant, `A × B` and `det(A)` are well-defined as long as coefficients can be added and multiplied, yielding a value of the same type (this can actually be relaxed even further, as to perform formal matrix multiplication, it is not strictly speaking necessary that the product of two coefficients is of the same type as the coefficients themselves, only that the resulting type is summable).

But currently, the nalgebra API is asking a lot more than that:

* The most general implementation of `Mul` requires entries to be `Zero + One + ClosedAdd + ClosedMul`, even though neither additive nor multiplicative identities are necessary to evaluate a formal matrix product (as long as you define that products involving empty matrices evaluate to an empty matrix).

* `.determinant()` requires entries to implement `ComplexField`, an incredibly broad trait that includes methods for computing transcendental functions, which is not at all necessary for evaluating a matrix determinant.

I'm aware that requiring the coefficients to be elements of certain algebraic structures enables optimizations such as decomposition-based determinant computation, which doesn't work if nothing is known about the coefficients. But *formally*, determinants, products, etc. are still well-defined, and it would be nice if nalgebra offered methods for computing them.

Formal matrix products and determinants have lots of practical applications, such as solving certain recurrence relations and ODEs, computing characteristic polynomials and resultants, and many, many more.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.