Computation of a determinant and a matrix product in~cellular automata

V. S. Kozhevnikov ; I. V. Matyushkin

Prikladnaâ diskretnaâ matematika, no. 4 (2019), pp. 88-107

Résumé

In the paper, possible implementations in cellular automata of matrix–vector multiplication, matrix multiplication, and determinant computation are described. The algorithms are formalised in terms of a cellular automaton model using a two-dimensional field with closed boundaries and von Neumann neighbourhood. The proposed algorithms are notable for isolated calculations (meaning that no data is entered during the computation process), which is a feature of a classical cellular automaton as opposed to a systolic array. Matrix multiplication is implemented for two square matrices as well as specifically for a matrix and a column vector, the latter implementation using less control flag states and therefore less additional memory. The matrix multiplication algorithm adapts Katona's scheme for matrix multiplication in a systolic array to an isolated cellular automaton. For calculation of a determinant, two algorithms based on Gaussian elimination are proposed. One has linear complexity and uses a control flag with only 5 states, being, however, inapplicable to an arbitrary matrix. The other one is modified to seek the largest leading element during row reduction, which makes its complexity quadratic and its control flags assume 11 states but allows the algorithm to be applied to an arbitrary matrix and be more numerically stable.

Détail

Keywords: cellular automaton, determinant, parallel computing.
Mots-clés : matrix multiplication