Singular
https://www.singular.uni-kl.de/forum/

Monomial ordering with components
https://www.singular.uni-kl.de/forum/viewtopic.php?f=10&t=2950		 Page 1 of 1
Author:  kelvin [ Thu May 20, 2021 2:25 am ]
Post subject:  Monomial ordering with components
I would like to make some modifications to the library to test out an idea.
Most things I've been able to figure out by looking at other sections of the code, but I am having trouble understanding how the monomial ordering works when dealing with syzygy components.

In idLiftStd it makes a new ring to allow calculating syzygies and/or tracing how the computed ideal relates to the initial ideal.
For example my ring initially looks like (printed using "rWrite(currRing, TRUE)" )
Code:
// coefficients: QQ
// number of vars : 54
//        block   1 : ordering dp
//                  : names    w0100 w0101 w0102 w0110 w0111 w0112 w0120 w0121 w0122 w0200 w0201 w0202 w0210 w0211 w0212 w0220 w0221 w0222 w0300 w0301 w0302 w0310 w0311 w0312 w0320 w0321 w0322 w1200 w1201 w1202 w1210 w1211 w1212 w1220 w1221 w1222 w1300 w1301 w1302 w1310 w1311 w1312 w1320 w1321 w1322 w2300 w2301 w2302 w2310 w2311 w2312 w2320 w2321 w2322
//        block   2 : ordering C

Then before calling idPrepare the ring is changed to:
Code:
// coefficients: QQ
// number of vars : 54
//        block   1 : ordering s syz_comp: 1
//        block   2 : ordering dp
//                  : names    w0100 w0101 w0102 w0110 w0111 w0112 w0120 w0121 w0122 w0200 w0201 w0202 w0210 w0211 w0212 w0220 w0221 w0222 w0300 w0301 w0302 w0310 w0311 w0312 w0320 w0321 w0322 w1200 w1201 w1202 w1210 w1211 w1212 w1220 w1221 w1222 w1300 w1301 w1302 w1310 w1311 w1312 w1320 w1321 w1322 w2300 w2301 w2302 w2310 w2311 w2312 w2320 w2321 w2322
//        block   3 : ordering C


This change appears to make the monomial ordering first group by component if the component is 1, then order by dp.
For example I see a polynomial ordered like this:
Code:
w0312*w1322*w2322*gen(1)+w0302*w1302*w2300*gen(55)-w0312*w1302*w2300*gen(28)-w0302*w1322*w2300*gen(37)+w0312*w1322*w2300*gen(10)+w0302*w1300*w2302*gen(55)-w0312*w1300*w2302*gen(28)+w0300*w1302*w2302*gen(55)+w0302*w1302*w2302*gen(53)-w0310*w1302*w2302*gen(28)-w0312*w1302*w2302*gen(26)-w0302*w1320*w2302*gen(37)+w0312*w1320*w2302*gen(10)-w0300*w1322*w2302*gen(37)-w0302*w1322*w2302*gen(35)+w0310*w1322*w2302*gen(10)+w0312*w1322*w2302*gen(8)-w0302*w1302*w2320*gen(49)+w0312*w1302*w2320*gen(22)+w0302*w1322*w2320*gen(31)-w0312*w1322*w2320*gen(4)-w0302*w1300*w2322*gen(49)+w0312*w1300*w2322*gen(22)-w0300*w1302*w2322*gen(49)-w0302*w1302*w2322*gen(47)+w0310*w1302*w2322*gen(22)+w0312*w1302*w2322*gen(20)+w0302*w1320*w2322*gen(31)-w0312*w1320*w2322*gen(4)+w0300*w1322*w2322*gen(31)+w0302*w1322*w2322*gen(29)-w0310*w1322*w2322*gen(4)-w0312*w1322*w2322*gen(2)


To test my understanding (and make the output a bit nicer to read), I tried to change this to order by all syzygy components first, then order by dp between terms with the same syzygy component.
So in the example above, this would place the multiple terms with gen(4) next to each other in the ordering.

Based on how the new ring is setup in the code, as a quick manual test I tried inserting the following right before the call to idGroebner in idPrepare:
Code:
    rSetSyzComp(82, currRing);
    rChangeCurrRing(currRing); // updates some globals

The ring does show a change:
Code:
// coefficients: QQ
// number of vars : 54
//        block   1 : ordering s syz_comp: 82
//        block   2 : ordering dp
//                  : names    w0100 w0101 w0102 w0110 w0111 w0112 w0120 w0121 w0122 w0200 w0201 w0202 w0210 w0211 w0212 w0220 w0221 w0222 w0300 w0301 w0302 w0310 w0311 w0312 w0320 w0321 w0322 w1200 w1201 w1202 w1210 w1211 w1212 w1220 w1221 w1222 w1300 w1301 w1302 w1310 w1311 w1312 w1320 w1321 w1322 w2300 w2301 w2302 w2310 w2311 w2312 w2320 w2321 w2322
//        block   3 : ordering C

