Systolic convolution of arithmetic functions (Q1184979): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4721605 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3941473 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4190126 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Systolic convolution of arithmetic functions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3686062 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A systematic design of a parallel program for Dirichlet convolution / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the design of some systolic algorithms / rank | |||
Normal rank | |||
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 | |||
links / mardi / name | links / mardi / name | ||
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