Opened 14 years ago
Last modified 13 years ago
#165 new proposed feature
Wishlist: SCA TODOs
Reported by: | Oleksandr | Owned by: | Oleksandr |
---|---|---|---|
Priority: | major | Milestone: | 3-1-1 |
Component: | singular-kernel | Version: | 3-1-0 |
Keywords: | sca, nc, wish | Cc: | hannes@…, simon.king@… |
Description
Thanks to Simon, here are some non-commutative requests due to from http://groups.google.com/group/sage-devel/browse_thread/thread/497bfc40ea5f17b8?pli=1
From http://groups.google.com/group/sage-devel/msg/1b183a717dbd0437
I need graded commutative rings, which can be easily constructed, provided that one has * Singular's "SuperCommutative" rings * additional degree vectors (resp. matrix orderings where the first matrix row is interpreted as degree vector). SuperCommutative provides precisely one block of variables that pairwise anticommute. However, it would be even nicer to have rings with several anticommuting blocks. I could imagine to create it (with additional degree vector) like that: sage: R.<a,b,c,d,e,f> = PolynomialRing(QQ, nc_blocks=[[0,1],[3,5]], degrees=[1,1,2,3,3,3]) Then, R should be a graded commutative ring: two generators in degrees 1, one in degree 2, and three in degree 3, and the nc_blocks determine that variables a,b,d,e,f are pairwise anti-commuting. If only one anticommutative block is possible, then it could be: sage: R.<c,a,b,d,e,f> = PolynomialRing(QQ, nc_block=[1,5], degrees= [2,1,1,3,3,3])
AFAIK: more than one block of odd variables can be avoided by reordering the variables and changing the ordering accordingly. It makes sense to allow more than one block of odd variables, e.g. due to more complicated resulting ordering...
Simon, is there something else to it? How would your ordering look like without the reordering?
From http://groups.google.com/group/sage-devel/msg/99e803cb4a127bc8
AFAIK, the Singular kernel has a marker for functions that are only available in the commutative case. I think it would be nice to distinguish not two but three cases: commutative, supercommutative, and general G-algebras. This suggestion comes from the observation that many algorithms for commutative rings work in the supercommutative (or graded commutative) setting as well, but Singular refuses them since they would not work for general G-algebras. Therefore, in my applications I had in some cases to work around and implement these algorithms as library functions. * Kernel/preimage of maps * Hilbert polynomial/function: This certainly makes sense for (weighted) homogeneous ideals in graded commutative rings. * AFAIK dim (Krull dimension) makes sense in the graded commutative case as well. * Hilbert driven standard basis computation
Simon, could you please provide us with some more input? It would be nice to have tests with known correct results and to make your workarounds check the correctness automatically. Moreover, references to corresponding definitions in literature are much appreciated.
From http://groups.google.com/group/sage-devel/msg/1b8f6205ba9ebab8
After all, testing for complicated conditions under which a function works costs time. So, why not have a very simple test (commutative vs. non-commutative) that is immediate? Therefore my suggestion to have markers, say ALLOW_G_ALGEBRA, ALLOW_SC_ALGEBRA, NO_PLURAL.
ps: my comments on this suggestion are in the original thread.
Hans, what do you think?
Attachments (1)
Change History (5)
comment:1 follow-up: 2 Changed 13 years ago by
comment:2 follow-up: 3 Changed 13 years ago by
Dear Viktor,
first of all, my apologies for answering so late. When you posted, I was busy with different things, and later I forgot to reply.
Replying to levandov:
1. ALLOW THINGS VERSUS CONTEXTS
Hmmm... A long time ago there was a discussion about context-dependent functionality of a given function.
Testing whether some operation is allowed in a certain context should of course be a fast decision.
ALLOW list is definitely a solution, but having many of them is not easy to maintain.
But at least in the graded commutative case, ALLOW can already be updated when the ring is created. So, for all subsequent operations, the decision will be fast.
Example: given the relation yx=xy+z, then {x,y} needs to be completed to {x,y,z} (note that this is NOT the case for graded commutative algebras). In many cases, however, one gets smaller subalgebras. Then a procedure will analyze the type of this context subalgebra (it's done internally) and make its decision. I like the idea of being able to factorize a univariate polynomial while sitting in any ring.
I wonder how general the approach should be.
My question: Is the data type in Singular for a general G-Algebra different from the data type for a SuperCommutative? ring? I guess so, since IIRC basic arithmetic for SuperCommutative? rings is much faster than for general G-Algebras.
If this is the case, then why not implement the features for that data type only? The test whether some operation is allowed will then usually boil down to the question whether an ideal is (weighted) homogeneous.
2. Recipe for Krull dimension in graded commutative case
... In the implementation in gkdim.lib, however, one does not add the dimension of the field to the result, so they are equal.)
gkdim.lib? I didn't know that library, so, I will look in the manual. Thank you!
3. Preimage
There's PLURAL kernel command preimage, which has some limitations.
Really? preimage is throwing an error when using it on graded commutative (quotient) rings.
Send me (or post here or somewhere and give me a link) the example of possible morphisms. I think for the graded comm case you'll be in the easiest case, where no severe restrictions of the general case apply. So this might be quite doable.
I have put some examples in folders here.
Remarks:
- The folder 'Exp_n_' contains data that occur when computing persistent group cohomology associated with the upper central series (Theoretical Background) of SmallGroup? number 'n' of order 81, provided that the upper central series is interesting.
- Each file in such subfolder defines two graded-commutative quotient rings Q1 and Q2, with matrix ordering, and a map phi between them. I need the kernel of phi.
- If I am not mistaken (at least this is what I do in my custom implementation), the usual procedure works in this setting: Let phi:Q1->Q2 be a homomorphism of graded commutative algebras. We consider R=Q2+Q1 (i.e., elimination order, and of course one has to change variable names, should there be a name conflict), and compute a Groebner basis G of the ideal <{phi(x)-x: x generators of Q1}>. The kernel can be read off G (it is given by the elements of G that do not contain generators of Q2).
- And if I am not mistaken again, the same Groebner basis G can also be used to compute one element of the pre-image under phi for any element of Q2.
Kind regards, Simon
comment:3 follow-up: 4 Changed 13 years ago by
Dear Simon,
Thanks for your answer. Please let me add my 0.05 euro.
Replying to SimonKing:
My question: Is the data type in Singular for a general G-Algebra different from the data type for a SuperCommutative? ring? I guess so, since IIRC basic arithmetic for SuperCommutative? rings is much faster than for general G-Algebras.
Thanks, my pleasure. But no. Singular has a single data type for all the polynomials and vectors. It's just my basic arithmetic implementation which makes the difference.
gkdim.lib? I didn't know that library, so, I will look in the manual. Thank you!
AFAIK, gkdim.lib will probably be deprecated since dim(std(I)) should work in a more or less current Singular.
Really? preimage is throwing an error when using it on graded commutative (quotient) rings.
Really? I must have missed your bug report about that... :( Oh... do you mean "Sorry, not yet implemented for noncomm. rings" message?
I have put some examples in folders here.
Thanks.
Regards,
Oleksandr
Changed 13 years ago by
Attachment: | COHO2COHO1.Kernel.Workaround.sng added |
---|
Simon's workaround for "kernel" in general NC-setting.
comment:4 Changed 13 years ago by
Dear Oleksandr,
Replying to motsak: [...]
Really? preimage is throwing an error when using it on graded commutative (quotient) rings.
Really? I must have missed your bug report about that... :( Oh... do you mean "Sorry, not yet implemented for noncomm. rings" message?
Yes!
I see that you uploaded my workaround; I wasn't aware that I had sent it to you. Hopefully the code is correct...
Cheers, Simon
1. ALLOW THINGS VERSUS CONTEXTS
Hmmm... A long time ago there was a discussion about context-dependent functionality of a given function. In the future we'll need more flags for more noncommutative subsystems (Letterplace, Locapal are on the way). ALLOW list is definitely a solution, but having many of them is not easy to maintain.
Context-dependent choice might be described as follows. Given an object( say, of type matrix) over a ring, one determines the subset of the set of variables, which occur there and (in the noncommutative case) its SAGBI basis, what means plainly you complete these set to the set, which is multiplicatively closed.
Example: given the relation yx=xy+z, then {x,y} needs to be completed to {x,y,z} (note that this is NOT the case for graded commutative algebras). In many cases, however, one gets smaller subalgebras. Then a procedure will analyze the type of this context subalgebra (it's done internally) and make its decision. I like the idea of being able to factorize a univariate polynomial while sitting in any ring.
2. Recipe for Krull dimension in graded commutative case
In the noncommutative case one uses actually Gelfand-Kirillov dimension, since Krull is generalized to two-sided ideals only and it's called Krull-Rentschler-Gabriel dimension (which is scary in general). I believe that they might very well coinside on graded comm algebras (as they do in the commutative case with the only difference: GK dimension of a field containing Q is the transcendence degree of the field while Krull dimension is just zero). In the implementation in gkdim.lib, however, one does not add the dimension of the field to the result, so they are equal.)
On the contrary, Gelfand-Kirillov dimension is nice-behaving and it is already implemented in a library and someday will become a kernel procedure.
Recipe: Take your ideal I (assume it's in Groebner basis) in a graded comm algebra C. Go to the G-algebra G, such that C is isomorphic to G/T, add two ideals I and T ( =: J), set the "isSB" attribute of J to 1 (in order to avoid GB computation in the next procedure) and compute gkdim().
3. Preimage
There's PLURAL kernel command preimage, which has some limitations. More general way is of course possible (see my diss) but requires in general a lot of stuff - that's why it's not implemented on the full scale. Send me (or post here or somewhere and give me a link) the example of possible morphisms. I think for the graded comm case you'll be in the easiest case, where no severe restrictions of the general case apply. So this might be quite doable.
Best luck, Viktor