Mentions légales du service

Skip to content
Snippets Groups Projects

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)