Opened 7 years ago

Closed 6 years ago

#13850 closed enhancement (fixed)

PolynomialSequence.solve()

Reported by: malb Owned by: malb
Priority: major Milestone: sage-6.1
Component: commutative algebra Keywords:
Cc: Bouillaguet, cosh Merged in:
Authors: Charles Bouillaguet Reviewers: Martin Albrecht
Report Upstream: N/A Work issues:
Branch: u/Bouillaguet/ticket/13850 (Commits) Commit: 02a4a872c173eb89f56b5d9b5dbcd8ba2a6a54c4
Dependencies: #13162,#13964,#13965,#13968,#13976,#13977 Stopgaps:

Description (last modified by malb)

Polynomial sequences over GF(2) should have a solve method which supports solving via

  • Gröbner bases (PolyBoRi)
  • SAT solving (CryptoMiniSat and friends)
  • exhaustive search (FES library)
  • (Mixed Integer Programming) (Sage's MIP stuff and SCIP)

All these interfaces exist, they only need to be properly exposed.

Attachments (1)

13850_boolean_solve.patch​ (8.8 KB) - added by Bouillaguet 7 years ago.

Download all attachments as: .zip

Change History (29)

comment:1 Changed 7 years ago by malb

  • Description modified (diff)

comment:2 Changed 7 years ago by ncohen

(just being curious)

comment:3 Changed 7 years ago by Bouillaguet

  • Dependencies set to #13162

+1 !

comment:4 Changed 7 years ago by Bouillaguet

  • Dependencies changed from #13162 to #13162,#13964,#13965,#13968
  • Milestone changed from sage-5.6 to sage-5.7

comment:5 Changed 7 years ago by Bouillaguet

  • Dependencies changed from #13162,#13964,#13965,#13968 to #13162,#13964,#13965,#13968,#13976

comment:6 Changed 7 years ago by Bouillaguet

  • Dependencies changed from #13162,#13964,#13965,#13968,#13976 to #13162,#13964,#13965,#13968,#13976,13977

comment:7 Changed 7 years ago by Bouillaguet

I am submitting a patch, but it is not ready for review. There is (at least) a problem with eliminate_linear_variables=True, but it should work fine when this is false...

I welcome any comments ;)

comment:8 Changed 7 years ago by Bouillaguet

  • Authors set to Charles Bouillaguet
  • Dependencies changed from #13162,#13964,#13965,#13968,#13976,13977 to #13162,#13964,#13965,#13968,#13976,#13977

Changed 7 years ago by Bouillaguet

comment:9 Changed 7 years ago by Bouillaguet

  • Status changed from new to needs_review

This time it means business

comment:10 Changed 7 years ago by malb

Patch looks good, I haven't installed it yet though (gosh, those are a lot of dependencies!). We should have a solve() for generic polynomial sequences as well, not only for GF(2). I guess for GF(2^e) we can offer at least two options: solve() via GB or solve via weil restriction and solving over GF(2).

comment:11 Changed 7 years ago by Bouillaguet

I think that the piece of code that eliminates variables occurring linearly could part of the most general solve() (where only GB would be possible...). Then in the subclasses, there could be other possible algorithms, such as SAT, etc.

comment:12 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:13 Changed 7 years ago by Bouillaguet

  • Branch set to u/Bouillaguet/ticket/13850

comment:14 Changed 7 years ago by malb

  • Reviewers set to Martin Albrecht
  • Status changed from needs_review to needs_work

Very nice! But the optional arguments are not correct: 

./sage -t --show-skipped multi_polynomial_sequence.py

i.e. the "needs" is incorrect.

comment:15 Changed 7 years ago by Bouillaguet

  • Commit set to 4daab78ad359d500b6a264708a30cafdbeb2a03e
  • Status changed from needs_work to needs_review

comment:16 Changed 7 years ago by malb

  • Status changed from needs_review to positive_review

Excellent: 

./sage -t --show-skipped --optional=magma,sage,cryptominisat,fes ./src/sage/rings/polynomial/multi_polynomial_sequence.py
...
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------

./sage -t --show-skipped ./src/sage/rings/polynomial/multi_polynomial_sequence.py
...
    1 cryptominisat test not run
    1 fes test not run
    1 magma test not run
    [181 tests, 4.56 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------

comment:17 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.13 to sage-6.0

comment:18 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.0 to sage-6.1

comment:19 Changed 6 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:20 Changed 6 years ago by ncohen

Hmmmm.... This ticket's message seems to say that LP solvers are made available through the solve() method, but it does not seem to appear in the doc, nor in the code O_o

Nathann

comment:21 Changed 6 years ago by malb

  • Description modified (diff)

comment:22 Changed 6 years ago by ncohen

Oh. That settles it :-D

Nathann

comment:23 Changed 6 years ago by vbraun

  • Resolution fixed deleted
  • Status changed from closed to new

Sage crashes on startup with this ticket

comment:24 Changed 6 years ago by git

  • Commit changed from 4daab78ad359d500b6a264708a30cafdbeb2a03e to 02a4a872c173eb89f56b5d9b5dbcd8ba2a6a54c4

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

​02a4a87bug fix : importing BooleanPolynomialRing at the top-level prevents sage from starting
​6c846edMerge branch 'master' into 13850

comment:25 Changed 6 years ago by Bouillaguet

  • Status changed from new to needs_review

I fixed the problem. Somehow importing BooleanPolynomialRing at the top level is no longer possible. I have no clue why

comment:26 Changed 6 years ago by vbraun

Its pretty clear that BooleanPolynomialRing imports multi_polynomial_sequence, so if multi_polynomial_sequence also imports BooleanPolynomialRing then you have a circular import.

comment:27 Changed 6 years ago by Bouillaguet

Alright, but this used to be working (otherwise I suspect that malb wouldn't have given the positive review). Thus, I understand that BooleanPolynomialRing? imported multi_polynomial_sequence somewhere between 5.13 and 6.1

comment:28 Changed 6 years ago by vbraun

  • Resolution set to fixed
  • Status changed from needs_review to closed
Note: See TracTickets for help on using tickets.