Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improved Buchberger algorithm #6

Open
fredrik-johansson opened this issue Oct 1, 2020 · 0 comments
Open

Improved Buchberger algorithm #6

fredrik-johansson opened this issue Oct 1, 2020 · 0 comments

Comments

@fredrik-johansson
Copy link
Collaborator

fredrik-johansson commented Oct 1, 2020

On the buchberger2 branch (commit a7caebe) is an attempt to implement the improved Buchberger algorithm GRÖBNERNEW2, p. 232 in Becker and Weispfenning. For some reason I can't figure out, it's not working as intended; random input quickly runs into cases where it slows down drastically while the ordinary Buchberger performs fine. Something like build/examples/dft -input 3 16 breaks.

At first I thought this was just due to randomness in the pair selection, but GRÖBNERNEW2 looks systematically worse, which shouldn't be the case. SymPy has an implementation of GRÖBNERNEW2 (https://github.com/sympy/sympy/blob/master/sympy/polys/groebnertools.py) and seems to do fine on a handful of examples I've tried manually.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant