Implement modules for fundamental algebraic structures in sympy

[Gaurav Sathe]

Hi all, I am interested in participating in Gsoc and I would like to know if this could be a good project for sympy. 

As you know the concept of group theory is widely used in abstract mathematics. Currently there is no module in sympy for the various algebraic structures which come under abstract maths such as groups,rings,vector spaces,modules and fields. 

I really think all these modules should be inculcated into sympy and I would be very much interested in doing the same as a part of Gsoc

I would really appreciate any feedback and suggestions as to how I can move forward with this idea

Cheers...

P.S.: Patch requirement: I tried to fix this bug from the issues list and have sent a pull request

https://github.com/sympy/sympy/pull/1117

Can someone please go through this and let me know if its OK... Thnx

  

[David Joyner]

On Sat, Mar 17, 2012 at 2:07 PM, Gaurav Sathe <gaurav....@gmail.com> wrote:
> Hi all, I am interested in participating in Gsoc and I would like to know if
> this could be a good project for sympy.
>
> As you know the concept of group theory is widely used in abstract
> mathematics. Currently there is no module in sympy for the various algebraic
> structures which come under abstract maths such as groups,rings,vector
> spaces,modules and fields.
> I really think all these modules should be inculcated into sympy and I would
> be very much interested in doing the same as a part of Gsoc

I think doing some of this this could be a very useful addition.
How specifically do you intend to implement groups?
Or vector spaces/matrices over a finite field?

>
> I would really appreciate any feedback and suggestions as to how I can move
> forward with this idea
>
> Cheers...
>
> P.S.: Patch requirement: I tried to fix this bug from the issues list and
> have sent a pull request
>
> https://github.com/sympy/sympy/pull/1117
>
>
> Can someone please go through this and let me know if its OK... Thnx
>
>
>
>
>

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/sympy/-/5e7iSce1HLIJ.
> To post to this group, send email to sy...@googlegroups.com.
> To unsubscribe from this group, send email to
> sympy+un...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/sympy?hl=en.

[Saptarshi Mandal]

Rebase and squash all the commits into one.

[Joachim Durchholz]

Am 17.03.2012 19:07, schrieb Gaurav Sathe:
> As you know the concept of group theory is widely used in abstract
> mathematics. Currently there is no module in sympy for the various
> algebraic structures which come under abstract maths such as
> groups,rings,vector spaces,modules and fields.
> I really think all these modules should be inculcated into sympy and I
> would be very much interested in doing the same as a part of Gsoc

What kinds of operations would these modules contain?

[Gaurav Sathe]

Under group theory(and ring theory) I intend to implement the following:

   subgroups, normal and quotient groups, homomorphisms on groups and permutation groups.

Under vector spaces:

   basis for a vector space, dual vector spaces and modules

Field theory however has a much larger scope for implementation since it includes the Galois theory.  I could also implement extension fields.

I think this topic is large enough for a whole summer's work and would make a great addition to sympy. 

--
Gaurav Sathe
-Student at BITS Pilani - Goa Campus

[krastano...@gmail.com]

I might be wrong, however the way I understand the question by Joachim
is rather what useful functionality those objects would bring?

For instance, what would be the use for the basis of a vector space?
Would I be able to define a scalar product to transform the vector
space into an Euclidean vector space where I can use the Gram–Schmidt
process to transform the basis into an orthonormal basis?

What about groups? Are there, for instance, algorithms to enumerate
subgroups of a group, or give the group from only defining some
representation? Check that an action is this and that... Concerning
groups, there is another recent thread about gsoc that you might want
to check.

Anyway, I suppose that such examples will be an invaluable addition to
your application (however do not take me for my word, I am also an
applicant, not a mentor).

Stefan

[Alan Bromborsky]

You might want to look at the documentation for the geometric algebra module for some ideas

    http://docs.sympy.org/0.7.1/modules/galgebra/GA/GAsympy.html

I am currently doing a complete rewrite of the module since the original version is not very extensible (pythonic) and does not use sympy in an optimum way for implementation (not to mention that due to the way it is written I have trouble understanding the code I wrote a few years ago).

[Joachim Durchholz]

Am 18.03.2012 20:17, schrieb krastano...@gmail.com:
> I might be wrong, however the way I understand the question by Joachim
> is rather what useful functionality those objects would bring?

That, and the examples that you mentioned, were what I was after.

[Saptarshi Mandal]

Hi,

> Under group theory(and ring theory) I intend to implement the following:
>    subgroups, normal and quotient groups, homomorphisms on groups and
> permutation groups.
>

I already have done some work on Permutation groups. Check out my
branch.

> Under vector spaces:
>    basis for a vector space, dual vector spaces and modules
>

How will this work? Do you have a reference you are working with?

> Field theory however has a much larger scope for implementation since it

Cheers
Saptarshi

