Re: [sage-support] Re: A ring with matrix ordering

[Martin Albrecht]

On Friday 04 September 2009, Simon King wrote:
> Hi Kwankyu,
>
> On Sep 4, 8:02 am, Kwankyu <ekwan...@gmail.com> wrote:
> > In Singular, a ring can be defined with matrix ordering:
>
> [...]
>
> > In Sage, I am trying to construct a polynomial ring with matrix
> > ordering.
>
> AFAIK, it is not implemented, but I think that some people were
> working on it.
>
> It is in fact one of the things that I miss in Sage's polynomial rings
> (the other thing are supercommutative rings), so that I need to use
> the Singular interface rather than libsingular.

Simon et al,

if you design a Python-ic interface how to construct all the term orderings we
are still missing in Sage from Singular (e.g. weighted term orderings), then I
might find the time to implement them. For me, it is mainly an interface
design question, the libSingular part looks relatively easy (and we have
[libsingular-devel] now, where every of my questions was answered very quickly
so far!).

As a starting point, the TermOder objects might be interesting?

sage: A = random_matrix(ZZ,3,3)
sage: TermOrder(A)

???

Cheers,
Martin

PS: Did you play with the new libsingular functions functionality in
4.1.2.alpha? It might help you out with your supercommutative rings. The
libsingular functions are not feature complete yet though.
--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
_www: http://www.informatik.uni-bremen.de/~malb
_jab: martinr...@jabber.ccc.de

[Michael Brickenstein]

Hi Simon!

> > It is in fact one of the things that I miss in Sage's polynomial rings
> > (the other thing are supercommutative rings),

Burcin will visit KL in octobre to work on
the integration of
noncommutative algebras in Singular.

Maybe, you can give use a list, what you need.

Cheers,
Michael

[Michael Brickenstein]

Hi Martin!

> sage: A = random_matrix(ZZ,3,3)
> sage: TermOrder(A)

It looks very natural to me.

Michael

[Burcin Erocal]

Hi Simon,

Can you also provide example sage sessions showing how you think these
objects should be constructed?

I completely agree with Martin's previous comments on this. :)

> if you design a Python-ic interface how to construct all the term
> orderings we are still missing in Sage from Singular (e.g. weighted
> term orderings), then I might find the time to implement them. For
> me, it is mainly an interface design question, the libSingular part
> looks relatively easy (and we have [libsingular-devel] now, where
> every of my questions was answered very quickly so far!).

I was planning to send a separate message about this topic, but since
Michael brought it up here it goes...

Is there anybody else interested in a wrapper for the noncommutative
functionality provided by Singular?

Singular's capabilities are described in the manual here:

http://www.singular.uni-kl.de/Manual/latest/sing_356.htm#SEC397

If you're interested please write back with the following information
- what exactly are your needs
- ideas for a possible user interface (example Sage session)
- if you can contribute to the development (testing patches and
designing an interface is also a contribution)

BTW, I will also be working on using Singular for rational function
fields, and (as time permits) maybe also algebraic function fields. I
would appreciate any help in that area as well.

Cheers,
Burcin

[Golam Mortuza Hossain]

Hi Burcin,

On Fri, Sep 4, 2009 at 7:33 AM, Burcin Erocal<bur...@erocal.org> wrote:

> Is there anybody else interested in a wrapper for the noncommutative
> functionality provided by Singular?
>
> Singular's capabilities are described in the manual here:
>
> http://www.singular.uni-kl.de/Manual/latest/sing_356.htm#SEC397
>
> If you're interested please write back with the following information
>  - what exactly are your needs
>  - ideas for a possible user interface (example Sage session)
>  - if you can contribute to the development (testing patches and
>   designing an interface is also a contribution)

Great! In quantum physics, one needs to work with quantum operator
that are non-commuting objects. There, we often need to check whether
commutator or anti-commutator of two composite operators are zero or not.

An example session would be:
----------
sage: A,B = nc_var('A,B')
sage: a,b,c,d = var('a,b,c,d')

sage: C = a*A + b*A*A
sage: D = d*B
sage: commutator(C, D)
a*d*commutator(A,B) + b*d*A*commutator(A,B) + b*d*commutator(A,B)*A

sage: commuator.define([A,B], 1)
sage commutator(A, B)
1

sage: commutator(C,D)
a*d + 2*b*d*A
------------

Thanks,
Golam

[Simon King]

Hi all!

On Sep 4, 11:33 am, Burcin Erocal <bur...@erocal.org> wrote:
[...]

> > Maybe, you can give use a list, what you need.
>
> Can you also provide example sage sessions showing how you think these
> objects should be constructed?

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])

> > if you design a Python-ic interface how to construct all the term
> > orderings we are still missing in Sage from Singular (e.g. weighted
> > term orderings), then I might find the time to implement them.

Currently, the ordering of a ring is determined by a string "name":
TermOrder.__init__(self, name='lex', n = 0, blocks=True)
respectively "order": PolynomialRing(base_ring, arg1=None, arg2=None,
sparse=False, order='degrevlex', names=None, name=None,
implementation=None)

Of course, it seems natural to define a matrix ordering by passing a
matrix:
sage: M = Matrix(2,2, [1,3,1,0])
sage: R.<x,y> = PolynomialRing(QQ,2,order=M)

But it is perhaps not so nice to break compatibility with the current
way of defining an ordering by strings.

Closer to Singular syntax would be
sage: R.<x,y> = PolynomialRing(QQ,2,order='M(1,3,1,0)')

