4ti2/4ti2

A software package for algebraic, geometric and combinatorial problems on linear spaces. By R. Hemmecke, R. Hemmecke, M. Köppe, P. Malkin, M. Walter

4ti2's Issues

4ti2API

In src/groebner/4ti2API.cpp the functions _4ti2_rays_create_state and _4ti2_circuits_create_state perform the same call as _4ti2_qsolve_create_state to new _4ti2_::QSolveAPI();

If I am not wrong, to get appropiate results, new _4ti2_::RaysAPI(); and new _4ti2_::CircuitsAPI(); should be called in its corresponding "create_state" function.

Thanks

Add issues from mailing list

Tests fail to tun: /bin/sh: ../check.template: not found

check target fails:

...skipped...
Making check in test
gmake[1]: Entering directory '/usr/ports/math/4ti2/work/4ti2-Release_1_6_9/test'
Makefile:838: warning: overriding recipe for target 'check-recursive'
Makefile:560: warning: ignoring old recipe for target 'check-recursive'
cd gensymm && gmake check
gmake[2]: Entering directory '/usr/ports/math/4ti2/work/4ti2-Release_1_6_9/test/gensymm'
gmake  check-local
gmake[3]: Entering directory '/usr/ports/math/4ti2/work/4ti2-Release_1_6_9/test/gensymm'
/bin/sh: ../check.template: not found
gmake[3]: *** [Makefile:627: check-local] Error 127

FreeBSD 11.2 amd64

Replace use of PATH_MAX by asprintf (C11)

... suggested by Jerome BENOIT for Debian

Make DEBUG_4ti2 configurable by configure

Mention running autogen.sh in README?

This is doubtlessly a minor issue but an inexperienced user might be at a loss when said to run ./configure which is not there.
Actually, although I compiled 4ti2 successfully and it works, I am not sure whether the canonical way is to first of all run autogen.sh and then follow the steps in README. Is it so?

Add "-q" switch to ppi

Make precision flag -p consistent

To set arbitrary precision, hilbert needs -p gmp while rays and (all ?) other programs need -p arb.

(Reported by Bernard Berthomieu.)

Out of bounds vector access

From Jerry James:
The Fedora Linux distribution recently added -D_GLIBCXX_ASSERTIONS to
the default compiler flags. This enables assertions in recent
versions of glibc that check arguments to various functions and
methods. The 4ti2 1.6.7 build is triggering one of those assertions
while running the 4ti2 test suite. The assertion complains of an
invalid vector access. I will paste in a bit of my attempt to debug
the issue:

$ cd test/circuits
$ gdb ../../src/groebner/.libs/4ti2int64
(gdb) run circuits -m 33

/usr/include/c++/8/bits/stl_vector.h:932: std::vector<_Tp,
_Alloc>::reference std::vector<_Tp,
_Alloc>::operator[](std::vector<_Tp, _Alloc>::size_type) [with _Tp =
_4ti2_::Vector*; _Alloc = std::allocator<_4ti2_::Vector*>;
std::vector<_Tp, _Alloc>::reference = _4ti2_::Vector*&;
std::vector<_Tp, _Alloc>::size_type = long unsigned int]: Assertion
'__builtin_expect(__n < this->size(), true)' failed.

Program received signal SIGABRT, Aborted.
0x00007ffff653800b in raise () from /lib64/libc.so.6
(gdb) bt
#0  0x00007ffff653800b in raise () from /lib64/libc.so.6
#1  0x00007ffff6522591 in abort () from /lib64/libc.so.6
#2  0x00007ffff7b74938 in std::__replacement_assert (
    __file=__file@entry=0x7ffff7bb7f50 "/usr/include/c++/8/bits/stl_vector.h",
    __line=__line@entry=932,
    __function=__function@entry=0x7ffff7bc0400
<_ZZNSt6vectorIPN6_4ti2_6VectorESaIS2_EEixEmE19__PRETTY_FUNCTION__>
"std::vector<_Tp, _Alloc>::reference std::vector<_Tp,
_Alloc>::operator[](std::vector<_Tp, _Alloc>::size_type) [with _Tp =
_4ti2_::Vector*; _Alloc = std::allocator<_4ti2_::Vector*>;
std::vector<_Tp, _A"...,
    __condition=__condition@entry=0x7ffff7bb7f20 "__builtin_expect(__n
< this->size(), true)") at
/usr/include/c++/8/x86_64-redhat-linux/bits/c++config.h:2389
#3  0x00007ffff7b93243 in std::vector<_4ti2_::Vector*,
std::allocator<_4ti2_::Vector*> >::operator[] (this=<optimized out>,
__n=<optimized out>)
    at /usr/include/c++/8/bits/stl_vector.h:805