[Gaurav Sathe]

Hi Joachim,

To answer your question the following operations can be implemented:

A)Under the group theory module: 

1) an algorithm to check if a set is a group(abelian also)... if True what is the Identity element,inverse of each element etc

   eg.   >>> G.isgroup()

          >>> G.isabelian()

2) an algorithm to check if a subset of a group is a subgroup

  eg    >>> A.issubgroup(G)

   if True then if A is a normal subgroup of G

I can also implement a method to create left and right cosets of a subgroup.

3) If a ∈ G, what is the order of a... is 'a' a generator for G    eg.  >>> a.order(G)

4) if H and K are two subgroups the define HK... check if HK is a subgroup of G     >>> HK.issubgroup(G)

5) if H is a subgroup of G then define the quotient group G/H as the set of all right cosets  

6) Homomorphism: If G and H are two groups and if Φ is a mapping between them then is Φ a homomorphism... if True what is the Kernel of Φ

7) Is Φ a 1-1 map(isomorphic)

I think some work on permutation groups has already been done... I could implement whatever is not there right now

Also all the above operations can be implemented for a Ring

B)Under vector spaces:

1) an algo to check if a set V is a vector space over a field F

2) if Φ is mapping between two vactor spaces then is it a homomorphism and 1-1

3) Find the basis of V and hence find dimension(V). Similarly finding dimension of a vector subspace

4) Then if B is a basis I can implement the Gram Shmidt process as Krestanov said to get an orthonormal basis for V

These are few of the operations that I have though of right now... I am sure many more can be implemented which can be added to the above list. I am trying to figure out what all I can implement from field theory. Please let me know if u think of anything more

Thnx,

Gaurav

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To post to this group, send email to sy...@googlegroups.com.

To unsubscribe from this group, send email to sympy+unsubscribe@googlegroups.com.

[David Joyner]

On Tue, Mar 20, 2012 at 2:18 AM, Gaurav Sathe <gaurav....@gmail.com> wrote:
> Hi Joachim,
>
> To answer your question the following operations can be implemented:
>
> A)Under the group theory module:
> 1) an algorithm to check if a set is a group(abelian also)... if True what
> is the Identity element,inverse of each element etc
>    eg.   >>> G.isgroup()

Wouldn't this require knowing the operation as well?

>           >>> G.isabelian()
>
> 2) an algorithm to check if a subset of a group is a subgroup
>   eg    >>> A.issubgroup(G)
>    if True then if A is a normal subgroup of G

???
There are subgroups which are not normal.

>
> I can also implement a method to create left and right cosets of a subgroup.
>
> 3) If a ∈ G, what is the order of a... is 'a' a generator for G    eg.  >>>
> a.order(G)
> 4) if H and K are two subgroups the define HK... check if HK is a subgroup
> of G     >>> HK.issubgroup(G)
> 5) if H is a subgroup of G then define the quotient group G/H as the set of
> all right cosets

I guess you mean group of all right cosets, but then the question is how do
you define the multiplication table? For example, do you return the
quotient group as another permutation group (isomorphic to the group of
right cosets)?

>
> 6) Homomorphism: If G and H are two groups and if Φ is a mapping between
> them then is Φ a homomorphism... if True what is the Kernel of Φ
> 7) Is Φ a 1-1 map(isomorphic)
>
> I think some work on permutation groups has already been done... I could
> implement whatever is not there right now

...

>
> These are few of the operations that I have though of right now... I am sure
> many more can be implemented which can be added to the above list. I am
> trying to figure out what all I can implement from field theory. Please let
> me know if u think of anything more
>
> Thnx,
> Gaurav
>
>
>
> On Mon, Mar 19, 2012 at 1:29 AM, Joachim Durchholz <j...@durchholz.org> wrote:
>>
>> Am 18.03.2012 20:17, schrieb krastano...@gmail.com:
>>
>>> I might be wrong, however the way I understand the question by Joachim
>>> is rather what useful functionality those objects would bring?
>>
>>
>> That, and the examples that you mentioned, were what I was after.
>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "sympy" group.
>> To post to this group, send email to sy...@googlegroups.com.
>> To unsubscribe from this group, send email to

>> sympy+un...@googlegroups.com.

>> For more options, visit this group at
>> http://groups.google.com/group/sympy?hl=en.
>>
>
>
>
>
>
>

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To post to this group, send email to sy...@googlegroups.com.
> To unsubscribe from this group, send email to

> sympy+un...@googlegroups.com.

[Sergiu Ivanov]

Hello,

Since the thread is about "fundamental algebraic structures", I'd like
to voice in. While group theoretical stuff is mainly discussed in
this thread, I'd like to point out that it would be nice (at least in
my opinion) to start the implementation from the fundamental
components of algebraic structures: operations. I'm trying to say
that I think that a group should be defined as an algebraic structure
with a single operation which has a number of properties; thus we may
define a class UniversalAlgebra, then derive Semigroup from it, then
Monoid, then Group. This would be similar to defining log as a
subclass of Function.