But what about block orderings? If one allows a matrix ordering to be
defined by a matrix, then I guess the blocks should be listed:
sage: P.<a,b,c,d,e> = PolynomialRing(QQ,5,order=[M,'degrevlex'])

Or, if one goes with strings:
sage: P.<a,b,c,d,e> = PolynomialRing(QQ,5,order='M(1,3,1,0),degrevlex
(3)'])

As mentioned above, I would expect that the first row of a matrix
determines degrees (which is so in Singular). Hence, in the preceding
example, one would have
sage: a.degree()
1
sage: b.degree()
3
sage: c.degree() == d.degree() == e.degree() ==1
True

> Is there anybody else interested in a wrapper for the noncommutative
> functionality provided by Singular?
>
> Singular's capabilities are described in the manual here:
>
> http://www.singular.uni-kl.de/Manual/latest/sing_356.htm#SEC397
>
> If you're interested please write back with the following information
>  - what exactly are your needs
>  - ideas for a possible user interface (example Sage session)

My needs are restricted to the SuperCommutative algebras. The
implementation seems very efficient (two years ago I made some tests,
and the basic arithmetic is as fast as in the commutative case).

General non-commutative algebras are not needed to me, but would
certainly be nice to have. The nc_algebras in Singular are given by
two strictly upper triangular matrices, see
http://www.singular.uni-kl.de/Manual/latest/sing_404.htm#SEC445

So, one should expect that Sage should use two matrices as well.

However, there is one problem: In Singular, one would first define a
usual ring, since this allows you to define the two matrices (which
may contain polynomials, that's why you need the ring!), and only then
define the nc_algebra.

The example from the Singular manual would correspond to the following
Sage session:
sage: F.<Q> = FractionField(PolynomialRing(QQ,'Q'))
sage: R.<x,y,z> = PolynomialRing(F)
sage: C = Matrix(3,3, [0, Q^2, 1/Q^2, 0, 0, Q^2, 0,0,0])
sage: D = Matrix(3,3, [0, -Q*z, 1/Q*y, 0, 0, (-Q)*x, 0, 0, 0])
sage: ncF = F.nc_algebra(C,D)

It would be nice to have a one-line definition, but I doubt that this
would be easy, since one needs to name x,y,z when defining the matrix
D that is used when defining ncF.

>  - if you can contribute to the development (testing patches and
>    designing an interface is also a contribution)

Certainly I can do some tests.

Best regards,
Simon

[Martin Albrecht]

> Currently, the ordering of a ring is determined by a string "name":
> TermOrder.__init__(self, name='lex', n = 0, blocks=True)
> respectively "order": PolynomialRing(base_ring, arg1=None, arg2=None,
> sparse=False, order='degrevlex', names=None, name=None,
> implementation=None)

> Of course, it seems natural to define a matrix ordering by passing a
> matrix:
> sage: M = Matrix(2,2, [1,3,1,0])
> sage: R.<x,y> = PolynomialRing(QQ,2,order=M)
>
> But it is perhaps not so nice to break compatibility with the current
> way of defining an ordering by strings.
>
> Closer to Singular syntax would be
> sage: R.<x,y> = PolynomialRing(QQ,2,order='M(1,3,1,0)')

Think this would be rather un-pythonic: converting an object into a string
instead of using it directly.

> But what about block orderings? If one allows a matrix ordering to be
> defined by a matrix, then I guess the blocks should be listed:
> sage: P.<a,b,c,d,e> = PolynomialRing(QQ,5,order=[M,'degrevlex'])

Have you seen this?

sage: TermOrder('deglex',3) + TermOrder('degrevlex',2)
deglex(3),degrevlex(2) term order

> Or, if one goes with strings:
> sage: P.<a,b,c,d,e> = PolynomialRing(QQ,5,order='M(1,3,1,0),degrevlex
> (3)'])

I would like to avoid this string business as much as possible. I find it
rather ugly (that's personal taste of course)

Cheers,
Martin

[Simon King]

Hi Golam!

On Sep 4, 12:18 pm, Golam Mortuza Hossain <gmhoss...@gmail.com> wrote:
[...]

> An example session would be:
> ----------
> sage:  A,B = nc_var('A,B')
> sage: a,b,c,d = var('a,b,c,d')
>
> sage:  C = a*A + b*A*A
> sage:  D = d*B
> sage: commutator(C, D)
> a*d*commutator(A,B) + b*d*A*commutator(A,B) + b*d*commutator(A,B)*A
>
> sage: commuator.define([A,B], 1)
> sage commutator(A, B)
> 1
>
> sage: commutator(C,D)
> a*d + 2*b*d*A
> ------------

I think we are here not talking about non-commutative symbolic
variables but about proper non-commutative polynomials over some base
ring. This has very little to do with symbolics. Moreover, I think it
is not pythonic to have a callable class "commutator" in the global
name space acting on polynomial rings.

However, I could imagine the following:

sage: F.<a,b,c,d> = FractionField(PolynomialRing(QQ,'a,b,c,d'))
sage: R.<A,B> = NCPolynomialRing(F)
# At this stage, R is a free non-commutative algebra

sage: C = a*A + b*A*A
sage: D = d*B

sage: C.commutator(D)
# whatever the answer is, but it would be an element of R and would
certainly not contain the word "commutator"
sage: R.nc_relation(A.commutator(B),1) # This would change R in
place, so by now it has some relations!!
sage: C.commutator(D)
a*d + 2*b*d*A

The advantage of this approach is that you can define any non-
commutative relation.

The disadvantages:
* Changing a ring in-place seems dangerous to me (can yield bugs that
are difficult to find)
* Changing a ring in-place is perhaps impracticable, since the
underlying implementation might completely change
* AFAIK, free non-commutative rings are only experimental in
Singular, and probably not yet ready for being wrapped in libSingular

Cheers,
Simon

[Simon King]

Hi Martin!

On Sep 4, 12:33 pm, Martin Albrecht <m...@informatik.uni-bremen.de>
wrote:
[...]

> > But it is perhaps not so nice to break compatibility with the current
> > way of defining an ordering by strings.
>
> > Closer to Singular syntax would be
> >   sage: R.<x,y> = PolynomialRing(QQ,2,order='M(1,3,1,0)')
>
> Think this would be rather un-pythonic: converting an object into a string
> instead of using it directly.

I agree -- I don't like to use strings either. My suggestion "order='M
(1,3,1,0)'" was only in an attempt to provide compatibility with the
status quo, which is to define the ordering by a string, or by a
TermOrder object.

> Have you seen this?
>
> sage: TermOrder('deglex',3) + TermOrder('degrevlex',2)
> deglex(3),degrevlex(2) term order

Yes, but in fact I forgot about it. Reason: In most of the examples,
the term ordering of a polynomial ring is given by a string, rather
than first defining a TermOrder object.

Anyway, I agree that

sage: M = Matrix(2,2, [1,3,1,0])

sage: P.<a,b,c,d,e> = PolynomialRing(QQ,5,order=TermOrder(M)+TermOrder
('degrevlex',3))
is a good solution.

Best regards,
Simon

[Burcin Erocal]

Hi Simon,

I should have mentioned earlier that long ago Michael Brickenstein and
I wrote a preliminary interface to Plural. You can find the patches
here:

http://trac.sagemath.org/sage_trac/ticket/4539

On Fri, 4 Sep 2009 04:27:25 -0700 (PDT)
Simon King <simon...@nuigalway.ie> wrote:

<snip>

> > Is there anybody else interested in a wrapper for the noncommutative
> > functionality provided by Singular?
> >
> > Singular's capabilities are described in the manual here:
> >
> > http://www.singular.uni-kl.de/Manual/latest/sing_356.htm#SEC397
> >
> > If you're interested please write back with the following
> > information
> >  - what exactly are your needs
> >  - ideas for a possible user interface (example Sage session)
>
> My needs are restricted to the SuperCommutative algebras. The
> implementation seems very efficient (two years ago I made some tests,
> and the basic arithmetic is as fast as in the commutative case).
>
> General non-commutative algebras are not needed to me, but would
> certainly be nice to have. The nc_algebras in Singular are given by
> two strictly upper triangular matrices, see
> http://www.singular.uni-kl.de/Manual/latest/sing_404.htm#SEC445
>
> So, one should expect that Sage should use two matrices as well.

This is not necessary. There is some code written by Michael that
converts the relations to a matrix, and passes that on to Singular
around line 396 of the patch here:

http://trac.sagemath.org/sage_trac/attachment/ticket/4539/plural_2.patch

Here is the doctest from that function:

sage: A.<x,y,z>=FreeAlgebra(QQ,3)
sage: G=A.g_algebra({y*x:-x*y})
sage: (x,y,z)=G.gens()
sage: x*y
x*y
sage: y*x
-x*y
sage: z*x
x*z
sage: (x,y,z)=A.gens()
sage: G=A.g_algebra({y*x:-x*y+1})
sage: (x,y,z)=G.gens()
sage: y*x
-x*y + 1
sage: (x,y,z)=A.gens()
sage: G=A.g_algebra({y*x:-x*y+z})
sage: (x,y,z)=G.gens()
sage: y*x
-x*y + z

IMHO, this is more user friendly compared to the Singular interface.
We shouldn't restrict ourselves to copying the Singular commands to
construct these objects.

We should also tie these to the FreeAlgebra stuff from the beginning.
Otherwise, we'll end up with a wrapper that lives independent of the
algebraic hierarchy like the PolyBoRi wrapper ended up being.

Thanks.

Cheers,
Burcin

[Simon King]

Hi Burcin!

On Sep 4, 12:56 pm, Burcin Erocal <bur...@erocal.org> wrote:
[...]

> > So, one should expect that Sage should use two matrices as well.
>
> This is not necessary. There is some code written by Michael that
> converts the relations to a matrix, and passes that on to Singular
> around line 396 of the patch here:
>
> http://trac.sagemath.org/sage_trac/attachment/ticket/4539/plural_2.patch
>
> Here is the doctest from that function:
>
> sage: A.<x,y,z>=FreeAlgebra(QQ,3)
> sage: G=A.g_algebra({y*x:-x*y})

Yes, this is much better than my stupid suggestion to add relations by
changing a ring in-place.

> IMHO, this is more user friendly compared to the Singular interface.

+1
I am glad that such interface already exists. Is it based on the
recent Singular implementation of free algebras, or is it independent?

Cheers,
Simon

[Michael Brickenstein]

Hi!

>  * AFAIK, free non-commutative rings are only experimental in
> Singular, and probably not yet ready for being wrapped in libSingular

AFAIK (and I hope, that's more) free algebras in Singular are only an
emulation on top of our existing rings and only work up to some
degree.

I think, this is very interesting and tricky stuff, but I wouldn't
recommend to do anything now about that.

I hope, that we get the best results out of this week.

Michael

[Burcin Erocal]

Do you mean the Letterplace (why do they capitalize the names of
these things?!?) extension [1] ?

[1] http://www.singular.uni-kl.de/Manual/latest/sing_425.htm#SEC478

I am not sure if using this directly for arithmetic from Sage is a good
idea, since you need to give a bound on the degree of each variable
that will appear in your computation (and we also need to fix the
printing anyway). I was thinking of hooking up the GB functions only to
the appropriate places (which don't exist at the moment).

Unfortunately this requires giving more care and attention to the
FreeAlgebra stuff in Sage than I have time for, so it will have to wait
till someone else takes it up.

Cheers,
Burcin

[Burcin Erocal]

It's independent. It was just a quick effort to use Plural from Sage. I
didn't have time afterwards to follow up and fix the remaining
problems. I don't even know if the patches still apply.

I'm hoping that things will be easier now since there is a much cleaner
interface to libSingular (many thanks Martin and Michael!). Though
sage/algebras/ is still one of the most rusty corners of sage. :)

Cheers,
Burcin

[Simon King]

Hi Burcin, Hi Michael,

On Sep 4, 1:23 pm, Burcin Erocal <bur...@erocal.org> wrote:
[...]

> Do you mean the Letterplace (why do they capitalize the names of
> these things?!?) extension [1] ?
>
> [1]http://www.singular.uni-kl.de/Manual/latest/sing_425.htm#SEC478

I think so. I didn't use it myself, but I heard it being mentioned in
conference talks.

> Unfortunately this requires giving more care and attention to the
> FreeAlgebra stuff in Sage than I have time for, so it will have to wait
> till someone else takes it up.

Well, Michael seemed to agree that Letterplace is of more experimental
character.

But certainly the G-algebra stuff in Singular (where the non-
commutativity is provided by two matrices) is mature enough, and I
understood from the previous posts that it is already more or less
wrapped, and we are talking about the interface.

Certainly,

sage: A.<x,y,z>=FreeAlgebra(QQ,3)
sage: G=A.g_algebra({y*x:-x*y})

is nice.

But what exactly is the input data? Would you allow general relations,
such as {y*x*y: -z+x*y}? Or must the keys of the dictionary be
monomials of degree 2, since otherwise you run into non-decidable
questions? In this case, I guess your interface is equivalent to
Singular's way of defining a G-algebra, but certainly nicer.

Since there is http://trac.sagemath.org/sage_trac/ticket/4539 and it
says "need work": What exactly is needed to do? Is it just a decision
about the interface? In that case, I am +1 to your suggestion!

Cheers,
Simon

[Burcin Erocal]

You're right, it is equivalent to the G-algebras defined in Singular.
Checking these conditions is one of the items on the list below. :)

> Since there is http://trac.sagemath.org/sage_trac/ticket/4539 and it
> says "need work": What exactly is needed to do? Is it just a decision
> about the interface? In that case, I am +1 to your suggestion!

No, unfortunately it's not that easy.

- We just subclassed MPolynomialRing_libsingular to create the ring
then, elements are instances of MPolynomial_libsingular. These
inherit from CommutativeRing and CommutativeRingElement
respectively. :)

One would have to create new classes for the elements and the parent
in the appropriate place of the hierarchy. Refactoring the
libSingular calls in the above classes helps tremendously here. :)

- Check if the commutativity relations satisfy the conditions for a
G-algebra as defined here:

http://www.singular.uni-kl.de/Manual/latest/sing_420.htm#SEC461

- sort out coercion
- wrap various functions defined by Singular:
http://www.singular.uni-kl.de/Manual/latest/sing_390.htm#SEC431
- find a way to wrap the predefined structures here:
http://www.singular.uni-kl.de/Manual/latest/sing_538.htm#SEC591
- etc.

Any volunteers?

Cheers,
Burcin

[Michael Brickenstein]

Hi!

> - sort out coercion
> - wrap various functions defined by Singular:
> http://www.singular.uni-kl.de/Manual/latest/sing_390.htm#SEC431

This part won't require hard Singular knowledge.
We probably will have to add some missing pieces to LibSingularFunction
to make the wrapping really easy.
I think, we can need every helping hand here.
Cheers,
Michael

[Simon King]

Hi Burcin!

On Sep 4, 2:52 pm, Burcin Erocal <bur...@erocal.org> wrote:
[...]

> > Since there ishttp://trac.sagemath.org/sage_trac/ticket/4539and it

> > says "need work": What exactly is needed to do? Is it just a decision
> > about the interface? In that case, I am +1 to your suggestion!
>
> No, unfortunately it's not that easy.
>
>  - We just subclassed MPolynomialRing_libsingular to create the ring
>    then, elements are instances of MPolynomial_libsingular. These
>    inherit from CommutativeRing and CommutativeRingElement
>    respectively. :)
>
>    One would have to create new classes for the elements and the parent
>    in the appropriate place of the hierarchy. Refactoring the
>    libSingular calls in the above classes helps tremendously here. :)

