Nonlinear subdivision through nonlinear averaging

We investigate a general class of nonlinear subdivision algorithms for functions of a real or complex variable built from linear subdivision algorithms by replacing binary linear averages such as the arithmetic mean by binary nonlinear averages such as the geometric mean. Using our method, we can easily create stationary subdivision schemes for Gaussian functions, spiral curves, and circles with uniform parametrizations. More generally, we show that stationary subdivision schemes for ep(x), cos(p(x)) and sin(p(x)) for any polynomial or piecewise polynomial p(x) can be generated using only addition, subtraction, multiplication, and square roots. The smoothness of our nonlinear subdivision schemes is inherited from the smoothness of the original linear subdivision schemes and the differentiability of the corresponding nonlinear averaging rules. While our results are quite general, our proofs are elementary, based mainly on the observation that generic nonlinear averaging rules on a pair of real or complex numbers can be constructed by conjugating linear averaging rules with locally invertible nonlinear maps. In a forthcoming paper we show that every continuous nonlinear averaging rule on a pair of real or complex numbers can be constructed by conjugating a linear averaging rule with an associated continuous locally invertible nonlinear map. Thus the averaging rules considered in this paper are actually the general case. As an application we show how to apply our nonlinear subdivision algorithms to intersect some common transcendental functions.