Systolic convolution of arithmetic functions (Q1184979)

Given two arithmetic functions \(f\) and \(g\), their convolution \(h=f^*g\) is defined to be \[ h(n)=\sum_{{k\ell=n} \atop {1\leq k,\ell\leq n}}f(k)g(\ell) \] for all \(n\geq 1\). Given two arithmetic functions \(g\) and \(h\), the inverse convolution problem is to determine \(f\) such that \(f^*g=h\). The authors propose a linear systolic architecture of \(O(N)\) cells which uses the dependence mapping method to solve the problem of computing the convolution (\(h(n)\), \(1\leq n\leq N\)) in time \(O(N)\). The space-time complexity of the proposed architecture is \(O(N^ 2\log N)\). They then describe another systolic architecture of only \(O(N^{1/2})\) processing cells which also solves the problem in time \(O(N)\); this second architecture requires only \(O(N\log N)\) delay cells, leading to the same space-time complexity as that of the first solution. Both of these architectures can be extended, with the same performances, to the inverse convolution problem.