I am not sure what you mean.

Certainly I don't know enough about the Singular internals. So far my
impression was that Singular/Plural has two data types /
implementations of non-commutative rings: One for SuperCommutative
rings and one for general G-algebras. And I thought that both somehow
rely on the commutative rings, internally.

So, do you re-implement Singular/Plural nc-algorithms (subclassing
MPolynomialRing_libsingular and building on top of it), or are you
directly wrapping Singular/Plural data types?

Or was your statement about how Sage's G-algebras should fit into the
hierarchy of algebras? Then the following seems to make sense to me:

* Ring(ParentWithGens)
* CommutativeRing(Ring)
* CommutativeAlgebra(CommutativeRing)
* Algebra(Ring)
* PolynomialRing_general(Algebra)
* GAlgebra(PolynomialRing_general) # new
* GAlgebra_libsingular(GAlgebra) # new
* PolynomialRing_supercommutative(G_Algebra) # new
# (perhaps with a _libsingular subclass)
* PolynomialRing_commutative(GAlgebra,
CommutativeAlgebra)
# this currently is (PolynomialRing_general,
CommutativeAlgebra)
* MPolynomialRing_libsingular etc.

Cheers,
Simon

[Oleksandr]

Hi Burcin, Michael, Simon,

Please let me explain the current non-commutative Singular
conventions:
1. the only way to create a G-algebra is to endow a commutative
polynomial ring (NOT a qring!) with a non-commutative structure
2. in order to create a GR-algebra:
compute two-sided GB in G-algebra and use it to define a factor
ring.

