The parallel complexity of function approximation (Q1179031)

The author defines a parallel algorithm \(\phi\) with \(n\) input variables \(x_ 1,\dots,x_ n\) as a finite directed graph \((G,M)\) having the following properties (\(G\) being the set of nodes, \(M\) the set of edges, \(M\subset G\times G)\): 1. \(G\subseteq\{N\cup\{0\}\}\times N\) and \((0,1),\dots,(0,n)\in G\) (\(N\) is the set of natural numbers). 2. Every node \((j,k)\in G\) with \(j>0\) has exactly 2 incoming edges: \(((j_ l,k_ l),(j,k))\), \(((j_ r,k_ r),(j,k))\in M\), where \(jl,j_ r<j\). 3. To every node \((j,k)\), \(j>0\), belongs an operation \(op(j,k)\in\{+,-,\ast\}\). To each node \((j,k)\) of an algorithm \(\phi\) is associated recursively a function \(\psi_{(j,k)}\) of the input variables as follows: \(\psi_{(0,k)}(x_ 1,\dots,x_ n)=x_ k\) if \(1\leq k\leq n\), \(\psi_{(0,k)}(x_ 1,\dots,x_ n)=a_ k\) if \(k\geq n\), \(\psi_{(j,k)}(x_ 1,\dots,x_ n)=\psi_{(j_ l,k_ l)}(x_ 1,\dots,x_ n) op(j,k)\psi_{(j_ r,k_ r)}(x_ 1,\dots,x_ n)\) if \(j>1\). The real numbers \(a_ k\) are the input constants. The interpretation of this is that at time step \(j>0\) the processor number \(k\) performs the operation \(op(j,k)\) at the operands \(\psi_{(j_ l,k_ l)}(x_ 1,\dots,x_ n)\), \(\psi_{(j_ r,k_ r)}(x_ 1,\dots,x_ n)\). The complexity of a prallel algorithm is given by \(\hbox{comp} \phi=\max\{j\in N\mid\;\exists k\in N:\;(j,k)\in G\}\) and the parallelism of \(\phi\) is defined by \(p(\phi)=\max\{\hbox{card}\{(j,k)\in G\mid\;j=l\}\mid\;l\in N\}\). If \(f: R^ n\to R^ 1\), it is said that the parallel algorithm \(\phi\) computes the function \(f\), if there exists a \((j_ 0,k_ 0)\in G\) such that \(\psi_{(j_ \sigma,k_ \sigma)}(x)=f(x)\) for all \(x=(x_ 1,\dots,x_ n)\in R^ n\). For every number \(p\) of processors, \(1\leq p\leq\infty\), the parallel complexity of a function \(f\) is given by \(p-\hbox{comp} f=\min\{\hbox{comp} \phi\mid\;\phi\hbox{ computes }f,\;p(\phi)\leq p\}\). If \(\Lambda\) is a class of functions, then define \(p-\hbox{comp}(\Lambda)=\max\{p-\hbox{comp} q\mid\;q\in\Lambda\}\). If \(\Lambda\) is a class of functions \(f: M\to R^ 1\), \(M\subset R^ n\), then for \(f\in\Lambda\) define \(p-\hbox{comp}(f;\varepsilon)=\min\{p-\hbox{comp} \phi\mid\;\phi\hbox{ computes a } \psi\hbox{ with } |\psi(x)-f(x)|\leq\varepsilon\}\) for all \(x\in M\) and \(p-\hbox{comp}(\Lambda;\varepsilon)= \max\{p- \hbox{comp}(f;\varepsilon)\mid\;f\in\Lambda\}\). The author obtains lower and upper bounds for \(p-\hbox{comp}(P^ r)\), \(p-\hbox{comp}(P_ r)\), \(1\leq p\leq\infty\), where \(P^ r\) resp. \(P_ r\) is the set of polynomials in \(R^ n\) of the degree at most \(r\) resp. of the degree at most \(r\) in regard to separate variables. He also obtains bounds for \(p-\hbox{comp}(\Lambda:\varepsilon)\) for some classes \(\Lambda\) of continuous functions.