УДК 004.421.2:004.032.24:512.714+ Исследование масштабируемости параллельных Д. А. Янович Лаборатория информационных технологий Объединённый институт ядерных исследований ул. <...> 6, Дубна, Московская область, Россия, 141980 В прошлых работах автором была представлена программная реализация двух подходов к параллелизации вычислений базисов Грёбнера и инволютивных базисов полиномиальных систем: на уровне редукций полиномов с вычислениями, проводимыми в кольце Z и на уровне вычисления базисов целиком по модулю простого числа с последующим подъёмом результатов. <...> Их масштабируемость была исследована только на восьмиядерном компьютере. <...> В этой работе приводятся результаты тестирования улучшенной реализации данных алгоритмов на компьютере с 32 ядрами, производится анализ масштабируемости и факторов, на неё влияющих. <...> Введение Мы будем использовать следующие обозначения: X = {x1, . . . ,xn} — множество полиномиальных переменных. <...> M — множество мономов, т.е. произведение степеней переменных из X с целыми неотрицательными показателями. lm(f) и lt(f) — старший моном и старший одночлен многочлена f ∈ R \ {0}, соответственно. <...> M(f,F) ⊂ X и NM(f,F) = X \ M(f,F) — множество мультипликативных и немультипликативных переменных соответственно. <...> Разделение переменных на немультипликативные и мультипликативные переменные порождает инволютивной деление мономов [1, 2]. <...> Это деление определяется по заданному конечному набору многочленов F и порядку на мономах ≻ следующим образом: если мономы u ∈ lm(F), v и w связаны соотношением w = u · v и при этом моном v содержит только мультипликативные переменные для u, то u является инволютивным делителем монома w. <...> В этом случае мы будем записывать отношение инволютивной делимости как u |L w. <...> Конечное множество F ненулевых многочленов является инволютивно автореNFL(p,F) = ˜ p = p−∑ ij дуцированным, если каждый моном, входящий в f ∈ F, не имеет инволютивных делителей среди lm(F) \ {lm(f)}. инволютивная нормальная форма NFL(p,F) многочлена p ̸∈ F <...>