{{{
// example Singular script:
// 1:
ring r;
def g=nc_algebra(-1,0); setring g;
g;
// 2:
ideal q=twostd(ideal(x^2, y^2, z^2));
qring gr = q;
gr; // exterior algebra in x,y,z
x*x; // gives 0: since gr is internally a SCA
}}}

Therefore the only "legal" steps are:
A. define G-algebra (using matrices C & D) (see jjPlural_mat_mat in
iparith.cc)
B. compute a two-sided(!) GB there (see jjTWOSTD in iparith.cc)
(the standard "std" command computes a left (!) GB in non-commutative
case)
C. create non-commutative factor ring (see jiA_QRING in ipassign.cc)
(factors of GR-algebras are allowed)

Special multiplicative structure (e.g. supercommutative) will be
automatically detected in A. & C. whereas forcefully calling the
internal API (e.g. sca_*) is prone of subtle side effects.

Cheers,
Oleksandr

> > Since there ishttp://trac.sagemath.org/sage_trac/ticket/4539and it

[Oleksandr]

Hello,

i would like to add that commutative variables in supercommutative
algebras may be local (whereas non-commutative variables must be
global), e.g:

{{{
LIB "nctools.lib";
ring r=0,(x,y,z), (ds(1), dp(2)); // x is local!
def E = superCommutative(2,3);setring E; E;
// characteristic : 0
// number of vars : 3
// block 1 : ordering ds
// : names x
// block 2 : ordering dp
// : names y z
// block 3 : ordering C
// noncommutative relations:
// zy=-yz
// quotient ring from ideal
_[1]=y2
_[2]=z2
> y*y; // SCA!
0
> 1+ x + y + z; // y > z > 1 > x !
y+z+1+x
}}}

