Для цитирования:
Кузнецов Ю. В. Об одной комбинаторной проблеме, связанной с быстрым умножением матриц // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2013. Т. 13, вып. 4, ч. 2. С. 63-67. DOI: 10.18500/1816-9791-2013-13-4-63-67
Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн:
25.11.2013
Полный текст:
(downloads: 183)
Язык публикации:
русский
Рубрика:
УДК:
519.7
Об одной комбинаторной проблеме, связанной с быстрым умножением матриц
Авторы:
Кузнецов Юрий Владимирович, Научно-исследовательский институт системных исследований РАН
Аннотация:
В рамках теоретико-группового подхода Х. Кона, К. Уманса, Р. Клейнберга, Б. Сегеди к проблеме быстрого умножения матриц возникают специфические комбинаторные объекты, получившие название «однозначно разрешимые матрицы» («uniquely solvable puzzle») или USP-матрицы. В работе обсуждается некоторая числовая характеристика USP-матриц и исследуется связь между USP-матрицами и известной комбинаторной проблемой, в англоязычной литературе носящей название «Cap set problem».
Ключевые слова:
Список источников:
- Coppersmith D., Winograd S. Matrix multiplication via arithmetic progressions // J. Symbolic Comput. 1990. Vol. 9, № 3. P. 251–280.
- Vassilevska Williams V. Multiplying Matrices Faster than Coppersmith–Winograd // Proceedings of the 44-th Symposium on Theory of Computing, STOC’12. 2012. URL: www.cs.berkeley.edu/ virgi/matrixmult.pdf (дата обращения 30.09.2013).
- Cohn H., Umans C. A group theoretic approach to fast matrix multiplication // Proceedings of the 44-th Annual IEEE Symposium on Foundations of Computer Science. 2003. P. 438–449. DOI: 10.1109/SFCS.2003.1238217.
- Cohn H., Kleinberg R., Szegedy B., Umans C. Group-theoretic algorithms for matrix multiplication // Proceedings of the 46-th Annual IEEE Symposium on Foundations of Computer Science. 2005. P. 379–388. DOI: 10.1109/SFCS.2005.39.
- Платонов В. П., Кузнецов Ю. В., Петрунин М. М. О теоретико-групповом подходе к проблеме быстрого умножения матриц. Математическое и компьютерное моделирование систем : теоретические и прикладные аспекты // Сб. науч. тр. НИИСИ РАН. М., 2009. C. 4–15.
- Кузнецов Ю. В. Некоторые комбинаторные аспекты теоретико-группового подхода к проблеме быстрого умножения матриц // Чебышевский сб. 2012. Т. 13,№ 1. С. 102–109.
- Alon N., Shpilka A., Umans C. On sunflowers and matrix multiplication // Electronic Colloquium on Computational Complexity. 2011. Report № 67. P. 1–16.
- Davis B. L., Maclagan D. The card game SET // Mathematical Intelligencer. 2003. Vol. 25, № 3. P. 33–40.
- Bateman M., Katz N. New bounds on caps sets // J. American Math. Soc. 2012. Vol. 25, № 2. P. 585–613.
- Edel Y. Extensions of generalized product caps // Designs, Codes and Cryptography. 2004. Vol. 31. P. 5–14.
- Mebane P. Uniquely Solvable Puzzles and Fast Matrix Multiplication. HMC Senior Theses, 2012. 37 p.
Краткое содержание:
(downloads: 75)
- 921 просмотр