2 unstable releases
0.2.0  Aug 16, 2022 

0.1.0  Jul 7, 2020 
#913 in Math
210KB
5K
SLoC
Cyclotomic
This is a library for exact operations in cyclotomic fields that is welltested, welldocumented, and aims for speed in certain use cases. Can be used from C, C++ or Rust.
TODO

Get rid of the clones in the Rational implementations.

See if we can use f64 for cases where we know the answer will be an integer.

See if structure constants can become competitive if we use floats.

Dense representations:
 Dense polynomials with computation modulo the cyclotomic polynomial

Get rid of all the copy and paste, make some abstractions that actually make sense.

C FFI interface for calling our Rust code from other languages

Explicit construction as field of fractions of ring of integers. Trivial inversion, good when you're only multiplying?

More investigation and thought into SIMD usage.
Why use this library?
There are other libraries for more general usecases out there, for example:
They all do many things and have a wide scope. Our library only does one thing, and does it fast: cyclotomic field operations. And not just that, we are optimised for the specific use case of cyclotomic linear algebra, with the intention of using SIMD operations wherever it will make our code faster (backed up by extensive benchmarking).
There's a lot of structure common to all number fields, and it's possible to get number field operations reasonably fast. But there is much, much more that's specific to cyclotomic fields, and this allows us to be faster for certain use cases (keep an eye on arXiv for some details).
See below for some benchmarks against antic.
Features

Sparse representations:
 Using the Zumbroich basis (GAPinspired) and hash maps of exponents (64 bit ints) to coefficients
 The same as the above, but with arbitrary integer exponents  this is for very large degree fields.

Dense representations:
 Vector of coefficients and Zumbroich basis (the same as GAP, unpacked)
 Vector of coefficients with multiplication via the structure constants (viewed as a Qalgebra).
Performance
The sparse representation perform better than the dense representations when the elements are sparse. Still acceptable even for nonsparse elements.
TODO: some graphs to show this
Quick start
TODO: you also need to have the antic and flint libraries installed, add some instructions for that.
Use cyclotomic in a Rust program
To install the latest release, install
cargo
to get a functional Rust installation, including the cargo package
manager. Then add the cyclotomic
crate to your Cargo.toml
:
[dependencies]
cyclotomic = "1.*"
If you're using this before version 1 is released, then change that to "0.*", but there'll be a lot of breaking changes.
Use cyclotomic in a C or C++ program
TODO, but this is very important.
More documentation
Take a look here for full API documentation, along with code examples.
Quick start for devs
 Install Rust using the instructions on their website
 Check that Cargo is on your PATH by running
cargo version
in the terminal  Clone this repository using
git clone https://github.com/CyclotomicFields/cyclotomic.git
 Download the prime tables by running the bash script
./download_prime_tables.sh
. You may then optionally convert it to a CSV using the J script./convert_prime_tables_to_csv.ijs
, which will enable the program to load the primes into memory faster  Check that all the tests pass using
cargo test
 Add your name to the contributors list in this README and push, to confirm that you have push permissions
 Check that your push has triggered a pipeline build on Travis
 Run the benchmark by first installing nightly rust with
rustup install nightly
and then runningcargo +nightly bench
.
Building the documentation
Just run cargo doc nodeps
and have a look at
target/doc/cyclotomic
with a web browser.
Coming soon: MathJax rendered LaTeX math in the documentation.
Motivation
Most of the motivation for this project comes from representation theory. In particular, given a finite group G, where m is the least common multiple of the orders of the elements of G, let K be a cyclotomic field containing the mth roots of unity.
Then using only coefficients from K, you can realise all representations of G. So in some sense, the cyclotomic numbers are "all you need" when it comes to the representation theory of finite groups.
The goals of this project are (in order):

Implement field operations and equality for cyclotomic fields of arbitrary degree. This includes testing, since otherwise we don't know whether it works or not.

Make it readable, well documented, and not a complete mess to contribute to. Documentation may or may not include detailed and rigorous (in a mathematical sense) proofs of any performanceenhancing tricks used.

Profile and benchmark everything so the performance of this library is good enough that it can be used to solve nontrivial problems.
Inspiration
The implementation we have borrowed most from is the one for the GAP computer algebra system, which implements specific logic for cyclotomic fields using various basis tricks. This is closest in spirit to what we're doing, but isn't standalone.
Another library is cyclotomic which is the same thing but in Haskell. This is just a reimplementation of GAP's algorithms, but I find Haskell code easier to read than C sometimes, so this deserves a mention.
Benchmarks
There is a README in the benchmarks/
directory, as well as some utility
programs for plotting results.
Contributors
Rob Moore, Kaashif Hymabaccus
Copyright
Copyright (C) 2020 Rob Moore, Kaashif Hymabaccus
This program is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
The full license text can be found in the LICENSE file.
Dependencies
~8.5MB
~183K SLoC