Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

Для цитирования:

Кузнецов Ю. В. Об одной комбинаторной проблеме, связанной с быстрым умножением матриц // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2013. Т. 13, вып. 4. С. 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: 134)
Язык публикации: 
русский
Рубрика: 
Математика
УДК: 
519.7
DOI: 
10.18500/1816-9791-2013-13-4-63-67

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

Авторы: 
Кузнецов Юрий Владимирович, Научно-исследовательский институт системных исследований РАН
Аннотация: 

В рамках теоретико-группового подхода Х. Кона, К. Уманса, Р. Клейнберга, Б. Сегеди к проблеме быстрого умножения матриц возникают специфические комбинаторные объекты, получившие название «однозначно разрешимые матрицы» («uniquely solvable puzzle») или USP-матрицы. В работе обсуждается некоторая числовая характеристика USP-матриц и исследуется связь между USP-матрицами и известной комбинаторной проблемой, в англоязычной литературе носящей название «Cap set problem».

Ключевые слова: 
быстрое умножение матриц
теоретико-групповой подход
экспонента матричного умножения ω
USP-матрицы
Cap set problem
Список источников: 
  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.
Краткое содержание:
скачать
(downloads: 45)
  • 754 просмотра