Comments (12)
I think I messed up git, so the issue got closed automatically π
.
Reopening now
from groebner.jl.
Hi @jpcurbelo. I have looked at the issue, the problem is that in F4 algorithm we don't limit the maximum number of critical pairs that can be handled at the same time, rather strangely though
I am at it ( #64 ), but haven't figured out the best fix yet. Will try again this weekend. Sorry for this taking so long
from groebner.jl.
Hi @sumiya11! Many thanks. Your efforts are highly appreciated. I will take a look at the updates and materials you mentioned. I'll keep my finger crossed so you can find time to work on reducing the memory footprint. Once again, thank you so much. Your package has already helped me with other problems as well.
from groebner.jl.
Hi @jpcurbelo , thanks for sharing this interesting system!
I'll have a look. At first glance, I think we don't compress monomials here, but we totally should
from groebner.jl.
You mentioned that you also have smaller similar systems. If you expect those to have a "similar" groebner basis as this large one, feel free to share the small systems as well, it will perhaps help
from groebner.jl.
Hi @sumiya11. Thanks for your quick response. In fact, the system for RK(s=8, p=7) doesn't have a solution - that's what I expected to obtain from this.
For example, RK(s=4, p=4) has a solution (multiple solutions, in fact) and I got this Grobner basis.
On the other hand, RK(s=6, p=6) doesn't have a solution, and the groebner(system)
gives us {"groebner_basis":["1"]}
. From what I've understood, this means no Groebner basis (no solution), right?
Please, let me know if I didn't make myself clear enough :)
Thanks again!
from groebner.jl.
Hey @sumiya11. I was wondering if you have had the time to look at this issue (a significant amount of memory RAM is required for specific problems). Please, let me know if you think there is something I could (try to) do on my end to somehow improve the performance of the jobs I'm running. Many thanks for your efforts!
from groebner.jl.
Hi @jpcurbelo , so there is good news and bad news:
- Good news is that
groebner
now has themaxpairs
keyword argument, which can be used to limit the matrix size in the internal F4 implementation. It is available in the latest Groebner.jl version.
For example, ifsystem
is RK(s=6, p=6) that you have kindly provided, thengroebner(system, maxpairs=1000)
should allocate a bit less than the baseline. - Bad news is that the big RK(s=8, p=7) is still not tractable. A complication is that we don't know the optimal values for
maxpairs
(it's tricky to control the matrix size in F4), and for smallmaxpairs
the computation expectedly becomes much-much slower.
On my machine, while computing RK(s=8, p=7) with maxpairs=500
, the process allocates 100 GB of RAM before it gets killed.
I have experimented with other values for maxpairs
, but seemingly to no avail π .
The commands std
and slimgb
from Singular are not competitive on RK(s=6, p=6), so I haven't checked them on the bigger system.
The Groebner
command in Maple reports Error, (in Groebner:-Basis) Segmentation Violation occurred in external routine
after using up around 25 GB of RAM (I used this Maple script).
I will work on reducing the overall memory footprint of Groebner.jl this summer, but I think at the moment Groebner.jl unfortunately cannot tackle such systems
from groebner.jl.
As a sidenote, if you do not care about the basis monomial ordering, you can explicitly set it to DegRevLex()
. Usually, it is more efficient than the default one:
# system is RK(s=6, p=6)
@time groebner(system);
# 258.834883 seconds (661.72 M allocations: 154.943 GiB, 5.61% gc time)
# Max. RAM: 9100.656 MiB
@time groebner(system, ordering=DegRevLex());
# 28.632552 seconds (7.53 M allocations: 2.620 GiB, 2.63% gc time)
# Max. RAM: 1676.414 MiB
@time groebner(system, ordering=DegRevLex(), maxpairs=1000);
# 12.556571 seconds (6.62 M allocations: 1.900 GiB, 4.33% gc time)
# Max. RAM: 1574.133 MiB
from groebner.jl.
I think there is a chance that incremental signature GB algorithms can deal with these problems (e.g., https://www.singular.uni-kl.de/Manual/4-0-3/sing_391.htm). I'll check if I can make it work via Singular.jl
from groebner.jl.
@jpcurbelo
I wonder if there is a simple way to describe how the system is formed?
The reason I am asking is that, from the shape of polynomials, it looks like the process involves some substitutions. In my experience, it is sometimes better not to perform all the substitution but keep extra variables and relations (for example, if you would like to replace c
with a + b
, you can just add c - a - b
to the system).
from groebner.jl.
Hi @pogudingleb. I don't think there is a simple way to describe how the systems are formed but you are right, there are key substitutions involved.
The systems are basically based on Butcher's Tableu (see the image) and, as we might see, the c terms are not in the systems based on the substitutions:
That's a good hint. I'll try to generate the systems without the substitutions and will generate the systems without tl let you know how it went.
from groebner.jl.
Related Issues (20)
- Fails to compute correct GrΓΆbner basis on DynamicPolynomials variable with non-standard monomial ordering HOT 7
- Many invalidations
- groebner does not return leading coefficient 1 HOT 6
- Calculate transformation matrix HOT 9
- Reduce a Polynomial by a Groebner Basis HOT 2
- FindInstance and boolean minimization HOT 9
- Julia 1.6 support HOT 2
- Integer Type Error HOT 1
- Error with `hashnextindex(::UInt32, ::Int64, ::UInt32)` HOT 3
- Compute basis in parallel HOT 19
- Groebner Basis with parameters HOT 2
- Computing bases up to some degree
- RecoverableException in Groebner\to18i\src\interface.jl:100 HOT 3
- Possible to make Groebner.jl support 32bit Julia? HOT 1
- Bug in `groebner` in Z_2 HOT 1
- Issues with `normalform` HOT 4
- Huge amount of dynamic dispatch HOT 2
- Does Groebner use checked arithmetic, or does it fail silently if a coefficient overflows? HOT 2
- exponent vector overflow, restarting HOT 8
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
π Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. πππ
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google β€οΈ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from groebner.jl.