Domain of validity of simplifications?

[gwhitney]

Now that there are some slightly non-trivial array simplifications (and mathjs is veering ever-closer to a full-blown CAS), I think it really raises the issue for simplify as to the domain over which the simplifications should be valid. For example, if I am working with matrix formulas and call simplify on them, I will find that all of my (fairly common) terms like X*M*X^(-1) are turned into just M which will totally destroy my results. Or in another vein, to fulfill #927, it might seem reasonable to add something like sqrt(x^2) -> abs(x) but this is only valid over real numbers, not complex numbers (one can find many other such examples). How should mathjs and simplify handle this sort of thing?

I guess the null possibility is to just declare that simplify performs simplifications valid over [domain X] and document and stick with that. (Seems like it somewhat curtails the potential utility of simplify, though.)

Another possibility that comes to mind is to add a new allowed key to the "options" argument called something like 'domain', with canned possible values like 'real', 'complex', 'matrices', etc.

Or there is already an internal options parameter called "context" that specifies such things as whether multiplication is commutative, etc. So simplify could just include a "context" key in the "options" parameter so that a client could specify whichever properties are true of the operations over the domain the client is considering. (We might need some additional context possibilities, though, to cover differences between reals and complex numbers that are not captured just by what laws the basic operations satisfy.)

Or there may be other possibilities. If you're still interested in a PR for #927, some guidance on this question would be very helpful.

[gwhitney]

Actually, I think this issue is more pressing than just whether to pursue #927: besides the issue of commutativity of multiplication, meaning mathjs is oversimplifying if the formulas concern matrices, in the current release (10.1.0, and probably before), simplify() is performing simplifications that are not even valid on all real numbers, e.g. x/x which is being simplified to 1 even though that's only valid for x not equal to 0. So if someone is expecting simplify to preserve the value of an expression for all real numbers, that's not happening. Perhaps PR #2388 should be held up (since it simplifies even more fractions) until there's a design decision on determining what collection of simplifications to perform, and a fix implementing that is in?

[gwhitney]

(Not to cloud the issue, but there's also the question of whether you'd want mathjs to handle different domains for different variables, e.g. "x is an arbitrary real number, k is a positive real number, M is a matrix with real entries, and z is a complex number" so that the rules that would apply in simplifying would depend on which variable(s) were involved in the subexpression being matched.)

[gwhitney]

Some further reflection: one "complete" solution to this issue would involve annotating every Node with a type, and then using that type to create a context of what the properties of operations are at that node. This is not difficult in theory: the client would pass in the types of all symbols (which could default to something like "real" for any symbol not mentioned), and then types would propagate up the parse tree. But there are two difficulties with such a solution: (a) the typed-function library does not currently include return types in the signatures, so there's not an existing way to propagate types up through a function call. So typed-function would have to be extended to include those, and return types would have to be added to all existing functions. (b) since what we really care about for simplify in the end are operation properties like "is multiplication commutative" or "is this value invertible" the type system might need to be more refined than it currently is, say including concepts like "positive real" as well as just "real", or even "integer" for some simplifications. And it's not clear how those sorts of "mathematical properties" types mesh with the actual currently existing type system of JavaScript types like number, bignumber, Matrix, string, etc.

So an approach along those lines would become a long-term project, potentially interacting with some of the major architecture issues facing mathjs like #2076 etc.

