A C implementation for computing Dixon resultants and solving polynomial systems over finite fields and the rationals ℚ, based on the FLINT and PML libraries.

Website: https://drsolve.github.io

• Dixon resultant computation for variable elimination
• Polynomial system solver for n×n systems
• Dixon with triangular ideal reduction
• Finite fields:
  • Prime fields F_p (any size): Implemented with FLINT modular arithmetic, optionally accelerated by PML.
  • Extension fields F_{p^k}: Further optimized for binary fields F_{2^n} with n in {8, 16, 32, 64, 128}.
• Rational field ℚ: Rational reconstruction via multi-prime CRT. Set field_size = 0 to enable.
• Complexity analysis — estimates Dixon matrix size, Bezout degree bound, and operation count before computing
• Command line input or file input. Automatic output to solution files

• FLINT (recommended version: 3.5.0)
  https://github.com/flintlib/flint

git clone https://github.com/flintlib/flint.git && cd flint
./bootstrap.sh
./configure 
make
make install

• PML (built in)
  https://github.com/vneiger/pml

git clone https://github.com/drsolve/drsolve.git && cd drsolve
./configure
make
make check                         # optional
make install                       # optional

For more options, run ./configure --help or make help. We also provide a Windows GUI at drsolve-win or drsolve-cross.

./drsolve "polynomials" "eliminate_vars" field_size
./drsolve -o output.dr "polynomials" "eliminate_vars" field_size

Examples:

./drsolve "x+y+z, x*y+y*z+z*x, x*y*z+1" "x,y" 257
./drsolve -o output.dr "x^2+y^2+z^2-1, x^2+y^2-2*z^2, x+y+z" "x,y" 0

./drsolve "polynomials" field_size
./drsolve -s "polynomials" field_size

-s is the short form of solver mode. --solve still works for compatibility, and is optional when only "polynomials" field_size are provided. Example:

./drsolve -s "x^2 + y^2 + z^2 - 6, x + y + z - 4, x*y*z - x - 1" 257

Without flags, drsolve inspects the first non-space character of line 1:

• digit => solver mode
• otherwise => elimination mode

