Suppose you are given a multivariable rational function f(x0,x1,x2,x3,..,xn), so the only four operation are +,-,*,/.
Assume that all constants and exponents are integers within certain range.
I need some kind of algorithm to answer the following:
- is f(...) monotonically increasing in x0 for any choice of variables x1...xn?
- does f(x0) have precisely five maximum/minimum points for any choice of variables x1...xn?
- and so on...
So essentially i am analyzing the function one variable at a time, treating all the other variables as wild cards.
Needless to say i am interested in real values of input variables only.
I have thought of using some variation of Strum theorem and that approach has a couple of problems. Suppose i have a ten-variable polynomial P(x1,x2,..,x10) and i know that domain of every variable is [0,100] And i want to know if it is increasing monotonically in x0 for any choice of the other variables in the domain. So i differentiate the polynomial with respect to x0 and try to count the number of roots of the derivative.
So i compute the Strum sequence: F1,F2,F3,..,Fn. At this point all Fs must be either all (positive or 0) or all (negative or 0) for all values of the remaining nine variables in the domain. And then i presumably could use Strum's again somehow.
- First of all this approach will not recognize x^3 as a monotonically increasing function because of its inflection point.
- Secondly, this approach is slow for high-degree polynomials with many variables. Execution of an algorithm based on Strum comes down to building a tree where number of levels is equal to the number of variables and the branching factor at every node is the length of the strum sequence which depends on the degree of the polynomial. So the total number of leafs of the tree would be enormous.
- Lastly, if we come back to the problem of rational functions, just counting the number of roots of numerator is not very useful because numerator and denominator of the expression night have same root.