Fraction-free linear algebra

See the documentation for what this is about.

This code is licensed under the Hippocratic License Version 3.0. Check the license for details, or click the badge:

lib.rs:

Fraction-free linear algebra for [ndarray], with minimal trait bounds.

This library provides linear algebra primitives that will work without inexact divisions. Sometimes, this is called "integer-preserving" linear algebra, because all intermediate results are kept as integers. The trick is to represent a matrix A with rational entries as a product D^(-1)B, where D is diagonal, and both D and B have only integral entries. Currently,

• LU decomposititon of full-rank, square-or-wider matrices,
• unique solutions to linear systems,
• matrix inverses, and
• determinants

are implemented.

Trait bounds placed on entry types of matrices are as loose as reasonably possible, hence this library should in principle be applicable for every integral domain. However, the various primitive integer types are the motivating example and main intended use case. In particular, all functions require matrix entries to be [Copy].

Everything here is based on an algorithm that computes a fraction-free LU decomposition taken from Dureisseix' paper "Generalized fraction-free LU factorization for singular systems with kernel extraction". However, the "singular" and "kernel extraction" parts of the paper are not yet implemented: For now, this library can solve only systems that have exactly one solution. That is enough to compute the inverse of a square matrix, if it exists, which was the original motivation.

Written in pure Rust, with few dependencies and even fewer optimisations, this library is for you if your matrices aren't extremely big, and you want to work without specialised hardware or platform restrictions.