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

Обложка

Цитировать

Полный текст

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

Аннотация

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