Once this architecture is set up, one will be able to (much easier)
add any other algebraic structure to SymPy. (I'd be interested in
adding lattices, for example.)

SymPy includes the classes AssocOp and LatticeOp; these may be used in
setting up the architecture I'm talking about. However, I think a
more general Operation class would be necessary.

This is would also make adding category theoretic things much easier :-)

I'd be glad to hear opinions on this idea :-)

Sergiu

[David Joyner]

I think this is great in principle (and this is the way Sage does this)
but in practice for an undergraduate student lacking in mathematical
sophistication, it is IMHO too optimistic.

My guess is that it is easiest and most practical to implement
(a) permutation groups and some basic algorithms
(b) finite rings, such as ZZ/nZZ, and some basic algorithms
(c) finite fields and some basic algorithms
(d) vector spaces over finite fields and their subspaces (ie,
linear block codes) and some basic algorithms

Just doing (a) properly would be a full summer project I think.

Hopefully the implementations are written clearly enough
and with some similar framework that they can be fit into
the more abstract category-theoretic framework that you describe.

Anyway, that's my 2 cents:-)

>
> Sergiu

>
> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To post to this group, send email to sy...@googlegroups.com.

> To unsubscribe from this group, send email to sympy+un...@googlegroups.com.

[Gaurav Sathe]

You are quite right David...

But i feel working only on permutation groups and some basic algos on it wont take up around two and a half months of summer since some work has already been done on it before.

I am sure along with that it would be possible to do atleast one more topics from the ones you have listed... maybe a smaller topic such as vector spaces and some of its algos.

Also if we make a module for the group structure we can make one for rings and fields... but include only the basic operations which also come under the group module. We could leave out the complicated stuff(like Eucledian Rings)

I think implementing all of the above in the time frame of a summer is quite possible.

-Gaurav

[Joachim Durchholz]

Am 20.03.2012 15:24, schrieb Sergiu Ivanov:
> I'm trying to say
> that I think that a group should be defined as an algebraic structure
> with a single operation which has a number of properties; thus we may
> define a class UniversalAlgebra, then derive Semigroup from it, then
> Monoid, then Group. This would be similar to defining log as a
> subclass of Function.

I have seen this kind of approach work excellently in Eiffel.

Unfortunately, it will run into trouble as soon as we need to inherit
the same algebraic data structure in two different roles.
For a handy example, Group cannot simply inherit from Monoid, since it
builds on two different monoids, the additive one (operator: +; neutral
element: Zero) and the multiplicative one (operator: *; neutral element:
One).

This can be circumvented: don't make Group inherit from Monoid twice,
make Group contain two Monoid members.

The question now is how to deal with those cases that could indeed be
done via inheritance (Monoid and Semigroup).
Alternative 1: Stick with inheritance. Might simplifiy some code (I have
no idea how much that would be in practice though).
Alternative 2: Make it a member, just for uniformity. Lowers the entry
barrier: new coders won't have to learn different coding patterns
depending on ancestry.

[Sergiu Ivanov]

On Thu, Mar 22, 2012 at 11:08 PM, Joachim Durchholz <j...@durchholz.org> wrote:
> Am 20.03.2012 15:24, schrieb Sergiu Ivanov:
>
>> I'm trying to say
>>
>> that I think that a group should be defined as an algebraic structure
>> with a single operation which has a number of properties; thus we may
>> define a class UniversalAlgebra, then derive Semigroup from it, then
>> Monoid, then Group.  This would be similar to defining log as a
>> subclass of Function.
>
>
> I have seen this kind of approach work excellently in Eiffel.

Excellent news :-) I'm glad to hear it's not only me who thinks this
way is among the appropriate ways.

> Unfortunately, it will run into trouble as soon as we need to inherit the
> same algebraic data structure in two different roles.
> For a handy example, Group cannot simply inherit from Monoid, since it
> builds on two different monoids, the additive one (operator: +; neutral
> element: Zero) and the multiplicative one (operator: *; neutral element:
> One).
>
> This can be circumvented: don't make Group inherit from Monoid twice, make
> Group contain two Monoid members.

Yes, sounds good to me.

(By the way, we are probably talking about rings, because groups have
only one operation; this doesn't matter too much though, everyone has
got the idea, I think.)

> The question now is how to deal with those cases that could indeed be done
> via inheritance (Monoid and Semigroup).

[...]

> Alternative 2: Make it a member, just for uniformity. Lowers the entry
> barrier: new coders won't have to learn different coding patterns depending
> on ancestry.

This option sounds like the best choice to me. Do you envision much
trouble with this approach? To me, it looks rather straightforward.

Sergiu