On Tue, Feb 14, 2012 at 2:45 AM, Aaron Meurer <asmeu...@gmail.com> wrote: > On Mon, Feb 13, 2012 at 4:21 AM, Sergiu Ivanov > <unlimitedscol...@gmail.com> wrote: >> >> 1. Karr algorithm >> >> 2. Improvement of Groebner bases >> >> 3. Improvements to the poly module > > What do you mean by relevance? Those are all relevant to SymPy. If > you want to sort by importance, then they are ordered from less > important to more important the way you've listed them.
Hm, I see. Although it's kind of obvious, I'd still like to make it explicitly clear that, of all the tasks I could potentially commit to, I'd rather choose the subset of tasks which are more likely to be accepted, that's why the question. > Pretty much all the algebra related ideas are relevant enough to be a > good project. I'd still need more convincing for category theory > (i.e., more specifics about what the module would look like). This is how I envision the structure of a module that would approach the problems I described. It should include a Python class to represent an abstract category (call it Category), another one for an object (CategoryObject) of the category and another one for a morphism (CategoryMorphism). Category must expose a method to test whether a CategoryObject is contained in it; likewise for CategoryMorphism. CategoryObject must have a name. CategoryMorphism must have a name and references to its domain and codomain. In the cases of concrete categories the user is expected to derive their own classes which would define the corresponding structure. For example, for the category of groups, a GroupObject should include a reference to the set over which it is defined and (symbolically) define the group operation. Correspondingly, a GroupMorphism should define a (symbolic) transition from an element of its domain to an element of its codomain (like, a -> a/2). The class GroupCategory, derived from Category, has the responsibility to check whether an instance of GroupObject is indeed a group and whether a GroupMorphism is indeed a group morphism. As you can see, all of this stuff relies very heavily on symbolic computations. Further, the module should contain a class Diagram, which contain a collection of CategoryObjects and corresponding CategoryMorphisms. Diagram should be able to draw itself and, I'd like this one as well, pretty print itself to the isympy console. Diagram should also support annotating every object it includes. In this way, some additional information can be included in the diagram, like the values of concrete elements we pick out in the objects. Obviously, the scent of graph theory can be sensed here. However, an algebraic diagram is a very specific type of graph. One of the most important specific details is that the dimension of a diagram is very small, on graph scale: I've rarely seen diagrams containing more than 20 objects (actually, I don't think many people have seen/drawn such diagrams). As I said earlier, there are two essentially different ways of checking the commutativity of a diagram. For a concrete category, the problem is in checking the equivalence of paths from A to B, where A and B and are arbitrary sources and sinks in the diagram. Here, obviously, I'm going to rely on symbolic calculations a big deal, while the graph theoretical part is quite trivial (find the sources and sinks, traverse all paths). This functionality may fit within a single function or it might be factored out in a class and a couple satellites if need be. The other way of checking commutativity is for abstract categories. I think this capability should be central to the tool and I expect it to require the better part of the effort. I expect to see something like a class AbstractCategory, which should be able to accept a list of diagrams which are *assumed* to be commutative. Checking the commutativity of a diagram in this setup would include considering the embeddings of the diagrams known to be commutative. Apparently, the scent of graph theory becomes very powerful here. However, the algorithms I am going to need are quite specific and aren't really relevant outside the domain I'm considering. With the simplest approach, I need to find *all* possible embeddings of every diagram and then consider *all* possible combinations of such embeddings. Every found embedding states that a certain part of the diagram in question is commutative. The problem is how to interpret a combination of embeddings. Right now I have the following idea: suppose I have found that two subsets of objects A and B of the diagram in question (together with the corresponding morphisms) form commutative (sub)diagrams. If the intersection of A and B is not empty, then the combination of objects A U B (union of A and B) together with the corresponding morphisms, forms a commutative diagram as well. Therefore, the straightforward way to see if a diagram is commutative is finding all possible embeddings of the diagrams known to be commutative, start from one of the embeddings and try to find embeddings which have common points with this one. Then, attempt to increase the coverage of the initial diagram and see whether it can all be covered. If no, drop the current route and start with another one. Now observe that I'm talking of "embeddings of diagrams" rather than "embeddings of graphs". The reason for this is that, when one has a diagram, one essentially considers the reflexive and transitive closure of the underlying graph. This, I believe, may make it easier to solve the problem of finding an embedding. Observer further that, beyond finding embeddings, the problems I describe are quite specific to category theoretic reasoning. I've skimmed the pages http://networkx.lanl.gov/contents.html , http://code.google.com/p/python-graph/ , and I've also read attentively http://wiki.python.org/moin/PythonGraphApi , and I've found little related to what I'm suggesting. Now, diagrams can actually include more information than I have already described. A commutative diagram which describes a property is usually specified as causal relation (like, if there is a morphism A -> B with <property1> and a morphism B -> C, then there *exists* a morphism A -> C such that <something>). Therefore, checking whether a given diagram is commutative does not only consist in finding embeddings, but rather, in finding the embeddings of the causal parts of diagrams (and checking the properties of the morphisms and objects specified in the causal parts) and in adding the inferred objects and morphisms, together with their properties. All this additional properties are, obviously, going to be stored in Diagram. This whole explanation makes me feel that the module I am talking of is very much similar to a proof checker. While I am still interested, I'd like to hear an assessment of how relevant to SymPy this could be. > I recommend that you pick an idea that is interesting to you and > research it so that you understand exactly what needs to be done in > SymPy to get it to work (and don't worry, we are here to help with > that too). And also, make sure that you have a good enough feel for > the mathematical background required for the project that you can do > it. It's OK if you haven't studied the thing itself yet, but you > should have all the prerequisites, so to speak. Oh, great, thank you :-) In this case, I'll have to confess that I've been musing on the perspective of working on Karr a couple days, and I feel like I'm more attracted to the problems listed here https://github.com/sympy/sympy/wiki/gsoc-2012-Ideas under the title Polynomials module. My interest decreases the way the ideas are ordered there, i.e., I like the idea about the Groebner bases most. Therefore, in accordance with your suggestion (I believe) I'll find some papers on this topic and, specifically, Faugere F4 (since F5 has already been implemented, I think). (BTW, I'm not saying that Karr is not interesting, it's just that I don't somehow feel emotionally attached to it :-) ) I am, of course, still willing to work on the commutative diagram tool, but I'm only in case you deem it relevant *and* important :-) 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.
