Opened 3 years ago

Closed 2 years ago

#28886 closed enhancement (fixed)

Update FP(Y)LLL

Reported by: malb Owned by:
Priority: major Milestone: sage-9.1
Component: packages: standard Keywords:
Cc: Merged in:
Authors: Martin Albrecht Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 8dfc58c (Commits, GitHub, GitLab) Commit: 8dfc58ca566b16b68eba5a174d714ec7bba32add
Dependencies: Stopgaps:

Status badges

Change History (15)

comment:1 Changed 3 years ago by malb

  • Branch set to u/malb/update_fp_y_lll

comment:2 Changed 3 years ago by malb

  • Authors set to Martin Albrecht
  • Commit set to 05936462ca51aad623bd0dc12a041829fd198c7a
  • Component changed from PLEASE CHANGE to packages: standard
  • Description modified (diff)
  • Milestone changed from sage-9.0 to sage-9.1
  • Status changed from new to needs_review
  • Type changed from PLEASE CHANGE to enhancement

New commits:

0593646update FPLLL to 5.3.1 and FPYLLL to 0.5.1dev

comment:3 Changed 3 years ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

LGTM.

(Do you want this to be in 9.1 instead of 9.0? There might be some time to still sneak it in.)

comment:4 Changed 3 years ago by malb

I'd love to see this in 9.0 but I figured that's already on beta9.

comment:5 Changed 3 years ago by tscrim

  • Milestone changed from sage-9.1 to sage-9.0

Then we'll set it to 9.0 and see if it gets in. Worst case is it doesn't, but since there no point in intentionally delaying it, we might as well set 9.0 as the target.

comment:6 Changed 3 years ago by malb

Thanks, make sense.

comment:7 Changed 3 years ago by vbraun

  • Branch changed from u/malb/update_fp_y_lll to 05936462ca51aad623bd0dc12a041829fd198c7a
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:8 Changed 3 years ago by vbraun

  • Branch changed from 05936462ca51aad623bd0dc12a041829fd198c7a to u/malb/update_fp_y_lll
  • Resolution fixed deleted
  • Status changed from closed to new

On a Debian 9 x86_64 buildbot this causes

[...] 
sage: A = random_matrix(ZZ, 4, 4) ## line 4357 ##
sage: B = random_matrix(ZZ, 2, 3) ## line 4358 ##
sage: B._solve_iml(A) ## line 4359 ##
sage: A._solve_iml(B, right=False) ## line 4363 ##
sage: A._solve_iml(B, right=True) ## line 4367 ##
sage: A = random_matrix(ZZ, 2000, 2000) ## line 4374 ##
sage: B = random_matrix(ZZ, 2000, 2000) ## line 4375 ##
sage: t0 = walltime() ## line 4376 ##
sage: alarm(2); A._solve_iml(B)  # long time ## line 4377 ##
**********************************************************************
Traceback (most recent call last):
  File "/var/lib/buildbot/slave/sage2_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 2504, in __call__
    doctests, extras = self._run(runner, options, results)
  File "/var/lib/buildbot/slave/sage2_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 2553, in _run
    result = runner.run(test)
  File "/var/lib/buildbot/slave/sage2_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 897, in run
    return self._run(test, compileflags, out)
  File "/var/lib/buildbot/slave/sage2_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 710, in _run
    got = got.decode('utf-8')
  File "/var/lib/buildbot/slave/sage2_git/build/local/lib/python2.7/encodings/utf_8.py", line 16, in decode
    return codecs.utf_8_decode(input, errors, True)
MemoryError
**********************************************************************
File "src/sage/modules/free_module_integer.py", line 702, in sage.modules.free_module_integer.FreeModule_submodule_with_basis_integer.voronoi_cell
Failed example:
    V.volume()           # long time
