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.
Download file
Counter downloads: 85
- Title Computation of a determinant and a matrix product in cellular automata
- Headline Computation of a determinant and a matrix product in cellular automata
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 46
- Date:
- DOI 10.17223/20710410/46/8
Keywords
клеточный автомат, определитель, детерминант, умножение матриц, параллельные вычисления, cel lular automaton, determinant, matrix multiplication, paral lel computingAuthors
References
Legendi T. et al. Megacell machine // Parallel Computing. 1988. V. 8. No. 1-3. P. 195-199
Kramer P. P. G. and van Leeuwen J. Systolic computation and VLSI // Foundations of Computer Science IV. P. 1. / eds. J. W. de Bakker and J. van Leeuven. Amsterdam, 1983. P. 75-103
Матюшкин И. В., Заплетина М. А. Отражение и транспонирование данных в матрице клеточно-автоматного вычислителя // Изв. вузов. Электроника. 2019. Т. 24. №1. С. 51-63
Матюшкин И. В., Жемерикин А. В., Заплетина М. А. Клеточно-автоматные алгоритмы сортировки строк и умножения целых чисел по схеме Атрубина // Изв. вузов. Электроника. 2016. Т. 21. №6. С. 557-565
Матюшкин И. В., Кожевников В. С. Клеточно-автоматные алгоритмы пермутации матриц // Труды МФТИ. 2019. Т. 11. № 1. С. 39-52
Гергель В. П. Теория и практика параллельных вычислений: учеб. пособие. М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2007. 423 с
Кудрявцев В. Б., Подколзин А. С., Болотов А. А. Основы теории однородных структур. М.: Наука, 1990. 296 с
Strassen V. Gaussian elimination is not optimal // Numer. Math. 1969. V. 13. No. 4. P. 354-356
Cohn H., Kleinberg R., Szegedy B., and Umans C. Group-theoretic algorithms for matrix multiplication // Proc. Ann. IEEE Symp. FOCS. 2005. P. 379-388
Фельдман Л. П., Назарова И. А., Хорошилов А. В. Параллельные блочные алгоритмы умножения матриц для мультикомпьютеров с распределенной памятью // Наукові праці Донецького національного технічного університету. Серія «Інформатика, кібернетика та обчислювальна техніка». 2007. Вып. 8(120). С. 297-308
Katona E. Cellular algorithms for binary matrix operations // LNCS. 1981. V. 111. P. 203-216
Stojanovic N. M., Milovanovic I. Z., Stojcev M. K., and Milovanovic E. I. Matrix-vector multiplication on a fixed size unidirectional systolic array // 8th Intern. Conf. on Telecommunications іп Modern Satellite, Cable and Broadcasting Services, Nis, Serbia. 2007. P. 457-460.
Gentleman W. M. Some complex!ty results for matr!x computations on parallel processors // J. ACM. 1978. V. 25. No. 1. P. 112-115
Dekel E., Nassimi D., and Sahni S. Parallel matr!x and graph algorithms // SIAM J. Comput!ng. 1981. V. 10. No. 4. P. 657-675
Moraga C. On a case of symbiosis between systolic arrays // Integratjon. 1984. V. 2. No. 3. P. 243-253
Umeo H. Firing squad synchronization algorithms for two-dimensional cellular automata // J. Cellular Automata. 2009. V. 4. No. 1. P. 1-20
Mazoyer J. A six-state minimal time solutjon to the firing squad synchronization problem // Theor. Comput. Sci. 1987. V. 50. No. 2. P. 183-238.
Беклемишев Д. В. Курс аналитической геометрии и линейной алгебры: учебник для вузов. 10-е изд., испр. М.: Физматлит, 2005. 304с
Аршон С. Обобщенное правило Саррюса // Матем. сб. 1935. Т. 42. № 1. С. 121-128
Mahajan M. and Vinay V. Determjnant: Combinatorics, Algorithms, and Complexity. Chicago J. Theor. Comput. Sd., 1997
Csanky L. Fast parallel inversion algorithms // SIAM J. Computing. 1976. V. 5. No. 4. P. 818-823
Berkowitz S. J. On computing the determinant in small parallel time using a small number of processors // Inform. Processing Lett. 1984. V. 18. No. 3. P. 147-150
Beliakov G. and Matiyasevich Y. A parallel algorithm for calculation of determinants and minors using arbitrary precision arithmetic // BIT Numerical Math. 2015. V. 56. No. 1. P. 33-50
Marco A. and Martinez J.-J. Parallel computation of determinants of matrices with polynomial entries // J. Symbolic Computation. 2004. V. 37. No. 6. P. 749-760
Almalki S., Alzahrani S., and Alabdullatif A. New parallel algorithms for finding determinants of N × N matrices // Proc. World Congress on Computer and Information Technology (WCCIT), 2013. P. 1-6
www.mathworks.com/help/matlab/ref/det.html -The MathWorks, Inc., 2019
Computation of a determinant and a matrix product in cellular automata | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 46. DOI: 10.17223/20710410/46/8
Download full-text version
Counter downloads: 434