This functionality was initially intended to support computation of
direct images of sheaves in certain cases but by no means limited to
that.
The Singular's "std" uses a modified Mora variant of BBA in such a
"local" case.
Feel free to experiment with this feature :)

Please do let us know about your favorite and yet missing non-
commutative features!

Any feedback is greatly appreciated!

Cheers,
Oleksandr

[Simon King]

Hi Oleksandr!

On Sep 4, 6:52 pm, Oleksandr <mot...@rhrk.uni-kl.de> wrote:
[...]

> Please do let us know about your favorite and yet missing non-
> commutative features!
>
> Any feedback is greatly appreciated!

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.

Three examples:
* 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.

Best regards,
Simon

[Oleksandr]

Hi Simon,

Thank you! That's definitely something to think about.

First of all, please, let me explain that Singular kernel doesn't have
any such markers... it's actually the Singular interpreter who cares
at the moment about command availability in general non-commutative
case. These markers are used to disable commands which are still only
commutative-minded and thus not guaranteed to work and compute
something sensible.
AFAIK It was done in such a static way mainly due to the ability to
remove the non-commutative subsystem in _compile_time_ without any
traces...

Well, if go on defining more cases and assigning more markers to
commands, wouldn't it make Singular less and less maintainable?
In fact i fail to see how non-commutativity is soooooo qualitatively
different from say homogeneity of input...
I would propose to move these checks into kernel feature
implementations so that they can be done in run time by every
individual feature, which definitely should know more about its
abilities than the Singular interpreter. This way we can guarantee
their correctness (or at least a sensible error message) even when
being called directly by Sage in any setting.

What do you think?

Best regards,
Oleksandr

[Simon King]

Hi Oleksandr,

On Sep 5, 10:53 am, Oleksandr <mot...@rhrk.uni-kl.de> wrote:
[...]

> First of all, please, let me explain that Singular kernel doesn't have
> any such markers...

Really? The only part of the Singular kernel that I ever met is
iparith.cc, or is this not kernel? Here, one typically sees lines such
as
{jjSTD_HILB_WP, STD_CMD, IDEAL_CMD, 4
NO_PLURAL}
{jjREDUCE5, REDUCE_CMD, IDEAL_CMD/*or set by p*/, 5
ALLOW_PLURAL}

By "markers", I was referring to these NO_PLURAL / ALLOW_PLURAL
markers.

[...]

> I would propose to move these checks into kernel feature
> implementations so that they can be done in run time by every

> individual feature, [...]

Perhaps it was my misunderstanding that iparith.cc is in the kernel.

I would agree that it makes mathematically sense to let each function
check by itself whether the input is suitable (e.g., jjSTD_HILB_WP
checks whether we are in a graded commutative weighted homogeneous
setting, in which Hilbert driven standard basis computation makes
sense).

However, I am not sure if Hans or Gert-Martin would agree that it
makes practically sense. 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.

Cheers,
Simon

[Oleksandr]

Dear Simon,

