Образец для цитирования:

Кузнецов Ю. В. Об одной комбинаторной проблеме, связанной с быстрым умножением матриц // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2013. Т. 13, вып. 4. С. 63-67. DOI: https://doi.org/10.18500/1816-9791-2013-13-4-63-67

Язык публикации: 
русский
Рубрика: 
Математика
УДК: 
519.7

Об одной комбинаторной проблеме, связанной с быстрым умножением матриц

Авторы: 
Кузнецов Юрий Владимирович, Научно-исследовательский институт системных исследований РАН, Россия, 117218, г. Москва, Нахимовский пр-т, 36, к. 1 , ykuz@niisi.ras.ru
Аннотация: 
В рамках теоретико-группового подхода Х. Кона, К. Уманса, Р. Клейнберга, Б. Сегеди к проблеме быстрого умножения матриц возникают специфические комбинаторные объекты, получившие название «однозначно разрешимые матрицы» («uniquely solvable puzzle») или USP-матрицы. В работе обсуждается некоторая числовая характеристика USP-матриц и исследуется связь между USP-матрицами и известной комбинаторной проблемой, в англоязычной литературе носящей название «Cap set problem».
Ключевые слова: 
быстрое умножение матриц, теоретико-групповой подход, экспонента матричного умножения !, USP-матрицы, Cap set problem.
DOI: 
https://doi.org/10.18500/1816-9791-2013-13-4-63-67
Библиографический список
1. Coppersmith D., Winograd S. Matrix multiplication via arithmetic progressions // J. Symbolic Comput. 1990. Vol. 9, № 3. P. 251–280.
2. 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).
3. 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.
4. 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.
5. Платонов В. П., Кузнецов Ю. В., Петрунин М. М. О теоретико-групповом подходе к проблеме быстрого умножения матриц. Математическое и компьютерное моделирование систем : теоретические и прикладные аспекты // Сб. науч. тр. НИИСИ РАН. М., 2009. C. 4–15.
6. Кузнецов Ю. В. Некоторые комбинаторные аспекты теоретико-группового подхода к проблеме быстрого умножения матриц // Чебышевский сб. 2012. Т. 13,№ 1. С. 102–109.
7. Alon N., Shpilka A., Umans C. On sunflowers and matrix multiplication // Electronic Colloquium on Computational Complexity. 2011. Report № 67. P. 1–16.
8. Davis B. L., Maclagan D. The card game SET // Mathematical Intelligencer. 2003. Vol. 25, № 3. P. 33–40.
9. Bateman M., Katz N. New bounds on caps sets // J. American Math. Soc. 2012. Vol. 25, № 2. P. 585–613.
10. Edel Y. Extensions of generalized product caps // Designs, Codes and Cryptography. 2004. Vol. 31. P. 5–14.
11. Mebane P. Uniquely Solvable Puzzles and Fast Matrix Multiplication. HMC Senior Theses, 2012. 37 p.
Краткое содержание (на английском языке): 
page_09.pdf
38
Полный текст в формате PDF:
скачать
58