#4  0x00007ffff7ba18d1 in _4ti2_::VectorArray::operator[] (index=4,
    this=0x555555772298) at ../../src/groebner/VectorArray.h:165
#5  _4ti2_::CircuitMatrixAlgorithm<_4ti2_::ShortDenseIndexSet>::compute1 (
    this=this@entry=0x7fffffffdfa0, orig_matrix=..., vs=..., circuits=...,
    rs=..., cirs=...) at ../../src/groebner/CircuitMatrixAlgorithm.tpp:260
#6  0x00007ffff7b926dc in
_4ti2_::CircuitMatrixAlgorithm<_4ti2_::ShortDenseIndexSet>::compute
(cirs=..., rs=..., circuits=..., vs=..., matrix=...,
    this=0x7fffffffdfa0) at ../../src/groebner/CircuitMatrixAlgorithm.tpp:50
#7  _4ti2_::QSolveAlgorithm::compute (this=this@entry=0x7fffffffe1e0,
    matrix=..., vs=..., circuits=..., rs=..., cirs=...)
    at QSolveAlgorithm.cpp:344
#8  0x00007ffff7b92923 in
_4ti2_::QSolveAlgorithm::compute(_4ti2_::VectorArray const&,
_4ti2_::VectorArray&, _4ti2_::VectorArray&, _4ti2_::VectorArray&,
_4ti2_::LongDenseIndexSet const&, _4ti2_::LongDenseIndexSet const&) ()
    at QSolveAlgorithm.cpp:301
#9  0x00007ffff7b92e12 in
_4ti2_::QSolveAlgorithm::compute(_4ti2_::VectorArray const&,
_4ti2_::VectorArray&, _4ti2_::VectorArray&, _4ti2_::VectorArray&,
_4ti2_::Vector const&, _4ti2_::Vector const&) () at
QSolveAlgorithm.cpp:146
#10 0x00007ffff7b7d055 in _4ti2_::CircuitsAPI::compute() ()
    at /usr/include/c++/8/bits/stl_vector.h:930
#11 0x0000555555559daf in _4ti2_::qsolve_main(int, char**) ()
    at qsolve_main.cpp:62
#12 0x00005555555576cb in main () at main.cpp:107
#13 0x00007ffff65241bb in __libc_start_main () from /lib64/libc.so.6
#14 0x000055555555793a in _start () at qsolve_main.cpp:67
(gdb) frame 4
#4  0x00007ffff7ba18d1 in _4ti2_::VectorArray::operator[] (index=4,
    this=0x555555772298) at ../../src/groebner/VectorArray.h:165
165        return *vectors[index];
(gdb) print *this
$1 = {vectors = std::vector of length 0, capacity 32, number = 0, size = 9}

The assertion fires in this loop at the bottom of
CircuitMatrixAlgorithm::compute1.

Vector zero(vs.get_size(), 0);
for (int i = 0; i < circuits.get_number(); ++i)
{
    if (circuits[i] <= zero) { vs[i].mul(-1); }
}

This code seems to assume that vs and circuits are the same size, but
as you can see from the gdb output above, vs has size zero. I have
tried changing the for loop termination test to "i <
circuits.get_number() && i < vs.get_number()", and I have tried adding
this above the declaration of Vector zero:

if (vs.get_number() < circuits.get_number())
    vs.renumber(circuits.get_number());

Both attempts fixed the out of bounds vector access, but resulted in
the algorithm computing the wrong answer. This is not terribly
surprising, since I do not understand the algorithm.

I should note that we get a failure that looks the same in the same
loop at the bottom of CircuitSupportAlgorithm::compute1 on
another test.

INT32_MIN and INT32_MAX are not defined in src/zsolve/VectorArrayAPI.hpp

Builds for multiple architectures (Power, s390x, i586) are failing for openSUSE, because INT32_MIN and INT32_MAX are not defined/declared in the file VectorArrayAPI.hpp.

