OPTIMAL PARALLEL SUPERPRIMITIVITY TESTING FOR SQUARE ARRAYS
Costas S. Iliopoulos, Maureen Korda · Parallel Processing Letters · 1996
We present an optimal O( log log n) time algorithm on the CRCW PRAM which tests whether a square array, A, of size n×n, is superprimitive. If A is not superprimitive, the algorithm returns the quasiperiod, i.e., the smallest square array that covers A.