Am 25.04.2014 00:52, schrieb Ondřej Čertík:
On Thu, Apr 24, 2014 at 11:58 AM, Matthew Rocklin <[email protected]> wrote:
We only need things
like multi-pattern unification and AC unification.
I do not know what exactly these are.
I read that AC unification can be polynomial, which sounds like a
potential performance bottleneck; do we really need it?
Given expression (like sin(2*x) + cos(2*x)) we need to match against many
possible patterns (like, every known trig identity).
I'm assuming that this is what was meant by "multi-pattern unification".
It's essentially a search in a potentially infinite decision tree. I
think that's already polynomial, possibly even undecidable.
>> It's possible to store
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 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.
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 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/535A04C8.6050000%40durchholz.org.
For more options, visit https://groups.google.com/d/optout.
