A Lower Bound for the Parallel Complexity of Periodicity on Multi Dimensional Arrays

Abstract

Given that an array $A[i_1,\dots ,i_d]$, $1\le i_1\le m,\dots 1\le i_d\le m$, has a \emph{period} $A[p_1,\dots ,p_d]$ of dimension $p_1\times \cdots p_d$ if $A[i_1,\dots ,i_d]=A[i_1+p_1,\dots ,i_d+p_d]$
for $i_1,\dots ,i_d=1,\dots ,m–(p_1,\dots ,p_d)$. The \emph{period} of the array is $A[p_1,\dots ,p_d]$ for the shortest such $q=p_1,\dots ,p_d$.

Consider this array $A$; we prove a lower bound on the computation of the period length less than $m^d/2^d$ of $A$ with time complexity
$$\mathrm{\Omega }(\log {\log }_{a}m),\text{ where }a=m^{d^2}$$
for $O(m^d)$ work on the CRCW PRAM model of computation.