generic-rings documentation

These modules provide a plain C implementation of generic rings intended for use with Flint, Antic, Arb and Calcium. The idea is to support fully generic recursive constructions of rings (polynomials, fractions, power series, matrices, etc.) over arbitrary user-defined base rings (including all Flint/Antic/Arb/Calcium types) with the ability to add specializations (e.g. fmpz_mat functions instead of generic functions for matrices over fmpz). This code is experimental.

Contents

• gr.h – generic structures and their elements
  • Introduction
    • Parents and elements
    • Parent and element types
    • Error handling
    • Predicates
  • Context operations
  • Element operations
    • Memory management
    • Random elements
    • Input, output and string conversion
    • Assignment and conversions
    • Basic properties
    • Arithmetic
    • Division
    • Powering
    • Square roots
    • Greatest common divisors
    • Factorization
    • Integer and complex parts
    • Ordering methods
    • Finite field methods
• gr.h (continued) – implementing rings
  • Example
  • Method table
  • Placeholder and trivial methods
  • Required methods
  • Testing rings
• gr.h (continued) – builtin domains and types
  • Coercions
  • Domain properties
  • Groups
  • Base rings and fields
  • Floating-point arithmetic
  • Vectors
  • Matrices
  • Polynomial rings
• gr_special.h – special arithmetic and transcendental functions
  • Mathematical constants
  • Elementary functions
  • Factorials and gamma functions
  • Combinatorial numbers
  • Error function and exponential integrals
  • Orthogonal polynomials
  • Bessel, Airy and Coulomb functions
  • Hypergeometric functions
  • Riemann zeta, polylogarithms and Dirichlet L-functions
  • Elliptic integrals
  • Elliptic, modular and theta functions
• gr_vec.h – vectors over generic rings
  • Types and basic operations
  • Arithmetic
  • Sums and products
  • Dot products
  • Other functions
• gr_mat.h – dense matrices over generic rings
  • Type compatibility
  • Types, macros and constants
  • Memory management
  • Window matrices
  • Input and output
  • Comparisons
  • Assignment and special values
  • Basic row, column and entry operations
  • Arithmetic
  • Diagonal and triangular matrices
  • Gaussian elimination
  • Solving
  • Determinant and trace
  • Rank
  • Row echelon form
  • Nullspace
  • Inverse and adjugate
  • Characteristic polynomial
  • Minimal polynomial
  • Similarity transformations
  • Eigenvalues
  • Hessenberg form
  • Random matrices
  • Special matrices
  • Helper functions for reduction
• gr_poly.h – dense univariate polynomials over generic rings
  • Type compatibility
  • Weak normalization
  • Types, macros and constants
  • Memory management
  • Basic manipulation
  • Arithmetic
  • Powering
  • Shifting
  • Division
  • Power series division
  • Square roots
  • Evaluation
  • Multipoint evaluation and interpolation
  • Composition
  • Derivative and integral
  • Monic polynomials
  • GCD
  • Squarefree factorization
  • Roots
  • Power series special functions
• gr_mpoly.h – sparse multivariate polynomials over generic rings
  • Weak normalization
  • Types, macros and constants
  • Memory management
  • Basic manipulation
  • Comparisons
  • Input and output
  • Input and output
  • Coefficient and exponent access
  • Arithmetic
  • Container operations

Python interface (python-flint)

• Python interface (python-flint)
  • Introduction
    • Types, parents and coercions
    • Real and complex numbers
  • API documentation

Design

We use element pointers + context objects holding method pointers. Vectors of elements can be packed densely without indirection.

Principles/goals/benefits

• Plain C, similar interface to existing Flint code.

• Small code size, fast compilation.

• Possible to pack data efficiently (down to 1 byte / element).

• Data layouts backwards compatible with most existing Flint element types, and mostly also with polynomials, matrices, etc.

• Support all unusual cases in Flint/Arb/Calcium uniformly (error handling, inexact rings, noncomputable rings, context objects), with a uniform interface.

• Support fast stack based allocation of temporary variables and arrays (with safe limits).

• Fully in-place operations.

• Very fast (a few cycles) runtime construction of rings / context objects. (May be hundreds of cycles when constructing a new method table, but this is rarely needed on the fly.)

• Possibility to use generic default methods or provide optimized versions (e.g. for vector operations).

Disadvantages

• Runtime generics in C means very little compiler protection against type errors; rigorous testing is crucial.

• Some function signatures become more complicated in order to provide uniform error handling.

• A few cycles overhead for each dynamic function lookup and function call. Function pointer generics also preclude intra-method compiler optimizations and inlining. Overloading vector methods should partially compensate for this.

Possible applications

• At minimum, this could be useful to bootstrap new types: we only need to provide some basic methods (init, clear, set_fmpz, randtest, add, mul, equal, etc.) and the generic code provides fallbacks for everything else (which can be overloaded later for better performance). Importantly, the generic code also provides unit tests including tests for boring and easily borked things like type conversions.

• This could simplify interfacing from other libraries and languages; it is enough to wrap the generic interface once, without having to wrap all the methods for every single Flint type (with all their quirks and subtle differences in interface).

• There is already plenty of ad-hoc generic code in Flint and its descendants:

  • Function pointer generics are used, for example, in some mpoly code and in fmpz_mod.

  • Template-based generics for the different fq implementations.

  • Type union + switch statement generics for fq_default and nf.

  • Some Arb functions use ugly hacks to distinguish between constants and power series, etc.

  The generics module could potentially replace such code and also eliminate a lot of other copy-pasted boilerplate. By specializing methods at runtime for rings with different parameters, it should even be possible to improve performance in some cases.