Flint Documentation
Release 3.1.0
The Flint development team
Feb 25, 2024
CONTENTS
1 Introduction 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 What is Flint? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Maintainers and Authors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.3 Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.4 Structure of Flint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.5 License . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Building, testing and installing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 Quick start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 Library and install paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Testing FLINT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.4 Static or dynamic library only . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.5 AVX2 instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.6 TLS, reentrancy and single mode . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.7 ABI and architecture support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.8 CMake build for Windows users . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.9 Uninstalling FLINT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.10 Assertion checking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.11 Linking and running code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Bug reporting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.1 Reporting bugs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Contributing to FLINT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4.1 Code conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4.2 Test code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5 Contributors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5.1 Contributors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6.1 Example programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7.1 Memory allocation functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7.2 Global caches and cleanup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7.3 Temporary allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.8 Portability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.8.1 Portable FLINT types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.9 Threading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.9.1 Multithreaded FLINT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.9.2 Writing threaded functions in FLINT . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.9.3 Functional parallel programming helpers . . . . . . . . . . . . . . . . . . . . . . . 13
2 General utilities 15
2.1 flint.h – global definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.1 Macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.2 Integer types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.3 Allocation Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
i
2.1.4 Random Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.5 Thread functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.6 Input/Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.7 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 profiler.h – performance profiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.1 Timer based on the cycle counter . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.2 Framework for repeatedly sampling a single target . . . . . . . . . . . . . . . . . 22
2.2.3 Memory usage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.4 Simple profiling macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 thread_pool.h – thread pool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.3.1 Thread pool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4 mpoly.h – support functions for multivariate polynomials . . . . . . . . . . . . . . . . . 24
2.4.1 Orderings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.2 Monomial arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.3 Monomial comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.4 Monomial divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.5 Basic manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4.6 Setting and getting monomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4.7 Packing and unpacking monomials . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.4.8 Chunking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4.9 Chained heap functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5 machine_vectors.h – SIMD-accelerated operations on fixed-length vectors . . . . . . . 30
2.5.1 Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.5.2 Printing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.5.3 Access and conversions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.5.4 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.5.5 Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.5.6 Arithmetic and basic operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.5.7 Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3 Generic rings 35
3.1 gr.h – generic structures and their elements . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.1.2 Context operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.1.3 Element operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2 gr.h (continued) – implementing rings . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.2.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.2.2 Method table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2.3 Placeholder and trivial methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2.4 Required methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.2.5 Testing rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.3 gr.h (continued) – builtin domains and types . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3.1 Coercions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3.2 Domain properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3.3 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3.4 Base rings and fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.3.5 Extended number sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.3.6 Floating-point arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.3.7 Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.3.8 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.9 Polynomial rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.10 Fraction fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.11 Symbolic expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.4 gr_generic.h – basic algorithms and fallback implementations for generic elements . . . 54
3.4.1 Generic string parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.4.2 Generic arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.4.3 Generic special functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.4.4 Generic vector methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
ii
3.5 gr_special.h – special arithmetic and transcendental functions . . . . . . . . . . . . . . 61
3.5.1 Mathematical constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.5.2 Elementary functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.5.3 Factorials and gamma functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.5.4 Combinatorial numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.5.5 Error function and exponential integrals . . . . . . . . . . . . . . . . . . . . . . . 64
3.5.6 Orthogonal polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.5.7 Bessel, Airy and Coulomb functions . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.5.8 Hypergeometric functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.5.9 Riemann zeta, polylogarithms and Dirichlet L-functions . . . . . . . . . . . . . . 66
3.5.10 Elliptic integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.5.11 Elliptic, modular and theta functions . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.6 gr_vec.h – vectors over generic rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.6.1 Types and basic operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.6.2 Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.6.3 Sums and products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.6.4 Dot products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.6.5 Other functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.7 gr_mat.h – dense matrices over generic rings . . . . . . . . . . . . . . . . . . . . . . . . 73
3.7.1 Type compatibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.7.2 Types, macros and constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.7.3 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.7.4 Window matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.7.5 Input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.7.6 Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.7.7 Assignment and special values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.7.8 Basic row, column and entry operations . . . . . . . . . . . . . . . . . . . . . . . 75
3.7.9 Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.7.10 Diagonal and triangular matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.7.11 Gaussian elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.7.12 Solving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.7.13 Determinant and trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3.7.14 Rank . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3.7.15 Row echelon form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3.7.16 Nullspace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.7.17 Inverse and adjugate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.7.18 Characteristic polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.7.19 Minimal polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.7.20 Similarity transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.7.21 Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.7.22 Jordan decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.7.23 Matrix functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.7.24 Hessenberg form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.7.25 Random matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.7.26 Special matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.7.27 Helper functions for reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.8 gr_poly.h – dense univariate polynomials over generic rings . . . . . . . . . . . . . . . . 85
3.8.1 Type compatibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.8.2 Weak normalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.8.3 Types, macros and constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.8.4 Memory management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.8.5 Basic manipulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.8.6 Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.8.7 Powering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.8.8 Shifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.8.9 Scalar division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.8.10 Division with remainder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.8.11 Power series division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
iii
