1. On the Computation of 2-Dimensional Recurrence Equations
- Author
-
Natale, Giuseppe
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Computational Complexity ,Computer Science - Distributed, Parallel, and Cluster Computing ,G.1.0 ,F.1.2 ,F.2.1 - Abstract
The paper demonstrates how a 2-dimensional recurrence problem can be reduced to a mono-dimensional recurrence problem where the Kogge and Stone algorithm is applicable, with the computation time - excluding the reduction step - becoming proportional to $log_2(2n-1)$., Comment: The reduction step and increase in space complexity might make the application of this method impractical, unless alternative architectures - such as dataflow computing architectures - or parallel data manipulation mechanisms are employed
- Published
- 2024