Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

Edit:

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.
share|improve this question
2  
If you are analyzing these rational functions one variable at a time, why not just apply the appropriate univariate methods. I believe that the two sample questions that you gave come down to counting the number of real roots of the derivative $\partial_{x_0} f$. After clearing denominators, this comes down to counting the real roots of some polynomial in $x_0$, whose coefficients depend on the other variables. I think something like the Sturm sequence method should do the trick: en.wikipedia.org/wiki/Sturm_sequence –  Igor Khavkine Jan 18 '13 at 5:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.