Opened 2 years ago

Closed 18 months ago

Last modified 18 months ago

#28777 closed enhancement (fixed)

F5 algorithm for Tate series

Reported by: caruso Owned by:
Priority: major Milestone: sage-9.1
Component: padics Keywords:
Cc: TristanVaccon, gh-ThibautVerron, roed, caruso Merged in:
Authors: Xavier Caruso, Thibaut Verron Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: e3ca91b (Commits, GitHub, GitLab) Commit: e3ca91bad987bfbed3750d1ddee7c980b6158be6
Dependencies: Stopgaps:

Status badges

Description (last modified by caruso)

This tickets implements two F5-like algorithms (called PoTe and VaPoTe respectively) for computing Gröbner bases over Tate algebras.

Change History (41)

comment:1 Changed 2 years ago by caruso

  • Branch set to u/caruso/F5_Tate

comment:2 Changed 2 years ago by git

  • Commit set to 95dc92cbd17f23b44d5d4a531e9fd5defbe88552

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

95dc92cmake things compile and add verbosity

comment:3 Changed 23 months ago by gh-ThibautVerron

  • Branch changed from u/caruso/F5_Tate to u/gh-ThibautVerron/F5_Tate

comment:4 Changed 23 months ago by git

  • Commit changed from 95dc92cbd17f23b44d5d4a531e9fd5defbe88552 to 229a95eaebbe86e62da384e7dcae5988b8a0ef81

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

229a95eBugfix: incorrect signature comparison in vopot reduction

comment:5 Changed 23 months ago by caruso

  • Branch changed from u/gh-ThibautVerron/F5_Tate to u/caruso/F5_Tate

comment:6 Changed 23 months ago by gh-ThibautVerron

  • Branch changed from u/caruso/F5_Tate to u/gh-ThibautVerron/F5_Tate

comment:7 Changed 23 months ago by caruso

  • Branch changed from u/gh-ThibautVerron/F5_Tate to u/caruso/F5_Tate

comment:8 Changed 22 months ago by gh-ThibautVerron

  • Branch changed from u/caruso/F5_Tate to u/gh-ThibautVerron/F5_Tate

comment:9 Changed 22 months ago by caruso

  • Branch changed from u/gh-ThibautVerron/F5_Tate to u/caruso/F5_Tate

comment:10 Changed 22 months ago by embray

  • Milestone changed from sage-9.0 to sage-9.1

Ticket retargeted after milestone closed

comment:11 Changed 21 months ago by git

  • Commit changed from 229a95eaebbe86e62da384e7dcae5988b8a0ef81 to 06b95ce8b22eb44716805824ae98a1d279c74156

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

0ed8a9aMerge branch 'F5_Tate' into F5Tate
06b95cecythonize regular_reduce and reduce

comment:12 Changed 21 months ago by gh-ThibautVerron

  • Branch changed from u/caruso/F5_Tate to u/gh-ThibautVerron/F5_Tate

comment:13 Changed 21 months ago by git

  • Commit changed from 06b95ce8b22eb44716805824ae98a1d279c74156 to 4bf843d3600b1b62a90e12ee98da8dfa780b2353

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

4bf843dFix ValueError for pot with zero ideal

comment:14 Changed 21 months ago by git

  • Commit changed from 4bf843d3600b1b62a90e12ee98da8dfa780b2353 to 3f710b12aba74ed35142dfcdf87c4058a0afaee0

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

3f710b1Fix pot for zero ideal

comment:15 Changed 21 months ago by git

  • Commit changed from 3f710b12aba74ed35142dfcdf87c4058a0afaee0 to 6a3d8db3e43a8fc1323d2e94a658bbe20668a358

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

6a3d8dbFix lshift

comment:16 Changed 21 months ago by git

  • Commit changed from 6a3d8db3e43a8fc1323d2e94a658bbe20668a358 to b409ee63c3d68bd0e0e74b292f3ae863609fc2e3

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

b409ee6Fix F5 pot

comment:17 Changed 21 months ago by chapoton

The patchbot "blocks" plugin tells you to avoid finishing a line with space then :. There should be no space before the final :.

comment:18 Changed 21 months ago by git

  • Commit changed from b409ee63c3d68bd0e0e74b292f3ae863609fc2e3 to 53677d8bc8397232d94e55cd31e572abedf13b88

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

53677d8Division and reduction by monic elements

comment:19 Changed 21 months ago by git

  • Commit changed from 53677d8bc8397232d94e55cd31e572abedf13b88 to 62f9ff574e942f063f63ce83e4618b4cdca4a9f2

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

62f9ff5Added flags for interrupting reductions in vopot

comment:20 Changed 21 months ago by git

  • Commit changed from 62f9ff574e942f063f63ce83e4618b4cdca4a9f2 to 8e94028cd7aefe7d4b07fb7b25c0699a1082c1b2

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

8e94028Passing flags

comment:21 Changed 21 months ago by caruso

  • Branch changed from u/gh-ThibautVerron/F5_Tate to u/caruso/F5_Tate

