# How to find composition of two piecewise-linear functions quickly?

Given two piecewise-linear scalar functions $f(x) = a_ix+b_i$ on $[x_i, x_{i+1}], i = 1, \ldots,m$ and $g(x) = \alpha_jx+\beta_j$ on $[y_j, y_{j+1}], j = 1, \ldots,n$. How can we determine the composition $f\circ g$ quickly on the interval $[a, b]$ where $a =\min\{x_1,y_1\}, b = \max\{x_{m+1},y_{n+1}\}$.

What I would do is to write $f\circ g = f(\alpha_jx+\beta_j)$ on$[y_j, y_{j+1}]$ then find $f(\alpha_jx+\beta_j)$. However, I think there is quick way to give the general formula for $f\circ g$ in term of $x_i$ and $y_j$. Thank you in advance!

The function $f\circ g$ is piecewise linear as a composition of piecewise linear functions. Unfortunately, my experience suggests that descriptions of compostions of piesewise linear fuctions are complicated. In order to determine $f\circ g$ it suffices to determine numbers $z_1\le \dots\le z_p$ such that $f\circ g (x)=c_k x+d_k$ (I decided to use banal Latin letters instead logical Russian of Hebrew these :-) ) on $[z_k, z_{k+1}]$. I remark that, in general $p=O(mn)$, for instance, when $|Y\cap\bigcap_{i=1}^{m-1} f([x_i,x_{i+1}])|=O(n)$, where $Y=\{y_1,\dots, y_n\}$. Next, we can describe the sequence $\{z_k\}$ as an extension of the sequence $\{x_i\}$, that is there exist numbers $p(1),\dots, p(m-1)$ such that
$$x_1=z_{1,1}\le z_{1,2}\le\dots\le z_{1,p(1)}=x_2=z_{2,1}\le \dots\le z_{2,p(2)}=x_3\le\dots\le z_{m-1,p(m-1)}=x_m,$$
where for each $i$ $(z_{i,2}\le \dots \le z_{i,p(i)-1})$ is an enumeration ot the points $x\in [x_{i},x_{i+1}]$ such that $f(a_ix+b)=y_j$ for some $j$ taken in the increasing order when $a_i>0$ and in the decreasing order when $a_i<0$ (we have to assume that $f([x_i, x_{i+1}])\subset [y_1, y_{n}]$, because otherwise the composition $f\circ g$ can be undefined on $[x_i, x_{i+1}]$). For instance, if $a_i>0$ and $$f([x_i,x_{i+1}])\cap Y=\{y_{j(i)}, y_{j(i)+1},\dots, y_{j’(i)}\}$$ for some numbers $j(i)$ and $j’(i)$ then for each $2\le k\le p(i)-1$ we have $a_iz_{i,k}+ b_i=f(z_{i,k})=y_{j(i)+k-2}$, that is $z_{i,k}=(y_{j(i)+k-2}-b_i)/a_i$. In remains to note that for $x\in [z_{i,k},z_{i+1,k}]$ we have $c_{i,k}x+d_{i,k}\equiv \alpha_{j(i)+k-2}(a_ix+b_i)+\beta_{j(i)+k-2}$ for each $1\le k\le p(i)-1$.