ГлавнаяАрхивВычисление детерминанта и произведе ния матриц в структуре клеточного автомата

Вычисление детерминанта и произведе ния матриц в структуре клеточного автомата | Прикладная дискретная математика. 2019. № 46. DOI: 10.17223/20710410/46/8

Приведено формальное описание двумерных клеточных автоматов, реализующих умножение матриц и нахождение определителя. Все алгоритмы даны для границ с замыканием, шаблона окрестности Неймана и закрытых вычислений (т. е. данные не вводятся в процессе расчёта). Отдельно реализовано умножение матрицы на вектор-столбец. Для вычисления определителя предложены два алгоритма, основанные на методе Гаусса. Один имеет линейную сложность и использует управляющий флаг с пятью состояниями, однако применим не ко всякой матрице. Другой работает для любой матрицы, но имеет квадратичную сложность и его управляющий флаг принимает одиннадцать состояний.
  • Title Вычисление детерминанта и произведе ния матриц в структуре клеточного автомата
  • Headline Вычисление детерминанта и произведе ния матриц в структуре клеточного автомата
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 46
  • Date:
  • DOI 10.17223/20710410/46/8
Ключевые слова
клеточный автомат, определитель, детерминант, умножение матриц, параллельные вычисления, cel lular automaton, determinant, matrix multiplication, paral lel computing
Авторы
Ссылки
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
Вычисление детерминанта и произведе ния матриц в структуре клеточного автомата | Прикладная дискретная математика. 2019. № 46. DOI: 10.17223/20710410/46/8
Вычисление детерминанта и произведе ния матриц в структуре клеточного автомата | Прикладная дискретная математика. 2019. № 46. DOI: 10.17223/20710410/46/8