On Oct 21, 2013, at 1:15 PM, "F. B." <[email protected]> wrote:
Hi, I was considering pattern matching for tensor expressions. Pattern matching on tensor expressions should work by components and by indices. Do you think that the existing pattern matching in SymPy can be used on tensor expressions to efficiently select/pattern replace subexpressions? I don't think so, but maybe I'm wrong. I don't know. You'll have to try it. Also try using xreplace and sympy.core.rules.Transform. I'm becoming convinced that those two make complex replacement more elegant and readable than any other combination of functions currently in SymPy. Aaron Meurer In any case, I made some research this weekend and I concluded that graph algorithms would be a good point for pattern matching in tensor expressions. A tensor expression can be regarded as a graph, components are the vertices, while contracted indices are the internal lines, and free indices are either external lines or lines connecting to a special vertex. Have a look at: http://en.wikipedia.org/wiki/Penrose_graphical_notation The pattern search problem is equivalent to finding an isomorphism between a subgraph to a part of a larger graph. A nice implementation of this is Ullmann's algorithm, which, in short, finds a permutation matrix between two adjacency matrices (each one representing a tensor expression). If applied to a tensor expression, such an algorithm would require some modifications, like: - handle free/contracted indices. - care for index symmetry. - care for tensor components commutation relations. - match indices in different order only if there is a symmetry which keeps the tensor expression identical on index exchange (save for a possbile negative sing). Do you think that an stand-alone pattern matching algorithm could be worth writing? Or do you think that it should be integrated with existing parts of SymPy? -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sympy. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sympy. For more options, visit https://groups.google.com/groups/opt_out.
