ФАКТОРИЗАЦИЯ БУЛЕВЫХ ПОЛИНОМОВ: ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ И ЭКСПЕРИМЕНТАЛЬНАЯ ОЦЕНКА (2021)
Факторизация полиномов – классическая алгоритмическая проблема алгебры, имеюшая широкий спектр приложений. Особый интерес представляет факторизация над конечными полями, среди которых поле порядка два является, вероятно, наиболее важным в связи с представлением булевых функций полиномами Жегалкина. В частности, факторизация булевых полиномов соответствует конъюнктивной декомпозиции булевых функций, заданных в алгебраической нормальной форме. Кроме того, факторизация дает решение проблемы декомпозиции функций, заданных в СДНФ и позитивных ДНФ, а также декартовой декомпозиции реляционых данных. Эти приложения демонстрируют важность разработки быстрых алгоритмов факторизации. В статье мы рассматриваем некоторые недавно предложенные алгоритмы факторизации полиномиальной сложности и описываем параллельную MIMD-реализацию, которая использует как параллелизм уровня задачи, так и параллелизм уровня данных. Мы представляем эксперименты, выполненные на бенчмарках логического синтеза и на синтетических (случайных) полиномах, которые показывают значительное ускорение факторизации. В заключение представлены результаты тестирования параллельной реализации алгоритма на массивнопараллельной многоядерной архитектуре (Redefine).
Идентификаторы и классификаторы
- eLIBRARY ID
- 44652415
Факторизация полиномов – классическая алгоритмическая проблема алгебры [1], которая имеет широкий спектр приложений. Один вариант проблемы, привлекающий особое внимание — факторизация булевых полиномов, т.е. мультилинейных полиномов над конечным полем порядка 2. Булев многочлен – это одно из широко известных представлений булевых функций, также известных в математической логике как полиномы Жегалкина [2] или каноническая форма Рида–Маллера [3] в синтезе логических схем и теории помехоустойчивого кодирования. В последнее время это представление становится все более популярным в связи со следующими преимуществами. Во-первых, это естественное и компактное представление некоторых важных классов булевых функций (например, арифметические функции, кодеры, и т.д.). Во-вторых, оно допускает естественное отображение в некоторых схемных технологиях (например, основанных на FPGA или в наноструктурной электронике), а также имеет хорошие свойства для тестирования.
Список литературы
- von zur Gathen J., Gerhard J. Modern Computer Algebra. Third edition. New York, NY, USA: Cambridge University Press, 2013. P. 812.
- Жегалкин И.И. Арифметизация символической логики // Математический сборник. 1928. Т. 35. № 1. С. 311-377.
- Muller D.E. Application of Boolean algebra to switching circuit design and to error detection // IRE Transactions on Electronic Computers. 1954. V. EC-3. P. 6-12.
- Емельянов П.Г., Пономарев Д.К. Алгоритмические вопросы конъюнктивной декомпозиции булевых формул // Программирование. 2015. Т. 41. № 3. С. 162-169. EDN: UCBEED
- Emelyanov P., Ponomaryov D. On tractability of disjoint AND-decomposition of boolean formulas // Proceedings of the PSI 2014: 9th Ershov Informatics Conference. V. 8974 of Lecture Notes in Computer Science. Springer, 2015. P. 92-101. EDN: VABFMZ
- Emelyanov P. On two kinds of dataset decomposition // Proceedings of the 18th International Conference on Computational Science (ICCS 2018), Part II. V. 10861 of Lecture Notes in Computer Science. Springer, 2018. P. 171-183. EDN: YBXDEL
- Emelyanov P., Ponomaryov D. Cartesian decomposition in data analysis // Proceedings of the Siberian Symposium on Data Science and Engineering (SSDSE 2017). 2017. P. 55-60. EDN: XXUKUP
- Shpilka A., Volkovich I. On the relation between polynomial identity testing and finding variable disjoint factors // Proceedings of the 37th International Colloquium on Automata, Languages and Programming. Part 1 (ICALP 2010). V. 6198 of Lecture Notes in Computer Science. Springer, 2010. P. 408-419.
- Emelyanov P., Ponomaryov D. On a polytime factorization algorithm for multilinear polynomials over F2 // Proceedings of the 20th International Workshop on Computer Algebra in Scientific Computing (CASC 2018). V. 11077 of Lecture Notes in Computer Science. Springer, 2018. P. 164-176. EDN: YBRHYT
-
Somenzi F. CUDD: CU Decision Diagram package // https://github.com/ivmai/cudd. Accessed 2019-12-11.
-
Corno F., Reorda M. S., Squillero G. RT-level ITC'99 benchmarks and first ATPG results // IEEE Design & Test of Computers. 2000. V. 17. № 3. P. 44-53.
-
Hansen M.C., Yalcin H., Hayes J.P. Unveiling the ISCAS-85 benchmarks: A case study in reverse engineering // IEEE Design Test of Computers. 1999. V. 16. № 3. P. 72-80.
-
Fišer P., Schmidt J. A prudent approach to benchmark collection // Proceedings of the 12th International Workshop on Boolean Problems (IWSBP'2016). 2016. P. 129-136.
-
Redefine - reconfigurable silicon core description // http://morphing.in/redefine. Accessed 2018-12-07.
-
Ponomaryov D. A polynomial time delta-decomposition algorithm for positive DNFs // Proceedings of the 14th International Computer Science Symposium in Russia (CSR'2019). V. 11532 of Lecture Notes in Computer Science. Springer, 2019. P. 325-336. EDN: MIHNNL
Выпуск
Другие статьи выпуска
Предлагается пакет символьного построения экспоненциально-логарифмических решений таких линейных обыкновенных дифференциальных уравнений, которые могут иметь неполностью заданные (усеченные) коэффициенты – степенные ряды, для которых известны только начальные члены. Входящие в решения ряды также представляются конечным числом начальных членов. Для каждого такого ряда вычисляется максимально возможное число начальных членов, полностью определенных известными начальными фрагментами коэффициентов уравнения. При этом степень усечения каждого из этих рядов не может превосходить заданной пользователем величины. Последнее обеспечивает окончание вычисления и тогда, когда по известным фрагментам коэффициентов уравнения может быть определено любое число членов рядов, входящих в решения.
На основе рекуррентных формул Ньютона приведен алгоритм построения результанта двух целых функций, что является одним из методов исключения неизвестных для систем неалгебраических уравнений. Алгоритм реализован в системе компьютерной алгебры Maple. Приведены примеры, демонстрирующие работу данного алгоритма.
В последнее время на место основного языка научных и инженерных расчетов выдвигается язык Julia. У ряда пользователей возникает желание работать полностью внутри “экосистемы” Julia, подобно тому, как происходит работа в “экосистеме” Python. Для Julia существуют библиотеки, покрывающие большинство потребностей научно-инженерных расчетов. Перед авторами возникла необходимость использовать символьные вычисления для задач математического моделирования. Поскольку основным языком реализации численных алгоритмов мы выбрали язык Julia, то и задачи компьютерной алгебры хотелось бы решать на этом же языке. Авторы выделили основные функциональные области, задающие разные варианты применения систем компьютерной алгебры. В каждой из областей нами выделены наиболее характерные представители систем компьютерной алгебры на Julia. В результате авторы делают вывод, что в рамках “экосистемы” Julia возможно (и даже удобно) использовать системы компьютерной алгебры.
Рассматривается поведение квантовой запутанности в процессе унитарной эволюции в конструктивных моделях многокомпонентных квантовых систем. Описываются группы симметрий квантовых систем, допускающих возникновение геометрических структур, ассоциированных с квантовой запутанностью. Алгоритмы моделирования динамики квантовой запутанности основаны на методах компьютерной алгебры и вычислительной теории групп. Приводятся примеры конкретных вычислений.
В статье предложены два наиболее простых метода определения положений равновесия спутника, движущегося в центральном ньютоновом силовом поле по круговой орбите под действием гравитационного момента. В первом методе применялись подходы линейной алгебры, во втором алгоритмы компьютерной алгебры. Положения равновесия спутника в орбитальной системе координат при заданных значениях главных центральных моментов инерции определяются корнями системы нелинейных алгебраических уравнений. Для определения равновесных решений проводилась декомпозиция системы алгебраических уравнений с применением методов линейной алгебры и алгоритмов построения базисов Гребнера. Положения равновесия спутника определялись путем исследования числа действительных корней алгебраических уравнений из полученных базисов Гребнера. С использованием предложенного подхода показано, что спутник с неравными главными центральными моментами инерции имеет на круговой орбите 24 положения равновесия.
Для систем обыкновенных дифференциальных уравнений (ОДУ) с невырожденной линейной частью в общем и гамильтоновом случаях ставится задача отыскания инвариантных координатных подпространств в координатах ее нормальной формы, вычисленной вблизи положения равновесия. Приведены условия существования таких инвариантных подпространств в терминах резонансных соотношений между собственными числами линейной части системы. Дан алгоритм поиска резонансных соотношений между собственными числами без их явного вычисления, который существенно использует методы компьютерной алгебры и q-аналог субрезультантов многочлена. Обсуждается его реализация в трех распространенных системах компьютерной алгебры – Mathematica, Maple и SymPy. Приведены содержательные модельные примеры.
Издательство
- Издательство
- ИЗДАТЕЛЬСТВО НАУКА
- Регион
- Россия, Москва
- Почтовый адрес
- 121099 г. Москва, Шубинский пер., 6, стр. 1
- Юр. адрес
- 121099 г. Москва, Шубинский пер., 6, стр. 1
- ФИО
- Николай Николаевич Федосеенков (Директор)
- E-mail адрес
- info@naukapublishers.ru
- Контактный телефон
- +7 (495) 2767735