algpath benchmarks
algpath benchmarks is a repository for homotopy continuation benchmarking. It is able to test different packages on polynomial systems, and to process the results in the form of tables and latex output.
Choosing the right branch
If you wish to perform your own benchmarks, you can clone the master branch. It has no results in it, only the scripts to perform benchmarks. In the tables folder you can find tables that can be used to run a series of benchmarks all at once (see run_entries.py). If you wish to access the raw data of A. Guillemot and P. Lairez. “Validated Numerics for Algebraic Path Tracking”, checkout to the branch issac_2024. If you wish to access the raw data of [A.Guillemot. “Certified Algebraic Path Tracking with Algpath”], checkout to the branch issac_2025.
Packages
Algpath, as well as the dev branch of algpath and a legacy version of algpath are submodules of this repository. To properly run benchmarks, it is required to update submodules with git submodule update --init --recursive. Compilation of algpath (main, dev, legacy) should be automatic, assuming that it can be compiled following instructions available at https://gitlab.inria.fr/numag/algpath/ (in particular you should enable AVX2 with the right compilation flags, see section Flags of algpath's README). If you compile algpath or the dev branch manually, you should use --feature "stats, disable_solutions".
Other packages (HomotopyContinuation.jl using julia, NAG for macaulay2, SIRROCO in SageMath) should be globally installed.
Creating a test file
Test file structure
The tested polynomial systems are stored in the data directory, in the form of JSON files containing info on the system. Here is a self-documenting input example. You can find a more precise documentation at algpath.
{
"system": [
"(0.818087391139500 - 0.809819499072137*I)*t*x0^10 + (-1.41235019958604 + 0.377371245510132*I)*t*x0^9 + (0.0705134085338873 + 1.21130004351844*I)*x0^10 + (0.503844134609127 + 0.908033829431579*I)*t*x0^8 + (0.244784168714577 + 0.882571674833907*I)*t*x0^7 + (0.253558366628191 + 1.13475494399624*I)*t*x0^6 + (-0.285623749704346 + 0.634196894406212*I)*t*x0^5 + (-0.970555787739074 + 0.429151054840467*I)*t*x0^4 + (-0.375976354583012 + 0.142113895698499*I)*t*x0^3 + (0.0788823115693671 + 0.949941419011724*I)*t*x0^2 + (-0.0274778530882288 - 0.994649865546906*I)*t*x0 + (-0.486870994043363 + 0.574248055961871*I)*t - 0.0705134085338873 - 1.21130004351844*I"
],
"variables": [
"x0"
],
"parameters": [
"t"
],
"path": [
[
"0.0"
],
[
"1.0"
]
],
"fiber": [
[
"1.00000000000000"
],
[
"0.809016994374947 + 0.587785252292473*I"
],
[
"0.309016994374947 + 0.951056516295154*I"
],
[
"-0.309016994374948 + 0.951056516295154*I"
],
[
"-0.809016994374947 + 0.587785252292473*I"
],
[
"-1.00000000000000 + 1.22464679914735e-16*I"
],
[
"-0.809016994374947 - 0.587785252292473*I"
],
[
"-0.309016994374948 - 0.951056516295154*I"
],
[
"0.309016994374947 - 0.951056516295154*I"
],
[
"0.809016994374947 - 0.587785252292473*I"
]
]
}Running a benchmark
run_test.py :
run_test.py is a python script to run a single benchmark, using pkg on data. It stores the results in the benchmarks directory. Documention can be accessed via python3 run_test.py --help.
Example run
python3 run_test.py packages/algpath.py data/linear/dense-10/all/1.json -p -m 8G -t 1hOutput can be found in benchmarks/linear/dense-10/all/1/algpath.
run_entries.py
A python script to run benchmarks specified in a JSON entry file. Documentation about entry files can be found in the next section. Entry files can be found in tables/some-dir/entries.json.
Example run
python3 run_entries.py tables/example_table/entries.json -p -m 8G -t 1hProcessing results
Entries
To process data, a JSON file must be specified containing what entries the table will contain. It consists of a list of data names and a tree representing the header of the table. Here is a self-explanatory example (tables/example_table/entries.json). More tables can be found in the tables directory.
{
"data_list": [
"linear/dense-10/all/1",
"linear/dense-20/all/1"
],
"packages": [
"algpath",
"algpath-reckless",
"algpath-dev",
"legacy_algpath",
"sirocco",
"macaulay2",
"homotopycontinuation"
],
"header": {
"val": "root",
"children": [
{
"val": "name",
"children": []
},
{
"val": "dimension",
"children": []
},
{
"val": "tot deg",
"children": []
},
{
"val": "algpath",
"children": [
{
"val": "tottime",
"children": []
},
{
"val": "maxsteps",
"children": []
}
]
},
{
"val": "algpath-reckless",
"children": [
{
"val": "tottime",
"children": []
},
{
"val": "maxsteps",
"children": []
}
]
},
{
"val": "algpath-dev",
"children": [
{
"val": "tottime",
"children": []
},
{
"val": "maxsteps",
"children": []
}
]
},
{
"val": "legacy_algpath",
"children": [
{
"val": "tottime",
"children": []
},
{
"val": "maxsteps",
"children": []
}
]
},
{
"val": "sirocco",
"children": [
{
"val": "tottime",
"children": []
},
{
"val": "maxsteps",
"children": []
}
]
},
{
"val": "macaulay2",
"children": [
{
"val": "tottime",
"children": []
},
{
"val": "maxsteps",
"children": []
}
]
},
{
"val": "homotopycontinuation",
"children": [
{
"val": "tottime",
"children": []
},
{
"val": "maxsteps",
"children": []
}
]
}
]
}
}We now give the list of statistics that can be shown in a table.
| Statistic | Type | Description |
|---|---|---|
raw name |
global | The name of the data test without any processing |
name |
global | Processed name of the data tests |
dimension |
global | Number of variables |
max deg |
global | Maximum degree of the equations |
tot deg |
global | Total degree of the system (in factorized form) |
paths |
global | Number of paths tracked |
f |
global | Number of instructions for the circuit evaluating the system |
df |
global | Number of instructions for the circuit evaluating the derivative of the system |
bezout |
global | Bezout bound of the system |
medmean hc algpath |
global | Median number of steps required for algpath/median number of steps required for homotopycontinuation |
htype |
global | Homotopy type |
failures |
local | Number of reported failures |
tottime |
local | Total time elapsed on the example |
meantime |
local | Mean time per path |
totsteps |
local | Total number of steps for the example |
stepseries |
local | Array listing the steps on each path |
stepspersec |
local | Number of steps per second |
timeperstep |
local | Time per step |
meansteps |
local | Mean number of steps |
stdsteps |
local | Standard deviation of the number of steps |
medsteps |
local | Median number of steps |
minsteps |
local | Minimum of the number of steps |
maxsteps |
local | Maximum of the number of steps |
q1steps |
local | First quartile of the number of steps |
q3steps |
local | Third quartile of the number of steps |
maxprec |
local | Maximum precision reached during computation |
meanprec |
local | Mean through all paths, of the mean of the precision at each iteration of the main loop in a single continuation |
maxmeanprec |
local | Max through all paths, of the mean of the precision at each iteration of the main loop in a single continuation |
wmeanprec |
local | Mean through all paths, of the mean weighted by step size of the precision at each iteration of the main loop in a single continuation |
maxwmeanprec |
local | Max through all paths, of the mean weighted by step size of the precision at each iteration of the main loop in a single continuation |
pathjump |
local | If path jump occured |
type : global if the satistic does not depend on a package, else local.
synthethize.sage
Description
A SageMath script to generate a table of results out of given entries. Documentation can be found with sage synthesize.sage --help.
Example run
sage synthesize.sage tables/example_table/entries.jsonlatextable.py
Description
A python script to generate a latex output out of a table of results. You can redirect the output to the file latex/table.tex and compile latex/minimal.tex to visualize your table. Documentation can be found with python3 latextable.py --help.
Example run
python3 latextable.py tables/example_table/table.json > latex/table.texFull example run
Assuming that you have SageMath and Latex installed, here is a full run to perform the benchmarks and process the results into a table:
python3 run_entries.py tables/example_table/entries.json -m 8G -t 1h
sage synthesize.sage tables/example_table/entries.json
python3 latextable.py tables/example_table/table.json > latex/table.tex
cd latex
latexmk minimal.tex
open minimal.pdf &