ЭФФЕКТИВНЫЕ НИЖНИЕ ГРАНИЦЫ ДЛЯ РАНГА МАТРИЦЫ И ПРИЛОЖЕНИЯ

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Предложена эффективно проверяемая нижняя граница для ранга разреженной вполне неразложимой квадратной матрицы, содержащей по два ненулевых элемента в каждой строке и каждом столбце. Ранг такой матрицы равен порядку или отличается на единицу. Построены базисы специального вида в пространствах квадратичных форм от фиксированного числа переменных. Существование таких базисов позволило нам обосновать эвристический алгоритм для решения задачи распознавания, проходит ли данное аффинное подпространство через вершину многомерного единичного куба. В худшем случае этот алгоритм может вернуть уведомление о неопределенности результата вычисления, но для общего подпространства достаточно малой размерности корректно отвергает вход. Алгоритм реализован на языке Python. В ходе тестирования получены оценки времени работы этой реализации алгоритма.

Об авторах

О. А. Зверков

Институт проблем передачи информации им. А.А. Харкевича Российской академии наук

Автор, ответственный за переписку.
Email: zverkov@iitp.ru
Россия, 127051, Москва, Большой Каретный пер., д. 19

А. В. Селиверстов

Институт проблем передачи информации им. А.А. Харкевича Российской академии наук

Автор, ответственный за переписку.
Email: slvstv@iitp.ru
Россия, 127051, Москва, Большой Каретный пер., д. 19

