1. На главную
  2. Электронные версии
  3. Программирование
  4. № 5, 2023

Программирование, 2023, № 5, стр. 79-86

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

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

a Институт проблем передачи информации им. А.А. Харкевича Российской академии наук
127051 Москва, Большой Каретный пер., д. 19, Россия

* E-mail: zverkov@iitp.ru
** E-mail: slvstv@iitp.ru

Поступила в редакцию 26.06.2022
После доработки 27.07.2022
Принята к публикации 30.10.2022

Аннотация

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

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

  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. $(0,1)$-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

Дополнительные материалы отсутствуют.

Инструменты

предыдущая статья выпуска содержание выпуска

Программирование

Архивы выпусков Информация о журнале Отправить рукопись в журнал