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

Bibliographie

[1] Legendi T. et al., “Megacell machine”, Parallel Computing, 8:1–3 (1988), 195–199 | DOI | MR | Zbl

[2] Kramer P. P. G., van Leeuwen J., “Systolic computation and VLSI”, Foundations of Computer Science IV, v. 1, eds. J. W. de Bakker, J. van Leeuven, Amsterdam, 1983, 75–103 | MR | Zbl

[3] Matushkin I. V., Zapletina M. A., “Data reflection and transposition in the matrix of a cellular automata computator”, Proc. Universities. Electronics, 24:1 (2019), 51–63 (in Russian)

[4] Matushkin I. V., Zhemerikin A. V., Zapletina M. A., “Cellular Automata Algorithms for String Sorting and Integer Multiplication by Atrubin's Scheme”, Proc. Universities. Electronics, 21:6 (2016), 557–565 (in Russian)

[5] Matyushkin I. V., Kozhevnikov V. S., “Cellular automata algorithms for matrix permutations”, Proc. MIPT, 11:1 (2019), 39–52 (in Russian) | MR

[6] Gergel V. P., Theory and Practice of Parallel Computing, Internet-Universitet Informatsionnykh Tekhnologiy; BINOM Publ., M., 2007, 423 pp. (in Russian)

[7] Kudryavtsev V. B., Podkolzin A. S., Bolotov A. A., Basics of the Theory of Homogeneous Structures, Nauka Publ., M., 1990, 296 pp. (in Russian) | MR

[8] Strassen V., “Gaussian elimination is not optimal”, Numer. Math., 13:4 (1969), 354–356 | DOI | MR | Zbl

[9] Cohn H., Kleinberg R., Szegedy B., Umans C., “Group-theoretic algorithms for matrix multiplication”, Proc. Ann. IEEE Symp. FOCS, 2005, 379–388

[10] Feldman L. P., Nazarova I. A., Horoshilov A. V., “Parallel block algorithms of matrix multiplication for computer systems with distributed memories”, Naukovi pratsi Donets'kogo natsional'nogo tekhnichnogo universitetu, seriya “Informatika, kibernetika ta obchislyuval'na tekhnika”, 2007, no. 8(120), 297–308 (in Russian)

[11] Katona E., “Cellular algorithms for binary matrix operations”, LNCS, 111, 1981, 203–216

[12] Stojanovic N. M., Milovanovic I. Z., Stojcev M. K., Milovanovic E. I., “Matrix-vector multiplication on a fixed size unidirectional systolic array”, 8th Intern. Conf. on Telecommunications in Modern Satellite, Cable and Broadcasting Services (Nis, Serbia, 2007), 457–460

[13] Gentleman W. M., “Some complexity results for matrix computations on parallel processors”, J. ACM, 25:1 (1978), 112–115 | DOI | MR | Zbl

[14] Dekel E., Nassimi D., Sahni S., “Parallel matrix and graph algorithms”, SIAM J. Computing, 10:4 (1981), 657–675 | DOI | MR | Zbl

[15] Moraga C., “On a case of symbiosis between systolic arrays”, Integration, 2:3 (1984), 243–253 | DOI

[16] Umeo H., “Firing squad synchronization algorithms for two-dimensional cellular automata”, J. Cellular Automata, 4:1 (2009), 1–20 | MR | Zbl

[17] Mazoyer J., “A six-state minimal time solution to the firing squad synchronization problem”, Theor. Comput. Sci., 50:2 (1987), 183–238 | DOI | MR | Zbl

[18] Beklemishev D. V., A course of analytic geometry and linear algebra, Fizmatlit Publ., M., 2005, 304 pp. (in Russian)

[19] Arshon S., “Generalized Sarrus' rule”, Matematicheskiy Sbornik, 42:1 (1935), 121–128 (in Russian)

[20] Mahajan M., Vinay V., “Determinant: Combinatorics, Algorithms, and Complexity”, Chicago J. Theor. Comput. Sci., 1997 | MR

[21] Csanky L., “Fast parallel inversion algorithms”, SIAM J. Computing, 5:4 (1976), 818–823 | DOI | MR

[22] Berkowitz S. J., “On computing the determinant in small parallel time using a small number of processors”, Inform. Processing Lett., 18:3 (1984), 147–150 | DOI | MR | Zbl

[23] Beliakov G., Matiyasevich Y., “A parallel algorithm for calculation of determinants and minors using arbitrary precision arithmetic”, BIT Numerical Math., 56:1 (2015), 33–50 | DOI | MR

[24] Marco A., Martínez J.-J., “Parallel computation of determinants of matrices with polynomial entries”, J. Symbolic Computation, 37:6 (2004), 749–760 | DOI | MR | Zbl

[25] Almalki S., Alzahrani S., Alabdullatif A., “New parallel algorithms for finding determinants of $N\times N$ matrices”, Proc. World Congress on Computer and Information Technology (WCCIT), 2013, 1–6

[26] , The MathWorks, Inc., 2019 http://www.mathworks.com/help/matlab/ref/det.html