[ 102s] In file included from ../../src/zsolve/RelAPI.h:26,
[  102s]                  from RelAPI.cpp:23:
[  102s] ../../src/zsolve/VectorArrayAPI.hpp: In function 'void _4ti2_zsolve_::convert(const T1&, T2&) [with T1 = long int; T2 = int]':
[  102s] ../../src/zsolve/VectorArrayAPI.hpp:79:14: error: 'INT32_MIN' was not declared in this scope; did you mean 'INT_MIN'?
[  102s]    79 |     if (v1 < INT32_MIN || v2 > INT32_MAX) {
[  102s]       |              ^~~~~~~~~
[  102s]       |              INT_MIN
[  102s] ../../src/zsolve/VectorArrayAPI.hpp:79:32: error: 'INT32_MAX' was not declared in this scope
[  102s]    79 |     if (v1 < INT32_MIN || v2 > INT32_MAX) {
[  102s]       |                                ^~~~~~~~~
[  102s] ../../src/zsolve/VectorArrayAPI.hpp:31:1: note: 'INT32_MAX' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
[  102s]    30 | #include <cstdlib>
[  102s]   +++ |+#include <cstdint>
[  102s]    31 |  

Dou you mean (as referenced by the build system) the INT32_MAX from the cstdint library?

Running time increases for repeated iteration using zsolve.

I found an interesting phenomenon about "zsolve()" in "4ti2" package in SageMath 9.1. Please see the sample codes, which prints the running time of a function zsolve().

from sage.interfaces.four_ti_2 import four_ti_2
import time
A = [[1,1,1],[1,2,3]]
rel = ['<', '<']
rhs = [2, 3]
sign = [1,1,1]
for i in range(1000):
    start = time.time()
    result=four_ti_2.zsolve(A, rel, rhs, sign)
    print("Running time for zsolve in 4ti2:", time.time()-start," sec")

I expected that except for the first iteration, which needs time for loading the library at first time on the memory, all iterations should take statistically consistent time with some noise following a normal distribution. However, the below chart from the output of the above code shows result different than what I expected.

This graph counts from the second iteration to the last iteration. We can observe that the running time is increasing while the operation itself still the same. Since I'm not an expert in programming so unsure that it is an issue of 4ti2 or python, but I hope to know the reason why this phenomenon happens and how to prevent it to minimize its running time.

Thank you very much for reading this issue.

Byeongsu Yu ([email protected])

src/groebner/script.template.in - do not use egrep

to avoid deprecation warnings - https://trac.sagemath.org/ticket/34708

Ray command doesn't interpret .rel file with inequality symbols

Small issue I encountered: the "ray" command as of version 1.6.9 does not properly interpret a ".rel" file which uses the symbols "<", ">" and "=" rather than corresponding integers "-1", "1" and "0". Example project files with the two different formats for the .rel file are attached, as well as output after calling the ray command for the projects.

bug-examples.zip

Install location for 4ti2 headers

groebner, util, zsolve should perhaps appear as subdirectories of ${prefix}/4ti2.
Check what distributions do.

Fix DEBUG_4ti2 build: Replace lp->it_cnt by lpx_get_int_parm

From Jerry James for Fedora:

there is a bug in the patch, but only for debug builds. Where the old version had:

  lpx_get_int_parm(lp, LPX_K_ITCNT)

the patched version has:

  lp->it_cnt

which is only correct if the compiler can see the structure definition. By default, that is not the case; it is an opaque type. I complained to glpk upstream about the lack of a way to get this information with the new API. I was promised that the next release of glpk will have a function glp_get_it_cnt() to retrieve it. However, that next release hasn't happened yet. Anyway, if you want those DEBUG_4ti2() forms to compile correctly, you'll have to arrange to see the internal structure for now, then migrate to glp_get_it_cnt() once it is actually available, or patch your copy of glpk to add glp_get_it_cnt(). We did the latter for Fedora, with the attached patch. It guards the new function with FEDORA_GLPK_ITCNT to avoid compatibility problems; you probably don't want that.

Add CI scripts

Add automatic deployment to latte-int/distro

Better integer overflow detection

It seems that 4ti2 relies on the gcc flag -ftrapv to detect integer overflows, but this flag has been
broken for years in gcc, and still is, apparently.

(Reported by Bernard Berthomieu.)

configure --with-glpk=yes should give an error if glpk cannot be found

Likewise for GMP.

Wishlist item: Inhomogeneous circuits

make check failed

Compiled 4ti2 1_6_9 successfully, but make check failed with

test_input_conversion_gmp.cpp:84:45: warning: ISO C++ forbids converting a string constant to ‘char*’ [-Wwrite-strings]
mv -f .deps/test_input_conversion_gmp.Tpo .deps/test_input_conversion_gmp.Po
/bin/bash ../../../libtool  --tag=CXX   --mode=link g++ -I../../../src/  -O3 -fomit-frame-pointer -malign-double -fstrict-aliasing -ffast-math -Wall -std=c++0x   -o test_input_conversion_gmp_to_64 test_input_conversion_gmp.o ../../../src/groebner/lib4ti2int64.la ../../../src/4ti2/lib4ti2common.la -lm
libtool: link: g++ -I../../../src/ -O3 -fomit-frame-pointer -malign-double -fstrict-aliasing -ffast-math -Wall -std=c++0x -o .libs/test_input_conversion_gmp_to_64 test_input_conversion_gmp.o  ../../../src/groebner/.libs/lib4ti2int64.so ../../../src/4ti2/.libs/lib4ti2common.so -lm
/usr/bin/ld: test_input_conversion_gmp.o: undefined reference to symbol '_ZrsRSiP12__mpz_struct'
/usr/local/lib/libgmpxx.so.4: error adding symbols: DSO missing from command line
collect2: error: ld returned 1 exit status
Makefile:785: recipe for target 'test_input_conversion_gmp_to_64' failed
make[4]: *** [test_input_conversion_gmp_to_64] Error 1
make[4]: Leaving directory '/home/bernard/Downloads/assorted_math_packages/4ti2-Release_1_6_9/test/qsolve/api'
Makefile:1087: recipe for target 'check-am' failed
make[3]: *** [check-am] Error 2
make[3]: Leaving directory '/home/bernard/Downloads/assorted_math_packages/4ti2-Release_1_6_9/test/qsolve/api'
Makefile:552: recipe for target 'check-recursive' failed
make[2]: *** [check-recursive] Error 1
make[2]: Leaving directory '/home/bernard/Downloads/assorted_math_packages/4ti2-Release_1_6_9/test/qsolve'
Makefile:837: recipe for target 'checkdir-qsolve' failed
make[1]: *** [checkdir-qsolve] Error 2
make[1]: Leaving directory '/home/bernard/Downloads/assorted_math_packages/4ti2-Release_1_6_9/test'
Makefile:583: recipe for target 'check-recursive' failed
make: *** [check-recursive] Error 1

OS is ubuntu 16.04.

Improve sage interface, perhaps make standalone python interface

Resurrect website 4ti2.de

As of Jul 12, 2018:
This page is currently under construction. It will be up again soon.

Add automatic deployment scripts for github release

https://docs.travis-ci.com/user/deployment/releases/
https://github.com/forexample/github-binary-release

4ti2 web: Automate updating of h.html from NEWS

zsolve does not find a solution to linear system with a single lattice point

Below is an example of a linear system that I know has a single solution but for some reason zsolve can't find it.
At some point I have began to question myself and have tested the number of lattice points using Latte.

I attach the input files for 4ti2-zsolve that I have prepared as well as the corresponding input file for Latte (as a list of hyperplane inequalities) .
(since github is checking file extensions files have been renamed in such a manner that riddle.mat was renamed to mat_riddle.txt
For simplicity I have also prepared a csv file that contains all constraints in human-readable format.

Am I doing something wrong or is it a bug?

mat_riddle.txt
rel_riddle.txt
rhs_riddle.txt
sign_riddle.txt
latte_riddle.txt
riddle.csv

EDIT: the input for latte should have 92 as the width dimension instead of 91 (is it possible to update the attached file?)

potential integer overflow in 32bit system

Hi, there are potential integer overflow vulnerabilities that can affect the 32bit system.

In src/util/output.c:59, the program reads the value of numOfVars from input file and calls createVector.

fscanf(in,"%d",numOfVars);

if (numOfVectors==0) return (0);

b=createVector(*numOfVars);

Since there is no range check in createVector, it may cause integer overflow and small buffer allocation which leads to buggy behavior.

vector createVector(int numOfVars) {
  vector w;

  w = (vector)malloc(sizeof(int)*(numOfVars+1));
  if (w==0) {
    printf("Could not allocate memory in function createVector.\n");
    printf("Please report this problem.\n");
    exit(0);
  }
  return (w);
}

Similar issues can happen in

4ti2/src/util/output.c

Line 720 in 4d70ab9

labels = (char **)malloc(sizeof(char*)*(numOfVars));

4ti2/src/util/output.c

Line 859 in 4d70ab9

labels = (char **)malloc(sizeof(char*)*(numOfVars));

Thank you.

Don't print progress messages to stdout

duplicate recipe, a warning

This is with version 1.6.9, as used by Macaulay2:

-*- mode: compilation; default-directory: "~/src/M2/M2/M2/BUILD/dan/builds.tmp/einsteinium-master/libraries/4ti2/build/4ti2-1.6.9/test/" -*-
Comint started at Sun Apr 19 09:34:43

make check
Makefile:838: warning: overriding recipe for target 'check-recursive'
Makefile:560: warning: ignoring old recipe for target 'check-recursive'
...

Make handling of legacy input file name (without .mat extension) consistent

"zbasis MyProject" loudly complains if file MyProject (without any extension) exists, even though it
is supposed to read MyProject.mat only. I then get the errors:

 INPUT ERROR: Badly formatted file MyProject 
 INPUT ERROR: Check the number of rows and columns. 
 INPUT ERROR: Check there are only integers. 

The other tools seem not to complain if a file with the name of the project already exists. 

(Reported by Bernard Berthomieu.)