Разреженный полином
В математике разреженный полином (также лакунарный полином [ 1 ] или малономиальный ) [ 2 ] - это многочлен , который имеет гораздо меньше членов, чем можно было бы предположить по его степени и количеству переменных . Например, х 10 + 3x 3 − 1 поскольку это трехчлен степени — разреженный многочлен , 10.
Мотивация изучения разреженных многочленов состоит в том, чтобы сконцентрироваться на структуре мономов многочлена, а не на его степени, в чем можно убедиться, например, сравнивая теорему Бернштейна-Кушниренко с теоремой Безу . Исследования разреженных полиномов также включали работу над алгоритмами, время работы которых растет в зависимости от количества членов, а не от степени. [ 3 ] для задач, включая полиномиальное умножение [ 4 ] [ 5 ] , разделение , [ 6 ] алгоритмы поиска корней , [ 7 ] и полиномиальные наибольшие общие делители . [ 8 ] Разреженные многочлены также использовались в чистой математике, особенно при изучении групп Галуа , потому что было легче определить группы Галуа определенных семейств разреженных многочленов, чем для других многочленов. [ 9 ]
Алгебраические многообразия, определяемые разреженными полиномами, имеют простую структуру, которая отражается и на строении решений некоторых родственных дифференциальных уравнений . [ 2 ] Кроме того, для одномерных разреженных полиномов существует разреженный позитивный стеллензац . В нем говорится, что неотрицательность многочлена может быть подтверждена полиномами sos, степень которых зависит только от количества мономов многочлена. [ 10 ]
Разреженные полиномы часто встречаются в уравнениях суммы или разности степеней. Сумма двух кубов утверждает, что (a + b)(a 2 − аб + б 2 ) = а 3 + б 3 . а 3 + б 3 , здесь – разреженный полином.
См. также
[ редактировать ]- Аскольд Хованский , один из главных авторов теории малономов.
Ссылки
[ редактировать ]- ^ Редеи, Л. (1973), Лакунарные полиномы над конечными полями , перевод Фёльдеса И., Elsevier, MR 0352060
- ^ Jump up to: а б Хованский А.Г. (1991), Февномиалы , Переводы математических монографий, вып. 88, перевод Здравковской, Смилки, Провиденс, Род-Айленд: Американское математическое общество, doi : 10.1090/mmono/088 , ISBN 0-8218-4547-0 , МР 1108621
- ^ Рош, Дэниел С. (2018), «Что мы можем (и не можем) делать с разреженными полиномами?», Кауэрс, Мануэль; Овчинников, Алексей; Шост, Эрик (ред.), Труды Международного симпозиума ACM 2018 по символическим и алгебраическим вычислениям, ISSAC 2018, Нью-Йорк, штат Нью-Йорк, США, 16–19 июля 2018 г. , Ассоциация вычислительной техники, стр. 25–30, arXiv : 1807.08289 , doi : 10.1145/3208976.3209027 , S2CID 49868973
- ^ Накос, Василейос (2020), «Почти оптимальное разреженное полиномиальное умножение», IEEE Transactions on Information Theory , 66 (11): 7231–7236, arXiv : 1901.09355 , doi : 10.1109/TIT.2020.2989385 , MR 4173637 , S2CID 59316578
- ^ Джорджи, Паскаль; Грене, Бруно; Перре дю Крей, Армель (2020), «По существу оптимальное разреженное полиномиальное умножение», Труды 45-го Международного симпозиума по символьным и алгебраическим вычислениям (ISSAC '20). , Ассоциация вычислительной техники, стр. 202–209, arXiv : 2001.11959 , doi : 10.1145/3373207.3404026 , S2CID 211003922
- ^ Джорджи, Паскаль; Грене, Бруно; Перре дю Крей, Армель (2021), «О точном делении и проверке делимости разреженных многочленов», Труды Международного симпозиума по символическим и алгебраическим вычислениям 2021 года (ISSAC '21). , Ассоциация вычислительной техники, стр. 163–170, arXiv : 2102.04826 , doi : 10.1145/3452143.3465539 , S2CID 231855563
- ^ Пан, Виктор Ю. (2020), «Ускорение поиска корня подразделения для разреженных полиномов», Компьютерная алгебра в научных вычислениях , Конспекты лекций по информатике, том. 12291, Чам: Спрингер, стр. 461–477, номер документа : 10.1007/978-3-030-60026-6_27 , MR 4184190 , S2CID 224820309 .
- ^ Зиппель, Ричард (1979), «Вероятностные алгоритмы для разреженных полиномов», Символические и алгебраические вычисления (EUROSAM '79, Международный симпозиум, Марсель, 1979) , Конспекты лекций по информатике, том. 72, Берлин, Нью-Йорк: Springer, стр. 216–226, MR 0575692.
- ^ Коэн, SD; Моваххеди, А.; Салинье, А. (1999), «Группы Галуа трехчленов», Journal of Algebra , 222 (2): 561–573, doi : 10.1006/jabr.1999.8033 , MR 1734229
- ^ Аверков Геннадий; Шайдерер, Клаус (07 марта 2023 г.). «Выпуклые оболочки мономиальных кривых и теорема о разреженных положительных местах». arXiv : 2303.03826 [ math.OC ].
 | Эта полиномам, статья, посвященная незавершена . Вы можете помочь Википедии, расширив ее . |