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.
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.
{
"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"
]
]
}
gen.sage
It is also possible to automatically generate examples coming from different families. Inputting the right arguments, it will generate a JSON file in data containing the requested example.
Description
A sage script that generates examples from different families.
Usage
sage gen.sage.py [-h] [--paths [PATHS]] {linear,newton} type [type ...]
Positional arguments
Argument | Description |
---|---|
{linear,newton} |
Homotopy type |
type |
Type of target system, followed by its parameters. It can be dense <d1> ... <dn> , structured <n> <d> <l> or katsura <n>
|
Options
Short | Long | Default | Description |
---|---|---|---|
--paths [PATHS] |
all |
Number of paths tracked. Should be either an positive integer or all
|
Running a benchmark
runtest.py :
Description
A python script to run a single benchmark, using pkg
on data
. It stores the results in the benchmarks directory.
Usage
usage: python3 runtest.py [-h] [-p] [-t [TIMEOUT]] [-m [MEM]] pkg data
Positional arguments
Argument | Description |
---|---|
pkg |
The package which is tested. Should be packages/<pkg_name> .py e.g. packages/algpath.py
|
data |
The system which is tested. Shoud be data/<test_name> .json e.g. data/linear_dense-10_all-paths_1.json
|
Options
Short | Long | Default | Description |
---|---|---|---|
-p |
--perf |
perf stat the benchmark and put the result in perflog.txt | |
-t [TIMEOUT] |
--timeout [TIMEOUT] |
None |
To run the benchmark with a timeout. Should be written as <number><unit> where <unit> may be nothing (this implicitely means seconds), s, m or h, e.g. 1h |
-m [MEM] |
--mem [MEM] |
None |
Maximum amount of memory used. Should be written as <number><unit> where <unit> may be nothing, K, M or G, e.g. 100M |
-n |
--norun |
To only generate script and command |
runall.py
Description
A python script to run multiple benchmarks. By default, it runs all the tests present in data with all packages present in packages and stores the results in benchmarks.
Usage
usage: python3 runall.py [-h] [-p] [-t [TIMEOUT]] [-m [MEM]] [-n] [-P [PACKAGES]]
Options
Short | Long | Default | Description |
---|---|---|---|
-p |
--perf |
perf stat the benchmarks and put the result in perflog.txt | |
-t [TIMEOUT] |
--timeout [TIMEOUT] |
None |
To run the benchmarks with a timeout. Should be written as where may be nothing (this implicitely means seconds), s, m or h, e.g. 1h |
-m [MEM] |
--mem [MEM] |
None |
Maximum amount of memory used for the different tests. Should be written as <number><unit> where <unit> may be nothing, K, M or G, e.g. 100M |
-n |
To only run benchmarks not previously done | ||
-P [PACKAGES] |
--packages [PACKAGES] |
algpath,macaulay2,sirocco,homotopycontinuation |
Comma separated list of packages to test |
Processing 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 :
{
"data_list": [
"linear_dense-10_all-paths_1",
"linear_dense-20_all-paths_1",
"linear_dense-30_all-paths_1",
"linear_dense-40_all-paths_1",
"linear_dense-50_all-paths_1",
"linear_dense-100_all-paths_1",
"linear_dense-500_all-paths_1",
"linear_dense-1000_all-paths_1",
"linear_dense-5-5_all-paths_1",
"linear_dense-10-10_all-paths_1",
"linear_dense-20-20_all-paths_1",
"linear_dense-30-30_all-paths_1",
"linear_dense-40-40_all-paths_1",
"linear_dense-50-50_all-paths_1",
"linear_katsura-4_all-paths_1",
"linear_katsura-6_all-paths_1",
"linear_katsura-8_100-paths_1",
"linear_katsura-10_100-paths_1",
"linear_katsura-15_100-paths_1",
"linear_katsura-20_100-paths_1",
"linear_katsura-25_100-paths_1",
"linear_katsura-30_100-paths_1",
"linear_katsura-40_100-paths_1",
"linear_dense-3-3-3-3_100-paths_1",
"linear_dense-3-3-3-3-3-3_100-paths_1",
"linear_dense-3-3-3-3-3-3-3-3_100-paths_1",
"linear_structured-4-3-5_100-paths_1",
"linear_structured-6-3-5_100-paths_1",
"linear_structured-8-3-5_100-paths_1",
"newton_structured-5-5-5_all-paths_1",
"newton_structured-10-10-5_all-paths_1",
"newton_structured-15-15-5_all-paths_1",
"newton_structured-20-20-5_all-paths_1",
"newton_structured-25-25-5_all-paths_1",
"newton_structured-30-30-5_all-paths_1",
"newton_dense-3-3-3-3-3-3-3-3_all-paths_1",
"newton_dense-3-3-3-3-3-3_all-paths_1",
"newton_dense-3-3-3-3_all-paths_1",
"newton_structured-4-3-5_all-paths_1",
"newton_structured-6-3-5_all-paths_1",
"newton_structured-8-3-5_all-paths_1"
],
"header": {
"val": "root",
"children":
[
{"val": "name", "children": []},
{"val": "dimension", "children": []},
{"val": "max deg", "children": []},
{"val": "paths", "children": []},
{
"val": "instructions",
"children":
[
{"val": "f", "children": []},
{"val": "df", "children": []}
]
},
{
"val": "homotopycontinuation",
"children":
[
{"val": "failures", "children": []},
{"val": "medsteps", "children": []},
{"val": "maxsteps", "children": []},
{"val": "stepspersec", "children": []},
{"val": "tottime", "children": []}
]
},
{
"val": "algpath",
"children":
[
{"val": "failures", "children": []},
{"val": "medsteps", "children": []},
{"val": "maxsteps", "children": []},
{"val": "stepspersec", "children": []},
{"val": "tottime", "children": []}
]
},
{
"val": "macaulay2",
"children":
[
{"val": "failures", "children": []},
{"val": "medsteps", "children": []},
{"val": "maxsteps", "children": []},
{"val": "stepspersec", "children": []},
{"val": "tottime", "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 | If the test was generated by gen.sage, returns the family to which the examples belong (dense, structured, katsura). If the homotopy was Newton, a "N" is added as a superscript. If a number of paths was specified, a "*" is added as a superscript |
dimension |
global | Number of variables |
max deg |
global | Maximum degree of the equations |
paths |
global | Number of paths tracked |
instructions |
global | Number of instructions. Should have f or df as a child |
f |
global | Number of instruction for the circuit evaluating the system |
df |
global | Number of instruction 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 |
totime |
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 |
type : global if the satistic does not depend on a package, else local.
synthethize.py
Description
A python script to generate a table of results out of given entries.
Usage
usage: python3 synthesize.py [-h] entries
Positional arguments
Argument | Description |
---|---|
entries |
A JSON file containing entries |
latextable.py
Description
A python script to generate a latex output out of a table of results.
Usage
usage: python3 latextable.py [-h] entries
Positional arguments
Argument | Description |
---|---|
table |
A JSON table file (should be generated via synthethize.py) |