comment:22 Changed 21 months ago by gh-ThibautVerron

  • Branch changed from u/caruso/F5_Tate to u/gh-ThibautVerron/F5_Tate

comment:23 Changed 21 months ago by caruso

  • Branch changed from u/gh-ThibautVerron/F5_Tate to u/caruso/F5_Tate

comment:24 Changed 19 months ago by git

  • Commit changed from 8e94028cd7aefe7d4b07fb7b25c0699a1082c1b2 to 49567f912322d2892242c703789b0e5972508984

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

677704dMerge branch 'u/caruso/F5_Tate' of git://trac.sagemath.org/sage into F5Tate
49567f9clean up code and add doctests

comment:25 Changed 19 months ago by caruso

  • Authors set to Xavier Caruso, Thibaut Verron
  • Cc roed added
  • Status changed from new to needs_review

Ticket ready for review.

comment:26 Changed 19 months ago by chapoton

Patchbot will complain about space before colon here:

+                if vv == 0 :

Did you ever look at the previous patchbot reports ?

comment:27 Changed 19 months ago by git

  • Commit changed from 49567f912322d2892242c703789b0e5972508984 to 86fd3f5354a1fb42c9e66c8fe4de83d8b516b77a

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

86fd3f5add references

comment:28 Changed 19 months ago by git

  • Commit changed from 86fd3f5354a1fb42c9e66c8fe4de83d8b516b77a to 7f2dec6e465d2af68519a799447f745e4bb7303e

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

7f2dec6remove space before colon

comment:29 Changed 19 months ago by caruso

  • Cc caruso added
  • Type changed from task to enhancement

comment:30 Changed 18 months ago by caruso

  • Description modified (diff)

comment:31 Changed 18 months ago by caruso

  • Description modified (diff)

comment:32 Changed 18 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.2

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

comment:33 Changed 18 months ago by git

  • Commit changed from 7f2dec6e465d2af68519a799447f745e4bb7303e to 29434e61ea8be51effb69e7eb399eda422d37a3c

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

0ffee86Merge branch 'u/caruso/F5_Tate' of git://trac.sagemath.org/sage into F5_Tate
29434e6implement a method for picking a single coefficient

comment:34 follow-up: Changed 18 months ago by tscrim

This doesn't make sense for a class level docstring:

Initialize a class for ideals in a Tate series algebra

Did you mean An ideal in a Tate series algebra?

For the result of the Gröbner basis, perhaps we should cache that where we disregard the algorithm (and keywords) used?

You can remove the TESTS:: block in Jpair. Also, would it make sense to inline that?

Instead of int i, I have been told it is better to use Py_ssize_t i as this can have a larger range of possible values.

Nitpick:

-    - ``I`` - an ideal in a Tate series algebra
+    - ``I`` -- an ideal in a Tate series algebra
 
-    - ``prec`` - the related precision at which the initial generators
+    - ``prec`` -- the related precision at which the initial generators
       are truncated

Also, the convention that we follow in Sage is that the one-line start of docstrings should end with a period/full-stop.

comment:35 Changed 18 months ago by git

  • Commit changed from 29434e61ea8be51effb69e7eb399eda422d37a3c to 671a93d359c12b395f77e2d571beacf575ab9394

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

671a93dfix typos in doctests

comment:36 in reply to: ↑ 34 ; follow-up: Changed 18 months ago by caruso

Replying to tscrim:

For the result of the Gröbner basis, perhaps we should cache that where we disregard the algorithm (and keywords) used?

I'm not sure: if the user specifies explicitely another algorithm, maybe it means that he really wants to use it and not to get a cached value.

comment:37 in reply to: ↑ 36 Changed 18 months ago by tscrim

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

Replying to caruso:

Replying to tscrim:

For the result of the Gröbner basis, perhaps we should cache that where we disregard the algorithm (and keywords) used?

I'm not sure: if the user specifies explicitely another algorithm, maybe it means that he really wants to use it and not to get a cached value.

Hmm...perhaps it would give a different answer as it might not be be a reduced Gröbner basis. Okay, then let's leave it as uncached. Thanks.

comment:38 Changed 18 months ago by gh-ThibautVerron

  • Branch changed from u/caruso/F5_Tate to u/gh-ThibautVerron/F5_Tate

comment:39 Changed 18 months ago by gh-ThibautVerron

  • Commit changed from 671a93d359c12b395f77e2d571beacf575ab9394 to e3ca91bad987bfbed3750d1ddee7c980b6158be6

In the latest commit, we removed a test which was a debug relic. This if branch is never entered and the debug content would pose problems if it were.


New commits:

e3ca91bRemoved useless test

comment:40 Changed 18 months ago by vbraun

  • Branch changed from u/gh-ThibautVerron/F5_Tate to e3ca91bad987bfbed3750d1ddee7c980b6158be6
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:41 Changed 18 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.1
Note: See TracTickets for help on using tickets.