Source-linked AI summary
Nemo/Hecke: Computer Algebra and Number Theory Packages for the Julia Programming Language
Claus Fieker, William Hart, Tommy Hofmann, Fredrik Johansson
TL;DR
Nemo and Hecke bring computer algebra and number theory algorithms to Julia, combining generic Julia implementations with wrappers for specialized C/C++ libraries. The paper demonstrates high-performance generic algorithms and improvements over existing systems, while noting that alternative models for real and complex numbers may be added in the future.
Problem
Method
Nemo combines generic Julia algorithms and data structures with wrappers for specialized C/C++ libraries, and Hecke builds on Nemo for algebraic number theory.
Source: §1 · p. 1Results
The authors report high-performance Julia algorithms and improvements over the state of the art in existing computer algebra systems.
Source: §1 · p. 1Takeaways & Limitations
Julia’s JIT compilation can specialize generic algorithms for types where no specific C implementation exists.
Source: §2 · p. 1Alternative implementations of real and complex numbers, such as a lazy bit-stream abstraction with automatically increasing precision, may be added in the future.
Source: §5.2 · p. 5
Abstract
from arXiv · showhide
We introduce two new packages, Nemo and Hecke, written in the Julia programming language for computer algebra and number theory. We demonstrate that high performance generic algorithms can be implemented in Julia, without the need to resort to a low-level C implementation. For specialised algorithms, we use Julia's efficient native C interface to wrap existing C/C++ libraries such as Flint, Arb, Antic and Singular. We give examples of how to use Hecke and Nemo and discuss some algorithms that we have implemented to provide high performance basic arithmetic.
1 INTRODUCTION
Nemo and Hecke bring computer algebra and number theory routines to Julia: Hecke builds on Nemo for algebraic number theory. The packages combine Julia implementations with wrappers for specialized C/C++ libraries, and the paper demonstrates high-performance algorithms and improvements over existing systems.
1 INTRODUCTION
- Nemo is a Julia computer algebra package, and Hecke builds on it to cover algebraic number theory.Nemo’s eventual aim is to provide performant commutative algebra, number theory, group theory, and discrete geometry routines.Source: §1 · p. 1
- Nemo combines generic algorithms and mathematical data structures implemented in Julia with wrappers for specialized C/C++ libraries.The libraries include Flint, Arb, Antic, and Singular.Source: §1 · p. 1
- The authors demonstrate that Julia can implement high-performance computer algebra algorithms and that their implementations improve on the state of the art in existing systems.Source: §1 · p. 1
2 COMPUTER ALGEBRA IN JULIA
Julia’s type system and JIT compilation support generic algorithms specialized for particular types, while Nemo models mathematical domains with abstract and parent objects. The packages also provide targeted in-place operations to reduce allocation and copying.
2 COMPUTER ALGEBRA IN JULIA
- Julia’s JIT compilation specializes generic algorithms for specific types when no specific C implementation exists.Julia also provides near-C or Fortran performance for low-level arithmetic.Source: §2 · p. 1
- Nemo uses parametric types for generic structures such as polynomials, while abstract types organize related mathematical domains.Julia’s abstract-type hierarchy lets ring-level generic functions also work with fields.Source: §2 · p. 1, §2.1 · pp. 1–2
2.1 Modelling domains in Julia
- Julia’s most-specific dispatch lets Nemo use a specialized implementation, including a C routine, for concrete types when available.Nemo wraps C types for ground domains and can switch to Flint’s polynomial wrapper over Z.Source: §2.1 · p. 2
- Modeling a domain such as Z/nZ as a type would place its modulus in the type and trigger recompilation for each distinct modulus.Instead, the modulus is attached to elements through a parent object, which acts like a type while holding domain-specific information.Source: §2.1 · p. 2
- Parent objects support coercions and constructors and can carry context for C libraries, while remaining ordinary Julia objects.They can be passed directly to C functions when their bit representation matches native C objects.Source: §2.1 · p. 2
2.2 In-place operations
- Reusable scratch variables and mutation methods avoid creating intermediate objects and copying unchanged data in performance-critical operations.In-place operations also save memory-allocation and garbage-collection costs.Source: §2.2 · p. 2
3 NEMO EXAMPLES
Nemo examples exercise polynomial arithmetic, resultants, and generic linear algebra. The reported timings show strong performance against other systems in these examples, alongside a comparison between generic Julia code and specialized implementations.
3 NEMO EXAMPLES
- The examples present Nemo code as benchmark problems, including a determinant computation over a cubic number field.Source: §3 · p. 2, §3.3 · p. 3
3.1 Multivariate polynomials
- The polynomial examples compare sparse multivariate arithmetic timings; the Fateman benchmark tests f·(f+1), while the Pearce problem is too sparse for the big-array method.The compared approaches include Johnson’s sparse multiplication algorithm and dense-polynomial big-array algorithms.Source: §3.1 · pp. 2–3, Table 1 · p. 3
- Within a factor of two of Flint’s C implementation without assembly, generic Julia code also runs slightly faster than Magma’s C code.For multivariate polynomials over Z, Nemo uses Flint by default rather than its generic Julia implementation.Source: §3.1 · p. 3, Table 2 · p. 3
3.2 Generic resultant
- The resultant example constructs recursive finite-field, polynomial, and residue rings before applying polynomial arithmetic.Flint is used for univariate polynomials over a finite field.Source: §3.2 · p. 3
- 0.2 s in Nemo, compared with 82 s in Magma and 179907 s in SageMath, for the generic resultant example.The example computes a resultant of polynomials in a nested quotient-ring setting.Source: §3.2 · p. 3
3.3 Generic linear algebra
- 2.4 s in Nemo, compared with 5.3 s in Magma, 21.9 s in Pari/GP, and 5893 s in SageMath, for the determinant benchmark.The benchmark uses an 80×80 matrix over a cubic number field; Antic provides the number-field arithmetic.Source: §3.3 · p. 3
4 GENERIC ALGORITHMS IN NEMO
Nemo implements generic polynomial and matrix algorithms in Julia, alongside specialized approaches for important operations. The section describes how these algorithms handle coefficient-ring constraints and presents a multimodular method for integer-matrix minimal polynomials.
4 GENERIC ALGORITHMS IN NEMO
- Nemo’s generic algorithms target fundamental polynomial and matrix operations where efficient implementations are important to higher-level computer algebra and number theory.Source: §4 · p. 3
4.1 Polynomial algorithms
- For generic coefficient rings, Nemo provides dense univariate, truncated power-series, and sparse distributed multivariate polynomial types, with subresultant pseudoremainder sequences for resultants.The resultant code can handle zero divisors when impossible inverses are caught, using a cubic-time Sylvester-matrix method as backup to the quadratic method.Source: §4.1 · p. 3
- Sparse polynomial operations use heap-based algorithms, with variable extraction for multivariate pseudodivision and degree- and monicity-based heuristics for GCD variable order.For polynomials with few terms, powering uses the multinomial formula; multivariate polynomials over Z also have an optimized Flint C implementation.Source: §4.1 · pp. 3–4
4.2 Matrix algorithms
- For generic commutative rings, determinant computation uses fraction-free LU with a division-free fallback, while polynomial-ring determinants use interpolation.The fallback computes the characteristic polynomial and extracts its determinant.Source: §4.2 · p. 4
- The fraction-free Danilevsky method computes characteristic polynomials by reducing matrices to Frobenius form while avoiding fractions through exact division.A scaling factor introduced at each outer iteration can be removed at the next step.Source: §4.2 · p. 4
4.2.1 Minimal polynomial.
- The multimodular spinning variant combines minimal polynomials computed modulo small primes using Chinese remaindering.It checks lifted basis vectors to verify a stabilized candidate; these matrix-vector tests usually cost less than direct matrix-matrix evaluation.Source: §4.2.1 · pp. 4–5
- In tested examples, the multimodular algorithm slightly outperforms Magma, including for matrices whose minimal polynomial is smaller than the characteristic polynomial.The authors report a worst-case cost of O(n^4) operations over Z, but say this is far from the generic case.Source: §4.2.1 · p. 5
5 C/C++ WRAPPERS IN NEMO
Nemo combines wrappers for specialized C/C++ libraries with Julia code to expose arithmetic, ball arithmetic, and algebraic-number-field operations. The section describes capabilities from Flint, Arb, and Antic, and notes a compatible Singular package.
5.1 Flint: arithmetic and number theory
- Flint supplies arithmetic and polynomial, matrix, and power-series operations across several ground rings; Nemo wraps its types and additional algorithms.Flint’s integer-polynomial multiplication selects among classical, Karatsuba, Kronecker, and FFT methods, with tuned cutoffs.Source: §5.1 · p. 5
5.2 Arb: arbitrary precision ball arithmetic
- Arb represents real values as arbitrary-precision midpoint-radius balls and complex values as rectangular boxes, with precision stored in Nemo’s parent object.Lazy evaluation can restart at higher precision, while automatic error bounds provide a certificate.Source: §5.2 · p. 5
5.3 Antic: algebraic number fields
- Antic provides Nemo’s number-field element arithmetic using Flint polynomials and precomputed context data to accelerate reduction and traces.It can defer reduction during dot products by accumulating unreduced products and reducing their sum afterward.Source: §5.3 · pp. 5–6
5.4 Singular: commutative algebra
- Singular is a C/C++ package for polynomial systems and algebraic geometry, and Singular.jl is a compatible Julia package for Nemo.The authors say Singular.jl will be described in a future article.Source: §5.4 · p. 6
6 HECKE: ALGEBRAIC NUMBER THEORY IN JULIA
Hecke brings algebraic number theory functionality to Julia, with new strategies for ideal arithmetic and computations involving approximations. Its examples show how these strategies support efficient ideal operations and guaranteed numerical results.
6 HECKE: ALGEBRAIC NUMBER THEORY IN JULIA
- Hecke provides element and ideal arithmetic in number-field orders, class-group and unit-group computation, verified embeddings, and verified Dedekind zeta residue computation.Most challenges use established techniques with modifications; the authors identify ideal arithmetic and computations with approximations as areas with new strategies.Source: §6 · p. 6
6.1 Fast ideal arithmetic in rings of integers
- Two-generator ideal representations are space-efficient, but working with two generators has been a key algorithmic difficulty.Normal presentations refine this representation by fixing a set S of primes and choosing generators with specified divisibility behavior.Source: §6.1 · p. 6
- Two gcd computations and a few arithmetic operations yield compatible ideal presentations, making multiplication cost asymptotically that of one algebraic-number multiplication.The authors contrast this with earlier algorithms, which require a linear-algebra step.Source: §6.1 · pp. 6–7
6.2.1 Computing conjugates.
- Ball arithmetic carries error analysis through approximate computations, maintaining guaranteed results without the a priori error analysis required by floating-point arithmetic.For conjugates, Hecke increases working precision until the computed balls meet the requested diameter bound.Source: §6.2.1 · p. 7
6.2.2 Torsion units.
- For large field degree, testing candidate exponents for whether an element is torsion quickly becomes inefficient; conjugate-based tests instead refine ball approximations until a lemma’s conditions hold.The stated procedure eventually terminates because the ball radii tend to zero.Source: §6.2.2 · pp. 7–8
6.2.3 Residues of Dedekind zeta functions.
- Approximating the Dedekind zeta residue can certify that tentative class and unit groups are correct.The described approximation uses the Belabas–Friedmann algorithm under GRH; ball precision is increased until the requested error bound is met.Source: §6.2.3 · p. 8