On Sep 5, 12:34 pm, Simon King <simon.k...@nuigalway.ie> wrote:
> On Sep 5, 10:53 am, Oleksandr <mot...@rhrk.uni-kl.de> wrote:
> > First of all, please, let me explain that Singular kernel doesn't have
> > any such markers...
> Really? The only part of the Singular kernel that I ever met is
> iparith.cc, or is this not kernel? Here, one typically sees lines such as
> {jjSTD_HILB_WP, STD_CMD, IDEAL_CMD, 4
> NO_PLURAL}
> {jjREDUCE5, REDUCE_CMD, IDEAL_CMD/*or set by p*/, 5
> ALLOW_PLURAL}
> By "markers", I was referring to these NO_PLURAL / ALLOW_PLURAL
> markers.

Yes exactly - this is a part of Singular interpreter. Functions like
jjSTD_HILB_WP should (ideally) _only_ delegate the call to the
appropriate
kernel function (say kStd) while doing some interpreter-related checks
and
convert interpreter's data structures (e.g. leftv, attributes) into
something
kernel-understandable (e.g. poly/ideal/intvec).

> > I would propose to move these checks into kernel feature
> > implementations so that they can be done in run time by every
> > individual feature, [...]

> Perhaps it was my misunderstanding that iparith.cc is in the kernel.

I agree that at the moment the boundary between the Singular
interpreter
(which is the /Singular directory) and the kernel (/kernel) is a way
tooooo weak:
ideally there should be NO parts of singular kernel logic inside
interpreter wrappers (jj***)...

> I would agree that it makes mathematically sense to let each function
> check by itself whether the input is suitable (e.g.,

> checks whether we are in a graded commutative weighted homogeneous
> setting, in which Hilbert driven standard basis computation makes
> sense).

> However, I am not sure if Hans or Gert-Martin would agree that it
> makes practically sense. 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?

Well, this "simple test" is exactly the existing static NO_PLURAL/
ALLOW_PLURAL-marker functionality.
Specific tests (detections) are performed _once_ during the algebra
construction.
Afterwards checks like "is non-commutative" or "is supercommutative"
are _cheap_
(see rIsPluralRing and rIsSCA).

> Therefore my suggestion to have markers, say ALLOW_G_ALGEBRA,
> ALLOW_SC_ALGEBRA, NO_PLURAL.

You see, the idea was to provide a framework in which one can easily
implement
any particular GR-algebra as a separate kernel extension with its own
multiplication routines and SB-related algorithms in a virtual-
overloading manner.
At the moment SCA is just an example of how this can be done...
Moreover, we already have a separate experimental implementation where
multiplication
uses formulas for specific automatically detectable G-algebras (e.g.
Weyl) instead of raw
relations+caching (as in the general G-algebra). I guess these
formulas will eventually be
merged into the framework...

More importantly: if Sage accesses the Singular kernel directly -
these Singular interpreter markers cannot help Sage...

Regards,
Oleksandr

[Simon King]

Hi Martin!

On Sep 4, 12:33 pm, Martin Albrecht <m...@informatik.uni-bremen.de>
wrote:

[..]

> Think this would be rather un-pythonic: converting an object into a string
> instead of using it directly.
>
> > But what about block orderings? If one allows a matrix ordering to be
> > defined by a matrix, then I guess the blocks should be listed:
> >   sage: P.<a,b,c,d,e> = PolynomialRing(QQ,5,order=[M,'degrevlex'])
>
> Have you seen this?
>
> sage: TermOrder('deglex',3) + TermOrder('degrevlex',2)
> deglex(3),degrevlex(2) term order

Meanwhile I've also seen the code of TermOrder.__add__. It is rather
un-pythonic, as it entirely relies on working with strings.

Namely:
...
name = []
for block_order in self.blocks + other.blocks:
nom = block_order.singular_str()
name.append("%s(%d)"%(inv_singular_name_mapping.get
(nom,nom), len(block_order)))

name = ",".join(name)
return TermOrder(name, len(self)+len(other))

