On Wed, Feb 15, 2012 at 9:37 AM, Sergiu Ivanov <unlimitedscol...@gmail.com> wrote: > 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.
The best chances to be accepted are to sell yourself, not so much your project. > >> 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). >From what I remember, there were problems implementing F4 because of our linear algebra module (i.e., the matrices) were too slow to really make the algorithm efficient. So if you want to implement an algorithm that uses linear algebra extensively, you'll probably need to improve the matrices as well (which could in itself be a project). > > (BTW, I'm not saying that Karr is not interesting, it's just that I > don't somehow feel emotionally attached to it :-) ) Then don't do it. This was just a suggestion. We definitely want you to do a project that you want to do, as this greatly increases its chances of success. > > 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 Is category theory used outside category theory? If so, maybe you could give an example showing how the module might be used to solve some actual problem. I remember reading that category theory has been called "general abstract nonsense" which is probably why I'm still having a hard time grasping onto it, or at least its usefulness. I'll try to read through the Wikipedia article as well. Aaron Meurer -- 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.