On the other hand, since it's the operation properties that matter, something like allowing a context in the options parameter that's presumed to hold at all nodes in the expression would get a very large part of the way there and seems immediately practical with a reasonable PR that I'd be happy to prepare. (It just couldn't handle knowing that k*X*M*X^(-1)*k should simplify to k^2*X*M*X^(-1) but not k^2*M if k is real and X and M are matrices.) To get the current state of affairs mathematically correct, there would need to be some new properties in the context considered, especially whether multiplicative inverses are always allowed, which would default to true to get behavior similar to the current. (Note that even x^a*x^b simplifying to x^(a+b) is not valid if inversion is not allowed, since the former evaluates to undefined on {x:0,a:-1,b:2} while the latter evaluates to 0.

Looking forward to your thoughts; I am happy to move forward in whatever direction you think this should go, as a highly functional simplify() is very important for my application.

[gwhitney]

I think the leading candidate here is to allow a context to be passed in among the options to simplify. As of now, the context consists of properties that functions might possess: commutative and associative. Here's an initial stab at other function properties we would want to track to be able to determine exactly which simplifications were valid:

invertible - whether an inverse for that operation always exists. This would default to true for addition and multiplication, to match current behavior; the simplification n^n1*n^n2 would be marked as only applying if multiplication is invertible.
total - whether the operation is always defined. A function node would only be allowed to be eliminated if the associated function is total. So for example a potential rule exp(log(n) -> n would be blocked from applying if log was not total in the context, and similarly with (sqrt(x))^2.
trivial - whether the operation has no effect. This would always default to false. But some functions are trivial in some contexts and so could automatically be eliminated. For example, in a context to reflect positive reals, abs could be marked as trivial.

I'd suggest that the default context would maximize the amount of simplification allowed, except that no functions would be marked as trivial in the default context. And I'd suggest that mathjs provide some built-in contexts like 'realContext', 'complexContext', 'matrixContext', maybe 'positiveRealContext', etc. so that clients could easily perform only the simplifications guaranteed to be valid for all elements of the domain corresponding to the context.

I think this plan would cover a very large fraction of use cases for simplify().

[gwhitney]

It's gratifying to see that basically the two main options suggested here are already mentioned in a comment near the top of function/algebra/simplify/util.js:

 // The properties should be calculated from an argument to simplify, or possibly something in math.config
  // the other option is for typed() to specify a return type so that we can evaluate the type of arguments

I am happy to take a stab at the "properties calculated from an argument to simplify" (namely, a context passed in as the context property of the options argument). I think at least at first, this won't need both "invertible" and "total" -- I think that rather than checking whether * is invertible, it will be OK just to check whether / is total. So I will try to start with just commutative, associative, total, and trivial, and see if it's then possible to pin down whether each rule is applicable. I may as well give a PR for this a try; but if you think it's not a direction you want to go with mathjs please let me know. Thanks!

[josdejong]

Really good discussion, thanks Glen for bringing this up. Some first thoughts:

1. first thought: can we learn from other CAS systems, see how they solved this?

2. the "mathematical properties" that are relevant for the CAS (real/complex, positive/zero/negative/integer) are indeed differing from the types that mathjs has (number, BigNumber, Fraction, ...). I don't think that will bite each other.

3. I'd suggest that mathjs provide some built-in contexts like 'realContext', 'complexContext', 'matrixContext', maybe 'positiveRealContext', etc. so that clients could easily perform only the simplifications guaranteed to be valid for all elements of the domain corresponding to the context.

   Yes this makes sense to me, being able to configure what "domain" or "context" you need. I also think that implementing this is doable and will not let the code explode in complexity.

4. About keeping track on what type of value every individual variable contains: we could extend SymbolNode to hold this kind of information I think, should not be needed to extend typed-function. However I'm not sure if this would introduce a lot of complexity, both for the implementation as well as the user having to specify a lot. So my preference is to first explore how far we can get with a set of configuration options to define a context for an expression as a whole instead of individual variables.

5. Defining for relevant functions/operations whether they are invertable/total/trivial sounds good.

6. We need to decide on a good default: don't simplify unless explicitly configured (safe), or simplify as much as possible (convenient in most cases). It is an assumption, but I think most people will have a real context, so it makes sense to use that as default. If we don't do that, and simplify doesn't do much out of the box, people will probably think it doesn't work.

7. I'm thinking about the case of x/x you're mentioning. Are there many of these kind of cases? If we get strict about this, I can imagine many of the simplifications will not work anymore. Is this also worth creating a configuration option for?

[gwhitney]

1. (I'm not a big expert on other CAS, the following notes are based on reading their manuals just now.)
   SageMath has a raft of different simplify_XXX flavors, where XXX can be log, trig, real, factorial, etc., etc., and then a simplify_full() that calls all of them in a specific order. In the docs, most of the sub-functions have warning boxes saying which domains they are or are not valid over. Not clear to me that having multiple different simplify functions is better than an options parameter to a single simplify function.
   Maxima has a long list of different properties (commutative, lassociative and rassociative, linear, constant, even, odd, etc., etc.) that can be attached to any symbol to control how it will be simplified, and it has a long list of global variables that control the simplification algorithm (like 'domain' to control the domain over which simplifications should be valid, 'exponentialize' to determine whether to change trig functions to exponential form, etc. etc.) In addition, like mathjs it has a simplification function that takes an explicit list of rules to apply. So this is fairly similar to what we're proposing here except that rather than globally assigning properties to functions or setting global options as in Maxima, they are all in maths placed in the option argument to simplify. One main motivator for that difference is that in Maxima apparently all results are simplified automatically before being presented, so there needs to be some way to control that simplification since it is not called explicitly.
   SymPy more or less combines the above two: there is a raft of various sub-simplification-functions and a master simplify that tries them all, and you can set properties on various symbols to specify whether each of the sub-simplifications will apply to them.
   By contrast, MathStudio has just a few simplification functions (SimplifyPoly, SimplifyFunction that deals with transcendental functions, and TrigReduce) and does not mention in its manual any way of controlling the assumptions these functions make.
   I don't have access to Mathematica, but its manual is online. According to that, its simplify optionally takes any of the following: a list of assumptions on any of the symbols in the expression (such as positive or real or whatever), the complexity function to optimize, a list of patterns not to touch, a time limit on the search (!), an explicit list of rules to try, and a flag whether or not to use trig identities.

So I don't think the ideas we're considering are too far away from features of other systems.

4. I agree that each symbol could be annotated with information, like "real" or "complex" or "positive" or "matrix" or whatever, but the trick (and therefore the place it was seeming that typed-function might come in) is propagating those properties up the tree, i.e. you want to know that a real times a matrix is a matrix, that a row vector times a column vector is real, that the square root of a positive is a real but the square root of a real is a complex, etc. etc. Hence I agree with you that we should first implement global properties, and only later think about per-symbol or per-node properties -- they are not mutually exclusive by any means.

And finally

6. I agree the default context should be quite aggressive. I am working on a PR based on this discussion so far, and modeling the default context not to alter the current behavior of simplify at all, which means that it does some simplifications that are not valid for all real numbers. That means the realContext also supplied will be more restrictive; but hopefully it will still be useful for someone who wants to be certain to preserve the behavior of their expression on all real numbers.

7. Almost every one of the existing simplification rules have some assumptions they depend on. Some of them are assumptions like "addition is associative" that would be very unusual to not want, but there doesn't seem to be any harm in documenting the properties needed. And my proposal is that the default context will validate all of the existing simplification rules, which means it will include assumptions that are not true of all real numbers. That's why there will be a need for a realContext that has fewer assumptions and so simplifies a bit less. But it won't simplify ridiculously less: it can still turn (xzx - y^2x^2) into x^2(z-y^2), it just can't turn (x^2-x)/(x-1) into x, since that's not valid for x=1.

So it seems like we are reasonably on the same page. Some time this week most likely I will submit a PR in which:
a) the simplify options can include a context which is propagated down to all of the rule matching (actually, I already have that part working)
b) any rule can specify properties that must hold in the context for the rule to apply (still need to implement that)
c) each standard rule uses (b) for all its required properties (still to do)
d) a simplify.defaultContext is provided which allows all existing rules and is used as a fallback if there is no context or if the supplied context is silent on a property (done)
e) at least a simplify.realContext which limits simplify to only those rules valid for all real numbers (still to do, and maybe will include a few more contexts like complexContext or positiveContext or even integerContext -- the problem of course with the latter is that so many operators do not return integers, so not much simplification would be allowed, so it's not likely to be worth it).

This may be a large-ish PR so when you see it if you think it should be split up, just let me know.

[josdejong]

Thanks for sniffing around to see what appraoch other CAS applications took 👍

So I don't think the ideas we're considering are too far away from features of other systems.

Yes indeed. Good to see other systems like Maxima do have support for attaching properties to individual variables, we can learn from that.

Hence I agree with you that we should first implement global properties, and only later think about per-symbol or per-node properties

Yes agree, one step at a time :)