Exception raised:
    Traceback (most recent call last):
      File "/var/lib/buildbot/slave/sage2_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 681, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/var/lib/buildbot/slave/sage2_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 1123, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.modules.free_module_integer.FreeModule_submodule_with_basis_integer.voronoi_cell[6]>", line 1, in <module>
        V.volume()           # long time
      File "sage/misc/cachefunc.pyx", line 1948, in sage.misc.cachefunc.CachedMethodCaller.__call__ (build/cythonized/sage/misc/cachefunc.c:10273)
        w = self._instance_call(*args, **kwds)
      File "sage/misc/cachefunc.pyx", line 1824, in sage.misc.cachefunc.CachedMethodCaller._instance_call (build/cythonized/sage/misc/cachefunc.c:9758)
        return self.f(self._instance, *args, **kwds)
      File "/var/lib/buildbot/slave/sage2_git/build/local/lib/python2.7/site-packages/sage/geometry/polyhedron/base.py", line 6498, in volume
        triangulation = self.triangulate(engine=engine, **kwds)
      File "/var/lib/buildbot/slave/sage2_git/build/local/lib/python2.7/site-packages/sage/geometry/polyhedron/base.py", line 3630, in triangulate
        return pc.triangulate()
      File "/var/lib/buildbot/slave/sage2_git/build/local/lib/python2.7/site-packages/sage/geometry/triangulation/point_configuration.py", line 1088, in triangulate
        return self.placing_triangulation()
      File "/var/lib/buildbot/slave/sage2_git/build/local/lib/python2.7/site-packages/sage/geometry/triangulation/point_configuration.py", line 2021, in placing_triangulation
        simplices = [frozenset(self.contained_simplex(large=True))]
      File "/var/lib/buildbot/slave/sage2_git/build/local/lib/python2.7/site-packages/sage/geometry/triangulation/point_configuration.py", line 1922, in contained_simplex
        ker = matrix(edges).right_kernel().matrix()
      File "sage/matrix/matrix2.pyx", line 4216, in sage.matrix.matrix2.Matrix.right_kernel (build/cythonized/sage/matrix/matrix2.c:29513)
        M = self.right_kernel_matrix(*args, **kwds)
      File "sage/matrix/matrix2.pyx", line 3820, in sage.matrix.matrix2.Matrix.right_kernel_matrix (build/cythonized/sage/matrix/matrix2.c:28153)
        format, M = self._right_kernel_matrix(algorithm=algorithm, proof=proof)
      File "sage/matrix/matrix_rational_dense.pyx", line 1408, in sage.matrix.matrix_rational_dense.Matrix_rational_dense._right_kernel_matrix (build/cythonized/sage/matrix/matrix_rational_dense.c:13855)
        K = A._rational_kernel_iml().transpose().change_ring(QQ)
      File "sage/matrix/matrix_integer_dense.pyx", line 3892, in sage.matrix.matrix_integer_dense.Matrix_integer_dense._rational_kernel_iml (build/cythonized/sage/matrix/matrix_integer_dense.c:31814)
        sig_on()
    SignalError: Segmentation fault
**********************************************************************
1 item had failures:
   1 of  12 in sage.modules.free_module_integer.FreeModule_submodule_with_basis_integer.voronoi_cell
    [97 tests, 1 failure, 27.71 s]
----------------------------------------------------------------------
sage -t --long src/sage/matrix/matrix_integer_dense.pyx  # MemoryError in doctesting framework
sage -t --long src/sage/modules/free_module_integer.py  # 1 doctest failed
----------------------------------------------------------------------

New commits:

0593646update FPLLL to 5.3.1 and FPYLLL to 0.5.1dev

comment:9 Changed 3 years ago by malb

I can reproduce it locally now.

comment:10 Changed 3 years ago by malb

The failures are in _solve_imp and _solve_flint when interrupted by using alarm(2), so perhaps FPLLL screws with the signal handler, somehow? Not clear what in FPLLL would, though. From the REPL it works:

sage:             sage: A = random_matrix(ZZ, 2000, 2000)
....:             sage: B = random_matrix(ZZ, 2000, 2000)
....:             sage: t0 = walltime()
....:             sage: alarm(2); A._solve_iml(B)  # long time
....:             
---------------------------------------------------------------------------
AlarmInterrupt                            Traceback (most recent call last)
<ipython-input-2-92190be6680a> in <module>()
      2 B = random_matrix(ZZ, Integer(2000), Integer(2000))
      3 t0 = walltime()
----> 4 alarm(Integer(2)); A._solve_iml(B)  # long time

/home/malb/software/sage-fplll/local/lib/python3.7/site-packages/sage/matrix/matrix_integer_dense.pyx in sage.matrix.matrix_integer_dense.Matrix_integer_dense._solve_iml (build/cythonized/sage/matrix/matrix_integer_dense.c:35877)()
   4447         try:
   4448             verbose('Calling solver n = %s, m = %s'%(n,m))
-> 4449             sig_on()
   4450             nonsingSolvLlhsMM(solu_pos, n, m, mself, mB, mp_N, mp_D)
   4451             sig_off()

AlarmInterrupt: 

Any ideas?

comment:11 Changed 2 years ago by embray

  • Milestone changed from sage-9.0 to sage-9.1

Ticket retargeted after milestone closed

comment:12 Changed 2 years ago by git

  • Commit changed from 05936462ca51aad623bd0dc12a041829fd198c7a to 8dfc58ca566b16b68eba5a174d714ec7bba32add

Branch pushed to git repo; I updated commit sha1. New commits:

6c0e664Merge branch 'master' into t/28886/update_fp_y_lll
8dfc58cupdate to fplll 5.3.2

comment:13 Changed 2 years ago by malb

  • Description modified (diff)
  • Status changed from new to needs_review

Updated FPLLL to (seemingly) fix the issue identified.

comment:14 Changed 2 years ago by tscrim

  • Status changed from needs_review to positive_review

Then positive review.

comment:15 Changed 2 years ago by vbraun

  • Branch changed from u/malb/update_fp_y_lll to 8dfc58ca566b16b68eba5a174d714ec7bba32add
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.