In other words, for each block, the defining string for the order in
Singular is translated into a defining string for the order in Sage,
by a dictionary lookup (inv_singular_name_mapping.get(nom,nom), then
everything is concatenated and given as the input to
TermOrder.__init__.

Problem: singular_str() for a matrix order will be M(1,3,1,0,...),
where the number of integers between the brackets depends on the
lengths. This can't be dealt with by a simple dictionary lookup.

So, a proper support of Matrix orders will be more work, and wrapping
things in libsingular will not suffice.

Best regards,
Simon

[Michael Brickenstein]

Hi!

> More importantly: if Sage accesses the Singular kernel directly -
> these Singular interpreter markers cannot help Sage...

Independent from what is the right solution, I would like to mention,
that I worked with Martin on using the same interface to the kernel
functions as the Singular interpreter does.
So maybe, SingularKernelFunction already checks the markers.
Cheers,
Michael

[Kwankyu]

Hi,

How about this syntax?

> sage: A = random_matrix(ZZ,3,3)
> sage: TermOrder("weight",matrix=A)

following the Magma syntax for weight ordering. I certainly prefer the
term weight ordering than matrix ordering.

The following is the description of the weight ordering in the Magma
documentation:

Definition (given n weight vectors W1, ... Wn from Q^n): s < t iff
there exists 1 ≤i ≤n such that s.Wj = t.Wj for 1 ≤j < i and s.Wi <
t.Wi. The order is specified by the arguments ("weight", Q) where Q is
a sequence of n^2 non-negative integers or rationals describing the n
weight vectors of length n (in row major order).

Kwankyu

[Simon King]

Hi!

On Sep 5, 7:32 pm, Kwankyu <ekwan...@gmail.com> wrote:
> How about this syntax?
>
> > sage: A = random_matrix(ZZ,3,3)
> > sage: TermOrder("weight",matrix=A)
>
> following the Magma syntax for weight ordering. I certainly prefer the
> term weight ordering than matrix ordering.

I don't know what is more common. I learned it under the name
"matrix", not "weight". By "weight", I would understand that one just
gets a degree vector for the ring generators (as in "weighted
homogeneous"), for example a "weighted degree lexicographic order".

Anyway, it seems redundant to give both a string ("weight" or
"matrix") *and* a matrix.

So, this syntax is shorter and clearer:
sage: TermOrder(A)

Note that when we talk about the input syntax, we would certainly not
be able to solve the problem with the __add__ method that I mentioned
in a previous post. I think that problem can only be solved by
improving the internal representation of the order.

Cheers,
Simon

[Martin Albrecht]

> Meanwhile I've also seen the code of TermOrder.__add__. It is rather
> un-pythonic, as it entirely relies on working with strings.

<snip>

> So, a proper support of Matrix orders will be more work, and wrapping
> things in libsingular will not suffice.

Sure, it is rather ad-hoc at the moment. As soon as we have an interface we
want to expose to the user (maybe TermOder(Matrix) suffices?) we can fix that!

[Oleksandr]

Hi Martin,

What about Sage implementation for

1. weighting vector(s) "a(w1, w2...wn)",
2. free module orderings (e.g. c/C) mixed somewhere in between? Does
Sage have such a concept?

In Sage i'd imagine something like:
{{{
TermOrder = WeightVector(2,5) + ModuleOrder('c') + WeightVector(-1,-2)
+ MatrixOrder(1,1,0,-1)
}}}

corresponding to:

{{{
> ring R =0,(x, y), (a(2,5), c, a(-1,-2), M(1,1,0,-1)); R;
// characteristic : 0
// number of vars : 2
// block 1 : ordering a
// : names x y
// : weights 2 5
// block 2 : ordering c
// block 3 : ordering a
// : names x y
// : weights -1 -2
// block 4 : ordering M
// : names x y
// : weights 1 1
// : weights 0 -1
> deg(x); // note that the 1st "a"/"M"/weighted ordering is used for "deg"
2
> deg(y);
5
}}}

Best regards,
Oleksandr


On Sep 4, 1:33 pm, Martin Albrecht <m...@informatik.uni-bremen.de>
wrote:

> _jab: martinralbre...@jabber.ccc.de

[Michael Brickenstein]

Hi!

Am 07.09.2009 um 14:34 schrieb Oleksandr:

>
> Hi Martin,
>
> What about Sage implementation for
>
> 1. weighting vector(s) "a(w1, w2...wn)",
> 2. free module orderings (e.g. c/C) mixed somewhere in between? Does
> Sage have such a concept?

I suppose, that the answer is no.

>
> In Sage i'd imagine something like:
> {{{
> TermOrder = WeightVector(2,5) + ModuleOrder('c') + WeightVector(-1,-2)
> + MatrixOrder(1,1,0,-1)
> }}}
>

I suppose, the best thing is to separate that into a ModuleOrder,
which builds on a TermOrder.

Michael

[Oleksandr]

Hi,

I am not sure what do you mean by that?
Note that one can mixin a ModuleOrder somewhere in between TermOrder-
s.

Well, I guess one needs a concept comprising all the possible
alternatives (even of) module orderings...
It would be nice to have a Syzygy and Schreyer (free module) orderings
as well!

As of Singular - please remember that ANY ordering is a module
ordering:
e.g. simply using something like "(dp)" actually means "(dp, C)"!

Oleksandr

[Michael Brickenstein]

Hi Oleksandr!

Am 08.09.2009 um 15:25 schrieb Oleksandr:

>
> Hi,
>
> On Sep 7, 3:17 pm, Michael Brickenstein <brickenst...@mfo.de> wrote:
>> Am 07.09.2009 um 14:34 schrieb Oleksandr:
>>> What about Sage implementation for
>>
>>> 1. weighting vector(s) "a(w1, w2...wn)",
>>> 2. free module orderings (e.g. c/C) mixed somewhere in between? Does
>>> Sage have such a concept?
>>
>> I suppose, that the answer is no.
>>> In Sage i'd imagine something like:
>>> {{{
>>> TermOrder = WeightVector(2,5) + ModuleOrder('c') + WeightVector
>>> (-1,-2)
>>> + MatrixOrder(1,1,0,-1)
>>> }}}
>> I suppose, the best thing is to separate that into a ModuleOrder,
>> which builds on a TermOrder.
>
> I am not sure what do you mean by that?
> Note that one can mixin a ModuleOrder somewhere in between TermOrder-
> s.

I am referring to the fact, that it is sensible
to assume, that for each component the ordering on the component is
the same as on the polynomial
ring.

SchreyerOrdering(exponents=[(list of integers)], term_order=TermOrder
(..))
ComponentFirst(term_order=..., ascending=True)# (c, dp)
ComponentLast(...)

I agree with you, that Schreyer orderings should be exposed to the
surface.

Using that assumption, the problem of a module ordering becomes
orthogonal to the Term Ordering.

Cheers,
Michael

[Oleksandr]

Hi Michael,

On Sep 8, 3:33 pm, Michael Brickenstein <brickenst...@mfo.de> wrote:
> Am 08.09.2009 um 15:25 schrieb Oleksandr:
> > On Sep 7, 3:17 pm, Michael Brickenstein <brickenst...@mfo.de> wrote:
> >> Am 07.09.2009 um 14:34 schrieb Oleksandr:
> >>> What about Sage implementation for
>
> >>> 1. weighting vector(s) "a(w1, w2...wn)",
> >>> 2. free module orderings (e.g. c/C) mixed somewhere in between? Does
> >>> Sage have such a concept?
>
> >> I suppose, that the answer is no.
> >>> In Sage i'd imagine something like:
> >>> {{{
> >>> TermOrder = WeightVector(2,5) + ModuleOrder('c') + WeightVector
> >>> (-1,-2)
> >>> + MatrixOrder(1,1,0,-1)
> >>> }}}
> >> I suppose, the best thing is to separate that into a ModuleOrder,
> >> which builds on a TermOrder.
>
> > I am not sure what do you mean by that?
> > Note that one can mixin a ModuleOrder somewhere in between TermOrder-
> > s.
>
> I am referring to the fact, that it is sensible to assume, that for each component the ordering on the component is
> the same as on the polynomial ring.
>
> SchreyerOrdering(exponents=[(list of integers)], term_order=TermOrder(..))

I'd add that in general one starts with a ModuleOrder (instead of
TermOrder) here.

> ComponentFirst(term_order=..., ascending=True)# (c, dp)
> ComponentLast(...)

I would not want to restrict us to "(c/C, >)" and "(>, c/C)" from the
very beginning...
How do you propose to mix in "c" in between? e.g. as in 'a(1,2), M(3),
c, dp'?

Please let me suggest the following "additive _block_ structure":

(e.g. WeightVector(1,2) + MatrixOrder(3) + ComponentOrder
(ascending=True) + SingularOrder('dp') for the above example)

. There should be at least ModuleOrder, WeightVector and TermOrder (3
different classes)
(ModuleOrder and WeightVector are _not_ TermOrder-s)

. TermOrder + WeightVector, WeightVector + TermOrder, TermOrder +
TermOrder give TermOrder-s

. TermOrder + ModuleOrder and ModuleOrder + TermOrder give ModuleOrder-
s

. ModuleOrder + ModuleOrder is _not_ defined

. MatrixOrder is a TermOrder

. ComponentOrder, SyzygyOrder, SchreyerOrder are ModuleOrder-s

Besided, i would suggest to have an option to supply an arbitrary
string to Singular (e.g. SingularOrder('a(1,2), M(3), c, dp') )

There may be a compatibility problem: some Orders may not be
compatible with each other or with the ring (due to the number of
variables). Therefore one might need an optional _length_ attribute.
e.g. WeightVector(1,2) has the length 2, MatrixOrder(1) - 1 and thus
they don't sum up together.

> I agree with you, that Schreyer orderings should be exposed to the surface.

That would be nice! Additionally one might need (at least i do) to add
more reference module-terms in run-time without changing the ring:
e.g. in Schreyer or LaScala resolution.
I guess it's a way toooo CAS specific. AFAIK M2 can somehow endowe
_just_ a matrix with a Schreyer ordering...


Cheers,
Oleksandr

[Martin Albrecht]

Hi there,

I have to say that I don't like the

WeightVector(2,5) + ModuleOrder('c')

syntax. WeightVector is a modification of the following term order (in
Singular). It feels much more natural to me to simply do:

TermOrder('lex',weights=(2,5))

Also, I don't really understand what

> ring R =0,(x, y), (a(2,5), c, a(-1,-2), M(1,1,0,-1)); R;
// characteristic : 0
// number of vars : 2
// block 1 : ordering a
// : names x y
// : weights 2 5
// block 2 : ordering c
// block 3 : ordering a
// : names x y
// : weights -1 -2
// block 4 : ordering M
// : names x y
// : weights 1 1
// : weights 0 -1
> deg(x); // note that the 1st "a"/"M"/weighted ordering is used for "deg"
2
> deg(y);
5

does exactly. As far as I can see a(X,Y) modifies the following ordering which
eventually is the Matrix odering (1,1,0,-1). What's the role of the second
a(X,Y) in the example above?

Cheers,
Martin

--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
_www: http://www.informatik.uni-bremen.de/~malb

_jab: martinr...@jabber.ccc.de

[Michael Brickenstein]

Hi!
It seems to me, that restricted to rings and ideals,
the ordering looks like
2 5
-1 -2
So, the Matrix M(1,1,0,-1) is probably useless in this example.

Michael

[Oleksandr]

Hi Martin, Michael,

clearly that example was too quickly made up and is somewhat redundant
(due to 2 variables).

a(w_1, ..., w_n) is the elementary comparison wrt the scalar product
of an exponent with the vector (w_1, ..., w_n) (denoted by $>_
{(w_1, ..., w_n)}$). Any matrix ordering is exactly a block-ordering
comprising n weightings (wrt its row-vectors),
e.g. M(A, B, C, D) is exactly the same as (a(A,B), a(C,D)), lp(2) = M
(1,0,0,1) = (a(1,0), a(0,1)) etc.

I'd say that (>_w) is an elementary building block for any
TermOrdering.

my point was that comparison of module components may be done
somewhere between two term orderings.

Maybe the following example would be a bit better:
consider a free module over the Weyl algebra as K<x1, x2, Dx1, Dx2;
relations >^{r} wrt the ordering which compares 1st the degree in D-
exponents, 2nd module components, and at last whole exponents wrt dp:
(a(0,0,1,1), C, dp).

Regards,
Oleksandr

> > _jab: martinralbre...@jabber.ccc.de

[Kwankyu]

Hi,

I created a trac ticket #6922 to track this issue. I also added a
patch, which does not work. :-)
As I really need matrix ordering, I hope someone solve this issue
soon.

Kwankyu