|0.2.0||Aug 16, 2022|
|0.1.0||Jul 7, 2020|
#913 in Math
This is a library for exact operations in cyclotomic fields that is well-tested, well-documented, and aims for speed in certain use cases. Can be used from C, C++ or Rust.
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 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 use-cases 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).
- Using the Zumbroich basis (GAP-inspired) 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.
- Vector of coefficients and Zumbroich basis (the same as GAP, unpacked)
- Vector of coefficients with multiplication via the structure constants (viewed as a Q-algebra).
The sparse representation perform better than the dense representations when the elements are sparse. Still acceptable even for non-sparse elements.
TODO: some graphs to show this
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
to get a functional Rust installation, including the cargo package
manager. Then add the
cyclotomic crate to your
[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.
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 --versionin 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
- 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 nightlyand then running
cargo +nightly bench.
Building the documentation
cargo doc --no-deps and have a look at
target/doc/cyclotomic with a web browser.
Coming soon: MathJax rendered LaTeX math in the documentation.
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 performance-enhancing tricks used.
Profile and benchmark everything so the performance of this library is good enough that it can be used to solve non-trivial problems.
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.
There is a README in the
benchmarks/ directory, as well as some utility
programs for plotting results.
Rob Moore, Kaashif Hymabaccus
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.