Systolic convolution of arithmetic functions (Q1184979): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(92)90265-h / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2064112698 / rank | |||
Normal rank |
Latest revision as of 10:11, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Systolic convolution of arithmetic functions |
scientific article |
Statements
Systolic convolution of arithmetic functions (English)
0 references
28 June 1992
0 references
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.
0 references
systolic arrays
0 references
convolution
0 references