Line 1 : variables to ELIMINATE (comma-separated)
Line 2 : field size (prime or p^k; use 0 for Q; generator defaults to 't')
Line 3+: polynomials (comma-separated, may span multiple lines)
         (#eliminate = #equations - 1)

Example:

# example.dr
x0,x1
257
x0^3+x1^3+x2^3, x0*x1+x1*x2+x2*x1, x1*x2*x0+1

Run:

./drsolve example.dr
./drsolve -f example.dr -o my_result.dr

Line 1 : field size
Line 2+: polynomials
         (n equations in n variables)

Example:

# example_solve.dr
257
x^2+y^2+z^2-6, x+y+z-4, x*y*z-x-1

Run:

./drsolve example_solve.dr
./drsolve -s -f example_solve.dr -o my_solutions.dr

./drsolve -v 0 <arguments>
./drsolve -v 1 <arguments>
./drsolve -v 2 <arguments>
./drsolve -v 3 <arguments>

-v 0 prints nothing but still writes the output file. -v 1 is the default. -v 2 restores the debug-level console output and timing. -v 3 additionally dumps small intermediate matrices.

For --comp: -v 0 prints only the final overall complexity, -v 1 prints the per-step / per-method summary, -v 2 adds formulas and parameter values, and -v 3 adds extra detail.

Example:

./drsolve -v 2 -f in.dr -o out.dr

Estimates the difficulty of a Dixon resultant computation without performing it. Reports equation count, variable count, degree sequence, Dixon matrix size (via Hessenberg recurrence), Bezout degree bound, and complexity in bits.

./drsolve --comp "polynomials" "eliminate_vars" field_size
./drsolve -c     "polynomials" "eliminate_vars" field_size
./drsolve --comp -f example.dr -o report.dr

Examples:

./drsolve --comp "x^3+y^3+z^3, x^2*y+y^2*z+z^2*x, x+y+z-1" "x,y" 257

Custom omega — set the matrix-multiplication exponent used in the complexity formula (default: 2.3):

./drsolve --comp --omega 2.373 "polynomials" "eliminate_vars" field_size
./drsolve -c -w 2.0            "polynomials" "eliminate_vars" field_size

File input uses the same elimination-file format shown above:

./drsolve --comp example.dr           # default output: out/example_comp.dr
./drsolve --comp -f example.dr -o report.dr

./drsolve "x + y^2 + t, x*y + t*y + 1" "y" 2^8

The default settings use t as the extension field generator and FLINT's built-in field polynomial.

./drsolve -s "x^2 + t*y, x*y + t^2" "2^8: t^8 + t^4 + t^3 + t + 1"

(with AES custom polynomial for F_256)

./drsolve --ideal "ideal_generators" "polynomials" "eliminate_vars" field_size
./drsolve --ideal -f input.dr -o output.dr

Example:

./drsolve --ideal "a2^3=2*a1+1, a3^3=a1*a2+3" "a1^2+a2^2+a3^2-10, a3^3-a1*a2-3" "a3" 257

After each multiplication, reduces x^q -> x for every variable.

./drsolve --field-equation "polynomials" "eliminate_vars" field_size
./drsolve --field-equation -r "[d1,d2,...,dn]" field_size

Example:

./drsolve --field-equation "x0*x2+x1, x0*x1*x2+x2+1, x1*x2+x0+1" "x0,x1" 2
./drsolve --field-equation -r [3]*5 2

./drsolve --method <num> --threads <num> <args>
./drsolve --dixon <args>
./drsolve --macaulay <args>
./drsolve --subres <args>

Available methods: 0. Recursive; 1. Kronecker+HNF; 2. Interpolation; 3. sparse interpolation; 5. fast recursive Dixon construction.

For convenience, 2 equations + 1 elimination variable auto-enable --subres, and 3/4 equations with standard Dixon shape auto-enable the fast recursive Dixon construction unless a method is explicitly selected.

Note: Only the Interpolation method supports multi-threading. The default method HNF or sparse interpolation does not support parallel acceleration.

Generate random polynomial systems with specified degrees for testing and benchmarking.

./drsolve --random "[d1,d2,...,dn]" field_size
./drsolve -r       "[d]*n"          field_size

• [d1,d2,...,dn]: degree list (comma-separated) for n polynomials
• [d]*n: all n polynomials have same degree d
• field_size: field size (prime or extension); use 0 for Q

# Random + Dixon elimination
./drsolve -r -s "[d1,...,dn]" field_size

# Random + complexity analysis
./drsolve -r --comp  "[d]*n" field_size
./drsolve -r -c --omega 2.373 "[4]*5" 257   # custom omega

# Random + Dixon with ideal reduction
./drsolve -r "[d1,d2,d3]" "ideal_generators" field_size

# 3 polynomials (deg 3,3,2) in GF(257)
./drsolve --random "[3,3,2]" 257

# Solve 3 quadratic system in GF(257)
./drsolve -r -s "[2]*3" 257

# Complexity analysis of 4 quartic polynomials
./drsolve -r --comp --omega 2.373 "[4]*4" 257

drsolve_sage_interface.sage lets you call DRsolve directly from SageMath with Sage polynomial objects.

• Load the interface with load("drsolve_sage_interface.sage"), then set the binary path once with set_dixon_path("./drsolve").
• Main entry points:
  • DixonRes(F, elim_vars, ...) / DixonResultant(...)
  • DixonSolve(F, ...)
  • DixonComplexity(F, elim_vars, ...)
  • DixonIdeal(F, ideal_gens, elim_vars, ...)
• Common options include field_size, verbosity, time, threads, debug, live_output, and timeout.
• field_size may be an integer prime, a string such as "2^8" or "2^8: t^8+t^4+t^3+t+1", a Sage GF(...) object, or 0 for ℚ. If omitted, it is inferred from the Sage polynomial ring when possible.
• Resultants are returned as strings, so iterative elimination works naturally by feeding one DixonRes(...) output into the next call.
• For a fuller Sage reference with examples and options, see index.txt or the top docstring in drsolve_sage_interface.sage.

Each output file contains field information, input polynomials, computation time, and the resultant, solutions, or complexity report.

• Equation count, variable list, elimination variable list, remaining variables
• Degree sequence of input polynomials
• Bezout bound (product of degrees)
• Dixon matrix size (Hessenberg recurrence)
• Resultant degree estimate
• Complexity in log₂ bits (with the omega value used)

• All computation modes generate a solution/report file by default under out/
• Use -o output.dr to override the default output filename
• Extension fields are slower than prime fields due to polynomial arithmetic
• The optional PML library only accelerates well-determined systems over prime fields
• Complexity analysis does not run any polynomial arithmetic; it parses only
• Over Q (field_size=0), --ideal and --field-equation are not supported

DRSolve is distributed under the GNU General Public License version 2.0 (GPL-2.0-or-later). See the file COPYING.