However, the polynomials created during the groebner calculation still have the same monomial ordering as before.
I am clearly misunderstanding something.
How do I specify the ring to order by all syzygy components first, then dp for comparing between monomials with the same component?

I am also confused about intention regarding the syz_comp parameter being different in various objects during a groebner calculation (the ring reports syz_comp = 1, while the slimgb algorithm has syz_comp = 82, and various function have syz_comp parameters which are sometimes 1 and sometimes 82). So likely there are multiple meanings being given to "syz_comp" that depend on context. So any clarification would be appreciated.

(I've already been able to greatly speed up some large liftstd calculations, but my changes are quite hacky at the moment, so I'm trying to get a better understanding of how to do things as the code design intended.)
Author:  kelvin [ Thu May 20, 2021 3:04 am ]
Post subject:  Re: Monomial ordering with components
By making the initial ring use ordering (C,dp), then the idLiftStd syzygy ring will group by component nicely.
But the first component is still treated differently than the others, regardless of what I set syz_comp to.
(It orders 1, then 82,81,80,... 2)
So there is still something I am not understanding here about how the syz_comp settings work.
Author:  hannes [ Tue May 25, 2021 10:37 am ]
Post subject:  Re: Monomial ordering with components
The syz_comp ordering influences only comparisons m_1*gen(i) with m_2*gen(j) where
i<=syz_comp and j>syz_comp (m_1*gen(i) is the leading term in this case).
Everything else is ordered by the other ordering blocks.
The algorithm REQUIRES that terms in component <=syz_comp are larger than
terms with component > syz_comp.(Elimination ordering for these components).
Setting syz_comp to other values gives in general faster but wrong results.
Author:  kelvin [ Wed May 26, 2021 4:43 am ]
Post subject:  Re: Monomial ordering with components
The monomial ordering questions are unrelated to the speedup I mentioned (I was not modifying the monomial ordering when speeding up the algorithm). I was trying to better understand why syz_comp in different structures are different values during the same computation. I guess that doesn't matter now.

Anyway, I achieved significant speed up of liftstd (when syzygies are not needed) by calculating only the part of the groebner basis with gen(1) in the leading order. There are also some calculations used to sort/prioritize which pairs to work on based on length, and I changed this to only count the number of monomials with gen(1). As another speed up, I also detected if the leading monomial is a constant*gen(1), as this means we can exit early as this will be the only term in the resulting greobner basis after the gen(i) are removed. The liftstd calculation was of course still slower and more memory intensive than just doing slimgb, because the polynomials now are carrying around extra monomials which hold the information of how they relate to the original basis. However with these changes the liftstd calculation now follows the same sequence of progress as slimgb alone. This was what I was hoping for in the other thread.

Basically, liftstd was still doing all the effort for calculating the syzygies even when they were not wanted. Removing that speeds things up significantly.
Author:  hannes [ Wed May 26, 2021 11:24 am ]
Post subject:  Re: Monomial ordering with components
To which version of Singular are you refering?
There were improvements in liftstd in version 4.2.0p2.
- syzygies were not computed if not needed (already in 4.2.0, if std is used)
- possible to select slimgb or std as Groebner base algorithm (already in 4.2.0)
- lazy computation of transformation matrix (only if syzygies are not needed and std used), new in 4.2.0p2
Author:  kelvin [ Wed May 26, 2021 6:53 pm ]
Post subject:  Re: Monomial ordering with components
I started from the github version (commit c2763fb4965b5f644ed27a9797f11dabc3d3f6fc), and modified from there.

In the github version, when using slimgb in liftstd the code would still do the work of calculating the syzygies, even if it dropped those results later. This can be seen by printing out the polynomials being collected in the "while(i < max_pairs)" loop of "void go_on (slimgb_alg * c)" in file "kernel/GBEngine/tgb.cc", or by dumping the c->S->m[i] to see the current status after each go_on call in "do_t_rep_gb". So I made some changes as mentioned in my last post, to do my best to remove that extra work and sort the pairs in a similar way. I don't understand the code well enough to know the "appropriate" place for many of the changes, but after the changes the prot output from a slimgb(I) would be similar to liftstd(I, T, "slimgb"), so the strategies appears to match now.
Author:  hannes [ Thu May 27, 2021 11:53 am ]
Post subject:  Re: Monomial ordering with components
Sounds interesting as all of the improvements I mentioned uses std.
Can you provide a link to your modifications or create a pull request?
Page 1 of 1 All times are UTC + 1 hour [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/