>>>> all of the patterns in a good data structure so that we can check them >>>> all >>>> simultaneously (see Trie for something similar). We need to do this >>>> matching in a way that is aware of commutative operators (like +). >>>> Naive >>>> solutions to this are very slow. There exists sophisticated solutions. >> >> >> Can't we deal with commutativity by normalizing the tree? >> E.g. in polynoms, it's already commonplace to put the higher exponents to >> the left; set up a total order over expressions that includes this and >> similar conventions. >> Similar for associative operators; there, we turn A+(B+C) into plus(A,B,C) >> and don't have to worry about burdening the unification algorithm with >> semantic subtleties. > > > For commutativity, yes, for associativity and commutativity no. > > Match x + B to A+B+C. This problem is typically solved for a single > pattern by performing a bipartite matching. It's more complex when there > exists several patterns and you don't want to check each of them linearly. >> >> >>> For trig simplification, there is a paper that I think uses some >>> systematic way >>> to simplify it. So it might be that for that you don't need to check >>> all the trig >>> identities. > > > Yeah, so this is actually in SymPy. Chris Smith already implemented this > in fusimp. Note that this doesn't use pattern matching but it does search > through a tree of small transformations. > > >>> fu(sin(x)/cos(x)) # default objective function > tan(x) > >>> fu(sin(x)/cos(x), measure=lambda x: -x.count_ops()) # maximize op > count > sin(x)/cos(x)
This is impressive!! It can do stuff like this: In [3]: cos((x+y)/2) * sin((x-y)/2) Out[3]: sin(x/2 - y/2)*cos(x/2 + y/2) In [4]: fu(_) Out[4]: sin(x)/2 - sin(y)/2 In [7]: sec(x) / (2*sin(x)) Out[7]: sec(x)/(2*sin(x)) In [8]: fu(_) Out[8]: 1/sin(2*x) I had no idea that this was implemented. That's very exciting. Ondrej > > I used the strategies module to pull out the tree search stuff. See either > sympy.strategies or github.com/logpy/strategies/ > It is used in fu simp here > > https://github.com/sympy/sympy/blob/821fc389bcb7285555f6ec46c32afa38faceeab1/sympy/simplify/fu.py#L1597 > >> I think that's the general approach. Do not exhaust the decision tree, >> follow a search strategy. >> Applies to trig, integrals, polynom simplification, and probably almost >> all areas of mathematics. >> >> Can this be captured as a simple priority value on each substitution rule? > > > You can get pretty far with a simple priority value. Often times greedy > solutions don't produce optimal results. My solution to this is to follow a > greedy solution but then allow backtracking, allowing the user to ask for > extra results. > > -- > 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. > To view this discussion on the web visit > https://groups.google.com/d/msgid/sympy/CAJ8oX-GKTNEkdakDCJf-eSW70cRC4xPD_dnyCQjAuTrLtgEFKw%40mail.gmail.com. > > For more options, visit https://groups.google.com/d/optout. -- 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. To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CADDwiVBhF5gtUfzr7iCXJQbix8ecfVdt%3DWCyykxFdFoiCpFzEw%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
