Opened 10 years ago
Closed 9 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, GitHub, GitLab) | Commit: | 02a4a872c173eb89f56b5d9b5dbcd8ba2a6a54c4 |
Dependencies: | #13162,#13964,#13965,#13968,#13976,#13977 | Stopgaps: |
Description (last modified by )
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)
Change History (29)
comment:1 Changed 10 years ago by
- Description modified (diff)
comment:2 Changed 10 years ago by
comment:4 Changed 10 years ago by
- Dependencies changed from #13162 to #13162,#13964,#13965,#13968
- Milestone changed from sage-5.6 to sage-5.7
comment:5 Changed 10 years ago by
- Dependencies changed from #13162,#13964,#13965,#13968 to #13162,#13964,#13965,#13968,#13976
comment:6 Changed 10 years ago by
- Dependencies changed from #13162,#13964,#13965,#13968,#13976 to #13162,#13964,#13965,#13968,#13976,13977
comment:7 Changed 10 years ago by
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 10 years ago by
- Dependencies changed from #13162,#13964,#13965,#13968,#13976,13977 to #13162,#13964,#13965,#13968,#13976,#13977
Changed 10 years ago by
comment:9 Changed 10 years ago by
- Status changed from new to needs_review
This time it means business
comment:10 Changed 10 years ago by
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 10 years ago by
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 9 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:13 Changed 9 years ago by
- Branch set to u/Bouillaguet/ticket/13850
comment:14 Changed 9 years ago by
- 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 9 years ago by
- Commit set to 4daab78ad359d500b6a264708a30cafdbeb2a03e
- Status changed from needs_work to needs_review
comment:16 Changed 9 years ago by
- 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 9 years ago by
- Milestone changed from sage-5.13 to sage-6.0
comment:18 Changed 9 years ago by
- Milestone changed from sage-6.0 to sage-6.1
comment:19 Changed 9 years ago by
- Resolution set to fixed
- Status changed from positive_review to closed
comment:20 Changed 9 years ago by
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 9 years ago by
- Description modified (diff)
comment:22 Changed 9 years ago by
Oh. That settles it :-D
Nathann
comment:23 Changed 9 years ago by
- Resolution fixed deleted
- Status changed from closed to new
Sage crashes on startup with this ticket
comment:24 Changed 9 years ago by
- Commit changed from 4daab78ad359d500b6a264708a30cafdbeb2a03e to 02a4a872c173eb89f56b5d9b5dbcd8ba2a6a54c4
comment:25 Changed 9 years ago by
- 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 9 years ago by
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 9 years ago by
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 9 years ago by
- Resolution set to fixed
- Status changed from needs_review to closed
(just being curious)