Список литературы

  1. Геворкян М.Н., Королькова А.В., Кулябов Д.С., Севастьянов Л.А. Пример модульного расширения системы компьютерной алгебры // Программирование. 2020. № 2. С. 30–37. DOI: Перевод: Programming and Computer Software. 2020. V. 46. № 2. P. 98–104.https://doi.org/10.31857/S0132347420020065
  2. Chistov A.L. Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic // In: L. Budach (eds) Fundamentals of Computation Theory. FCT 1985. Lecture Notes in Computer Science, vol. 199. Springer, Berlin, Heidelberg, 1985. P. 63–69. https://doi.org/10.1007/BFb0028792
  3. Mulmuley K. A fast parallel algorithm to compute the rank of a matrix over an arbitrary field // Combinatorica. 1987. V. 7. № 1. P. 101–104. https://doi.org/10.1007/BF02579205
  4. Malaschonok G., Tchaikovsky I. About big matrix inversion // In: Abramov S.A., Sevastyanov L.A. (eds) Computer algebra. Moscow: MAKS Press, 2021. P. 81–84. https://doi.org/10.29003/m2019.978-5-317-06623-9
  5. Малашонок Г.И., Сидько А.А. Суперкомпьютерная среда выполнения для рекурсивных матричных алгоритмов // Программирование. 2022. № 2. С. 33–46. DOI: Перевод: Programming and Computer Software. 2022. V. 48. P. 90–101.https://doi.org/10.31857/S0132347422020091
  6. Cheung H.Y., Kwok T.C., Lau L.C. Fast matrix rank algorithms and applications // Journal of the ACM. 2013. V. 60. № 5. Article № 31. P. 1–25. https://doi.org/10.1145/2528404
  7. Abdeljaoued J., Malaschonok G.I. Efficient algorithms for computing the characteristic polynomial in a domain // Journal of Pure and Applied Algebra. 2001. V. 156. P. 127–145. https://doi.org/10.1016/S0022-4049(99)00158-9
  8. Переславцева О.Н. О вычислении характеристического полинома матрицы // Дискретная математика. 2011. Т. 23. № 1. С. 28–45. DOI: Перевод: Discrete Mathematics and Applications. 2011. V. 21. № 1. P. 109–128.https://doi.org/10.4213/dm1128
  9. Neiger V., Pernet C. Deterministic computation of the characteristic polynomial in the time of matrix multiplication // Journal of Complexity. 2021. V. 67. № 101572. P. 1–35. https://doi.org/10.1016/j.jco.2021.101572
  10. Chen Z. On nonsingularity of circulant matrices // Linear Algebra and its Applications. 2021. V. 612. P. 162–176. https://doi.org/10.1016/j.laa.2020.12.010
  11. Алаев П.Е., Селиванов В.Л. Поля алгебраических чисел, вычислимые за полиномиальное время. I // Алгебра и логика. 2019. Т. 58. № 6. С. 673–705. DOI: Перевод: Algebra Logiс. 2020. V. 58. P. 447–469.https://doi.org/10.33048/alglog.2019.58.601
  12. Алаев П.Е., Селиванов В.Л. Поля алгебраических чисел, вычислимые за полиномиальное время. II // Алгебра и логика. 2021. Т. 60. № 6. С. 533–548. DOI: Перевод: Algebra Logiс. 2022. V. 60. P. 349–359.https://doi.org/10.33048/alglog.2021.60.601
  13. Harris J., Tu L.W. On symmetric and skew-symmetric determinantal varieties // Topology. 1984. V. 23. № 1. P. 71–84. https://doi.org/10.1016/0040-9383(84)90026-0
  14. Harris J. Algebraic geometry. Springer-Verlag New York, 1992. 330 p. https://doi.org/10.1007/978-1-4757-2189-8
  15. Rubei E. Affine subspaces of matrices with constant rank // Linear Algebra and its Applications. 2022. V. 644. № 1. P. 259–269. https://doi.org/10.1016/j.laa.2022.03.002
  16. Селиверстов А.В. Двоичные решения для больших систем линейных уравнений // Прикладная дискретная математика. 2021. № 52. С. 5–15. https://doi.org/10.17223/20710410/52/1
  17. Кузюрин Н.Н. Полиномиальный в среднем алгоритм в целочисленном линейном программировании // Сибирский журнал исследования операций. 1994. Т. 1. № 3. С. 38–48.
  18. Kuzyurin N.N. An integer linear programming algorithm polynomial in the average case // In: Korshunov A.D. (eds.) Discrete Analysis and Operations Research. Mathematics and Its Applications. V. 355. P. 143–152. Springer, Dordrecht, 1996. https://doi.org/10.1007/978-94-009-1606-7
  19. Pan Y., Zhang F. Solving low-density multiple subset sum problems with SVP oracle // Journal of Systems Science and Complexity. 2016. V. 29. P. 228–242. https://doi.org/10.1007/s11424-015-3324-9
  20. Рыбалов А.Н. О генерической сложности проблемы о сумме подмножеств для полугрупп целочисленных матриц // Прикладная дискретная математика. 2020. № 50. С. 118–126. https://doi.org/10.17223/20710410/50/9
  21. Рыбалов А.Н. О генерической сложности проблемы вхождения для полугрупп целочисленных матриц // Прикладная дискретная математика. 2022. № 55. С. 95–101. https://doi.org/10.17223/20710410/55/7
  22. Селиверстов А.В. Эвристические алгоритмы распознавания некоторых кубических гиперповерхностей // Программирование. 2021. № 1. С. 65–72. DOI: Перевод: Programming and Computer Software. 2021. V. 47. № 1. P. 50–55.https://doi.org/10.31857/S0132347421010106
  23. Minc H. -matrices with minimal permanents // Israel Journal of Mathematics. 1973. V. 15. P. 27–30. https://doi.org/10.1007/BF0277177010.1007/BF02771770
  24. Seliverstov A.V., Lyubetsky V.A. About forms equal to zero at each vertex of a cube // Journal of Communications Technology and Electronics. 2012. V. 57. № 8. P. 892–895. https://doi.org/10.1134/S1064226912080049
  25. Schwartz J.T. Fast probabilistic algorithms for verification of polynomial identities // Journal of the ACM. 1980. V. 27. № 4. P. 701–717. https://doi.org/10.1145/322217.322225
  26. Harris C.R., Millman K.J., van der Walt S.J. et al. Array programming with NumPy // Nature. 2020. V. 585. № 7825. P. 357–362. https://doi.org/10.1038/s41586-020-2649-2
  27. Chen Y.A., Gao X.S. Quantum algorithm for Boolean equation solving and quantum algebraic attack on cryptosystems // Journal of Systems Science and Complexity. 2022. V. 35. P. 373–412. https://doi.org/10.1007/s11424-020-0028-6

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© О.А. Зверков, А.В. Селиверстов, 2023

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».