dimforge / dimforge/nalgebra

Proposal: Provide nalgebra wrappers to `faer` factorizations

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

Description

[faer](https://faer-rs.github.io/), a pure Rust library for performant low-level linear algebra spearheaded by @sarah-ek, provides dense matrix factorizations with [remarkable performance](https://github.com/sarah-ek/faer-rs#cholesky-decomposition).

Implementing truly performant matrix factorizations is a major undertaking that only a precious few individuals are capable of. `nalgebra` provides matrix factorizations of its own, but they are not undergoing active development other than bug fixes, and there are - to my knowledge - no plans to improve them further. I propose that we rally behind `faer` and try to find a way to leverage these exciting developments, so that users of `nalgebra` can enjoy the improved performance provided by `faer`.

*Replacing* nalgebra's matrix factorizations would be a non-trivial affair. `nalgebra` targets both fixed-size small dimensions and dynamically sized and potentially large matrices. For high performance, different algorithms need to be used for small and large dimensions. Determining the point at which to switch is something that needs to be done with great care. Moreover, managing buffers and finding a good way for the decomposition to contain different data structures depending on dimensions are further non-trivial design considerations.

Therefore, I suggest we instead start by providing idiomatic `nalgebra` wrappers to `faer` decompositions in a separate module.

## Possible design

I propose that we provide a new module, `nalgebra::faer`, containing a separate struct for each relevant decomposition in `faer`. For example, faer's Cholesky decomposition may be named `faer::FaerCholesky`. I am not sure if the redundancy in naming is necessary, but it might help avoid confusion since at this point there will be multiple cholesky factorizations in `nalgebra`.

The individual APIs might look somewhat similar to the current APIs, so that it's easy to switch, but this also depends on what is appropriate for use with `faer`. I think we should experiment with this and see where it takes us.

I am not sure if we want to expose `faer` types in the public API, as this would mean that in the future, we may not be able to update `faer` internally without risking a breaking change for `nalgebra`. One way to accomplish this is to provide our own internal, sealed traits for data types, such as `FaerRealField`, `FaerComplexField` etc. These would use the corresponding `faer` traits as super traits (which would not be visible to users of `nalgebra`), but implemented for concrete types. On the other hand, I can see it being useful in some instances to be able to obtain the underlying `faer` decomposition directly, to offer the user more control. However, in that case the user can perhaps just work directly with `faer` instead.

## Experimental features

Continual breaking changes in `nalgebra` has become [a bit of a problem](https://github.com/dimforge/nalgebra/issues/1205) in the ecosystem, since `Matrix` data structures do not compose if libraries use different versions of `nalgebra`. I would personally like to see fewer breaking changes in `nalgebra` going forward. This is at odds with the perhaps experimental nature of this proposed feature, given that we are not quite sure about the design, and that the design may change over time as `faer` also changes.

I think this proposed feature might therefore be a good opportunity to try out something that we have only briefly discussed on the #nalgebra Discord.

It would be convenient if some parts of newly developing features could be exempt from semver. This might accelerate the pace of development of these features, and prevent breaking changes in `nalgebra` until we feel that we can commit to a particular design. One way to go about this is to introduce the concept of *experimental* features. These features would only be available under the `experimental` feature flag (so for the proposed `faer` integration, you would need to enable both `faer` and `experimental`), and the documentation for each experimental feature would clearly state that the feature is unstable, similar to how unstable features are documented in the Rust standard library.

To simplify managing experimental features, we could add an `#[experimental]` attribute macro to `nalgebra_macros`, maybe with a link to a tracking issue. For example:

```rust
#[experimental(issue = XXXX)]
mod faer;
```

which would produce very visible documentation along the lines of

> This is an experimental feature. Tracking issue: [#XXXX](github.com). Breaking changes in experimental features are not considered breaking changes for the crate, and must be enabled with the `experimental` feature flag.

This idea is based on [Eigen](https://eigen.tuxfamily.org/index.php?title=Main_Page)'s [unsupported modules](https://eigen.tuxfamily.org/dox/unsupported/index.html), although I'm not sure if we want to adopt the idea of *unsupported* code that is not actively maintained / tested and developed.

## Summary

I propose that we try to provide idiomatic `nalgebra` wrappers for the matrix factorizations provided by `faer` under the `faer` feature flag, and also move to implement it as an *experimental* feature, a new concept that could help us develop new features over time without having to worry about breaking changes in `nalgebra`.

I've outlined only a vague and general plan for how this might look like. I think detailed design work should happen alongside implementation work.

Longer term, beyond what is proposed here, I hope we can also consider conditionally using `faer` for matrix factorizations by default. But this is a more involved issue, and it would be helpful to have the experience of developing the wrappers separately for now.

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.