Hello, On Fri, Feb 10, 2012 at 6:42 AM, Aaron Meurer <asmeu...@gmail.com> wrote: > > I would recommend using your algebra knowledge, as few people have > this, but it's very important to computer algebra.
OK, understood :-) >> One of the other ideas that interest me is "Groebner bases and their >> applications in geometry, simplification and integration". I've only >> started the course in Gröbner bases, so I can't claim being >> knowledgeable, but I will have graduated the course by the beginning >> of May, which is before the start of coding time, and which means that >> I should be quite prepared to work on this task by that time. > > This would be a good project. There was a project for Groebner bases > last year, and the page hasn't been updated yet, so you should look at > the current status. From what I understand, there is still work that > can be done in this area, especially regarding applications of > Groebner bases (which is why they are important to us anyway). Hm, I see. Yes, I can find confirmations here http://bit.ly/A4HKaY and on SymPy's GSoC-2012 ideas page ( http://bit.ly/y47J9h ). > I think Mateusz can give you a more detailed status update. It would be great if he could join the discussion. I'd be willing to work on any algebra-related task, and I'm willing to take up projects which rank as hard. It is important thus that I know which of the such projects are of more relevance to SymPy. >> There's extra motivation for me to work on Gröbner bases: a part of >> the research I'm part of now focuses on this object. > > Cool. What is the research on, if you don't mind me asking? I am part of a team which does research in biocomputing. My current focus is mostly on P systems ( http://en.wikipedia.org/wiki/P_system ), but the team works with different biologically inspired computational models. Among our goals is solving computationally hard problems with biologically inspired methods and, namely, we would like to find a better way of computing Groebner bases. It would thus be great for me to get a good feeling of these objects, because this knowledge would be applicable elsewhere as well. >> Finally, I'd like to suggest an idea of my own. Since I'm studying >> category theory now (and I don't think I'm ever going to put this >> instrument aside), I'm dealing with commutative diagrams quite often. >> It would be great to have a tool which would be able to allow one >> solve typical problems about commutative diagrams, like: > > Well, to approve it, you'll need to be more detailed. I don't know > anything about category theory, but maybe others do. Yes, I see. One of the reasons I didn't offer a proper presentation of the idea was that I know some people don't like category theory (at least I was told so), thus I wanted to make sure I wasn't going to offend anyone :-) In what follows I'll try to provide a very brief introduction to the relevant parts of category theory. I'll assume a fair understanding of set theory and group theory, and zero knowledge in category theory itself. I hope I'll manage to keep everything intelligible and unboring. Category theory stems from the observation that a large part of a theory about a certain kind of algebraic systems can be described by some reasoning about the systems and their homomorphisms. Consider, for example, the three isomorphism theorems in group theory: http://bit.ly/zu5pZ8 . These statements only talk about groups and relationships between them described by certain group homomorphisms. A category is defined as a structure consisting of two classes: the class of objects and the class of morphisms (sometimes called just arrows). The term "class" is used in set theoretical meaning. For example, the category of groups contains the class of all groups and the class of all group (homo)morphisms. When reasoning about certain algebraic systems and the corresponding (homo)morphisms, one often runs into patterns of structures. For example, in the case of the first isomorphism theorem for groups ( http://bit.ly/zu5pZ8 ), one talks about a morphism f:G->G', a quotient group G/ker f, a subgroup of G': Im f, and about the morphism pi:G->G/ker f and the isomorphism phi:G/ker f->Im f. It is useful to represent such relations graphically, as seen here: http://bit.ly/z5Z4Jq . Such patterns of structures are called diagrams. Graphical representations of diagrams generally depict objects as points and their morphisms as arrows. This is an example of a graphical representation of a diagram: A -(f)-> B -(g)-> C. The path A-B-C, obviously, represents a morphism h:A->C, h = gf. Consider a certain diagram and fix two objects A and B in it. If all paths from A to B yield the same morphism, these paths are said to commute. If, for any pair of objects A and B, all paths from A to B commute, the diagram is called commutative. Commutative diagrams are often used to describe and/or deduce properties of certain constructions. Commutative diagrams are an extremely important instrument in category theoretical reasoning and, re-quoting the corresponding Wikipedia article, "Commutative diagrams play the role in category theory that equations play in algebra." Now, there are basically two different approaches to reasoning in category theoretic way. The first one is about abstract categories: one takes the notion of the category, maybe requires some properties of it, and then plays with what one has. The second approach is about concrete categories: one takes a certain category (category of all sets, category of all groups, etc.) and starts by applying the reasoning from abstract categories. Eventually, one constructs a specific theory with category theoretical basis, which has its own individuality among theories about other concrete categories. These two approaches are directly reflected upon how commutative diagrams are used. For example, in concrete categories of algebraic systems, one knows that the objects are sets with some structure. In that case, when one has a diagram, one can do diagram chasing ( http://bit.ly/x6MAwc ), which basically consists in fixing a node in the diagram, fixing an element in this node, and then checking how the morphisms included in the diagram act upon this element. The approach described in the previous paragraph is obviously impossible when talking about abstract categories, the objects of which are not necessarily sets. In abstract categories, properties are formulated in the form of commutative diagrams. Denote, for example, by Prop the set of diagrams describing the initial properties of a category. Then, checking if a diagram D1 is commutative in this category can be reduced to finding all possible "embeddings" of diagrams in Prop into D1 and checking whether these embeddings are sufficiently "well placed" to assure that D1 is commutative. I will now try to describe what I would like to see a commutative diagram tool do for me. This is going to be a kind of a wish-list; I will not necessarily have the time to implement *all* of these in a summer. The tool should be able to 1. allow the user to describe a category, by specifying some of the properties in the form of a set Prop of predicates over objects and morphisms, but also by directly implementing morphisms as functions, when possible/necessary; 2. check whether a given object/morphism belongs to the category (satisfies the necessary clauses in Prop); 3. allow to construct a diagram, directly assert that it is commutative and state that the commutativity of the diagram is a property of a given category; 4. allow to visualise diagrams; 5. if in a concrete category with objects having underlying sets, allow to fix an element in a node of the diagram and trace the values it is carried into across the diagram; for example, consider the two ring automorphisms, with Q being the rational numbers: Q -(f)-> Q -(g)-> Q, where f(a) = a/2 and g(a) = 3a; I would like to obtain something like the following: Q{a} -(f)-> Q{a/2} -(g)-> Q{3a/2}; 6. if in a concrete category with objects having underlying sets, allow to check the commutativity of the diagram by taking all pairs of objects A and B in the diagram, taking the generic symbolic representation of the elements in A and checking whether all paths to B lead to equivalent symbolic forms; note that it would be perfect to only check the paths from all sources to all sinks ("sources" and "sinks" in the sense of graph theory); 7. if in an abstract category, find all the necessary embeddings of the diagrams describing the properties of a category into a certain diagram D to show whether D is or is not commutative; 8. offer a database of canonical properties, expressed in diagrams (like isomorphism theorems). While I was listing these points, I have once again realised that the kinds of morphisms and objects are expected to vary widely. The tool should be able to work with objects ranging from concrete sets with operations to something with absolutely no internal structure. Similarly, morphisms may be direct formulae (like f(a) = a/2), or just pure arrows, with no more information beyond the mere fact of existence. I have also considered the possibility of allowing a morphism to be just any function, but this seems to nullify the usability of commutative diagrams, therefore, I think, in their most explicit form, morphisms should be functions (in Python sense) which transform one symbolic SymPy expression into another. (It has just struck me that morphisms which can do anything are actually more similar to functors, but that looks beyond the subject of this letter.) Apparently, doing stuff about commutative diagrams implies applying graph theory, which I am of course going to do in order to achieve acceptable performance. > Basically, you need to convince us: > > - that the idea is within the scope of the project, Commutative diagrams are used in a broad range of situations and proved to be a very powerful instrument. However, I haven't yet managed to find a tool that would do the things I enumerated above. Adding this functionality to SymPy will thus give it unique value. Category theorists will be able to formally check their results, which is crucial in formal science. On the other hand, using an automated commutativity checking tool, researchers will be able to verify more possibilities with much less effort, because the tedious part of finding the proper patterns in the diagram will be offloaded to SymPy. As I can see, the scope of SymPy is fairly broad: it even includes a physics module. Considering the fact that category theory reasoning has gradually become an essential technique in algebra, I am totally convinced that adding category theoretic tools to SymPy is not only relevant, but kind of required by the evolution of modern maths :-) > - that the idea constitutes enough work to be sufficient for a summer > project, and Consider the list I have produced above. Item 1 implies setting up a hierarchy of classes to represent categories, objects and morphisms. As I remarked immediately after the list, these representations are not going to be trivial. Item 4 poses a modified version of the classical difficult problem of graphically representing a graph. The modification is that, in representing commutative diagrams, it is not necessary to represent the morphism A->C if the morphisms A->B and B->C are already represented. Item 7, the hardest one, will require adapting more than one nontrivial graph theory algorithms. Finally, item 8, while not apparently necessitating too much mental effort, may require another week to work on. On the overall, I estimate that the amount of work is quite sufficient for the time frame of a summer, provided that I will also have to produce documentation, test my code, and have it reviewed. > - that you can implement the project. I used to take part in various programming contests for a number of years. I have never been hard-working enough back then to do much good at international olympiads, but I consistently ranked slightly below the guys who did. Although this was quite some time ago, I haven't got much worse at algorithms, including graph algorithms. I believe that, at the university, I have successfully implemented all the essential solutions which I am going to need in the commutative diagrams tool. I have what I believe to be a rather good understanding of OOP and a slightly worse understanding of functional programming (I've been programming in Haskell for two years already, my graduation project had one of the core parts written in Haskell). I've had some experience with Wolfram Mathematica, a much larger exposure to Matlab, and a yet much larger exposure to Scilab. I am going sit down on all of the above and say that I believe that I'll be able to not only implement the commutative diagram tool, but also do it efficiently, elegantly, and in compliance with SymPy's coding standards :-) Despite my "arguments", obviously, I can't but ask you to trust me on the fact that I'm any good. To materialise the argumentation, I'll now start fulfilling the patch-fixing requirement (which I haven't started yet because of the illness). >> I hope that I did manage to express my enthusiasm sufficiently well >> :-) > > Yeah, you did :) Great to hear :-) Sergiu -- You received this message because you are subscribed to the Google Groups "sympy" group. To post to this group, send email to sympy@googlegroups.com. To unsubscribe from this group, send email to sympy+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
