LinalgScalar does not have to imply Sub and Div

[dingxiangfei2009]

trafficstars

Recall the definition of LinalgScalar: https://github.com/rust-ndarray/ndarray/blob/eb82c93f0147df38e061597221ece3627f119a60/src/linalg_traits.rs#L18-L28

However, no algorithm involving LinalgScalar requires the scalar to be invertible in the additive group and multiplicative semigroup, in this crate at the very least. Therefore, Sub and Div trait bounds are not used. It would be more flexible if Sub and Div trait bounds are relaxed.

In addition, Add<Self, Output=Self> and Mul<Self, Output=Self> is already implied by num::Zero and num::One, respectively. These trait bounds can be relaxed, too.

[bluss]

It restricts adding new features if we remove these, so I don't think we should.

[dingxiangfei2009]

@bluss or maybe not. Additional features, if requiring invertibilities, can make use of additional trait bounds on top of this. It would be more reasonable if requirements of various linear algebraic procedures are clearly separated apart, so that algorithms can be generic over as many data types as possible.

By the way, what new features are being planned that can be affected by this change?

[bluss]

It's true, I don't know if there are concrete plans

[LukeMathWalker]

It depends on how far-reaching are our plans for LinalgScalar. It can be quite convenient to be able to divide and subtract when implementing linear algebra routines that go beyond matrix multiplication. Do we have a concrete reason to remove this, apart from minimalism (which is generally a good principle, but re-introducing these bounds if we realize we need them later on would be a breaking change, so...)?

How do we handle this in ndarray-linalg @termoshtt?

[bluss]

@dingxiangfei2009 Can you formulate which types you want to include, and what new things can be accomplished with ndarray, with this change? Being specific is great.

[dingxiangfei2009]

@bluss Sure. I am writing routines to decompose finitely generate modules over principle ideal domains into invariant factor forms, and a matrix having entries in the PID is a natural representation of conversion from the module's input form into its invariant factor form. For instance, the entries will be just integers that does not equip division. Integers do not technically equip division and the closest thing to division is rem_euclid. In order to highlight this difference, a wrapper type is constructed to explicitly disallow naive division. In this case Div will never be implemented on this wrapper type.

Relaxing the requirement will in addition enable us to model computation on finitely generate modules over PID with ndarray, instead of only computation on vector spaces.

@LukeMathWalker I privately digged around ndarray-linalg crate, and it uses its own Scalar trait that semantically incorporate the properties of LinalgScalar trait. There is no references to LinalgScalar in that crate.

[dingxiangfei2009]

There is another issue with trait bounds on some methods with ArrayBase that I think I need to raise a separate ticket for. LinalgScalar and stacking with ArrayBase prohibits num::BigRational from being used as the "scalar" (?) and elements of a matrix, because Copy is required. However, BigRational is not Copy, because it needs heap allocation.

[vadym-kl]

@LukeMathWalker @bluss @dingxiangfei2009 I would also be interested in using ndarray for matrices with integer entries, so removing Div would be really nice. This will enable the use of ndarray for various algorithms from computational number theory. For libraries in other languages that benefit from matrices with integer entries ( and entries in other rings ) see:

C/C++

• https://github.com/flintlib/flint2
• https://github.com/libntl/ntl

Julia

• https://github.com/Nemocas/Nemo.jl
• https://github.com/thofma/Hecke.jl
• https://github.com/wbhart/AbstractAlgebra.jl

I did a quick search and it looks like there is no dependencies on this trait outside ndarray within rust-ndarray org.

P.S. Thank you for such a useful library.

[bluss]

Just to come back to why does this trait exist, to better understand the problem: It's the minimal requirements on floating point elements, so that operations that are typical of float or complex float BLAS can be implemented in pure Rust. In addition to that, it has the 'static bound so that we can use type id - which is mandatory to be able to detect types such as f32 and f64 and dispatch to the correct BLAS function.

Yes, it's possible to break this up into separate traits.

[vadym-kl]

Thanks for getting back on this, and thanks for the clarification about LinalgScalar trait design. Something I would like to be able to do is to use .dot and kron for matrices and vectors with scalar being an integer type. Currently Dot trait implementation requires the scalar to implement LinalgScalar trait for vector-vector multiplication matrix-vector multiplication and matrix-matrix multiplication and similarly, the Kronecker product of two matrices requires LinalgScalar trait.

If I understand your point correctly, the reason for the current design is to be able to seamlessly switch between pure Rust implementation and blas implementation. The latter requires LinalgScalar while pure Rust implementation does not.

Would you be interested in a PR that splits LinalgScalar into a trait that captures integer types and modifying src/linalg/impl_linalg.rs so that Pure Rust implementation can be used with a wider range of scalar types?
Or do you think this could make code too complex and out of the scope for this library?

Any suggestions regarding the PR are welcome.

Abandoning #1235, as I understand the design better.