|
Чебышевский сборник, 2011, том 12, выпуск 2, страницы 60–67
(Mi cheb77)
|
|
|
|
Быстрый алгоритм проверки вырожденности ганкелевых матриц
Ю. В. Кузнецов, М. М. Петрунин НИИСИ РАН
Аннотация:
Из результатов работ 2009–2010 годов Платонова В. П. (совместно с Беняш-Кривецем В. В.) следует, что в случае эллиптических полей эффективность алгоритмов вычисления нетривиальных единиц напрямую определяется эффективностью алгоритмов проверки вырожденности соответствующих ганкелевых матриц. В этой связи был разработан асимптотически наилучший рекурсивный алгоритм проверки вырожденности ганкелевых матриц сложности $O(n \log^2 n)$, который не накладывает ограничений на невырожденность ведущих подматриц и для этого алгоритма вычислена мультипликативная константа 468.
Поступила в редакцию: 17.10.2011
Образец цитирования:
Ю. В. Кузнецов, М. М. Петрунин, “Быстрый алгоритм проверки вырожденности ганкелевых матриц”, Чебышевский сб., 12:2 (2011), 60–67
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/cheb77 https://www.mathnet.ru/rus/cheb/v12/i2/p60
|
|