Введение
Порядок членов многочлена
In mathematics, a monomial order (sometimes called a term order or an admissible order) is a total order on the set of all (monic) monomials in a given polynomial ring, satisfying the property of respecting multiplication, i. e.,
If and is any other monomial, then
Monomial orderings are most commonly used with Gröbner bases and multivariate division. In particular, the property of being a Gröbner basis is always relative to a specific monomial order.
В математике, порядок мономов (иногда называемый порядком слагаемых или допустимым порядком) — это полный порядок на множестве всех (нормализованных) мономов в заданном кольце многочленов, удовлетворяющий свойству согласованности с умножением, то есть, если и — любой другой моном, то
In mathematics, a monomial order (sometimes called a term order or an admissible order) is a total order on the set of all (monic) monomials in a given polynomial ring, satisfying the property of respecting multiplication, i. e.,
If and is any other monomial, then
Monomial orderings are most commonly used with Gröbner bases and multivariate division. In particular, the property of being a Gröbner basis is always relative to a specific monomial order.
Порядок мономов наиболее часто используется при работе с базисами Грёбнера и многомерным делением. В частности, свойство быть базисом Грёбнера всегда относительно конкретного порядка мономов.
In mathematics, a monomial order (sometimes called a term order or an admissible order) is a total order on the set of all (monic) monomials in a given polynomial ring, satisfying the property of respecting multiplication, i. e.,
If and is any other monomial, then
Monomial orderings are most commonly used with Gröbner bases and multivariate division. In particular, the property of being a Gröbner basis is always relative to a specific monomial order.
Ведущие мономиалы, термина и коэффициенты
Выбор полного порядка на мономах позволяет упорядочить члены многочлена. Ведущий член многочлена – это, таким образом, член с наибольшим мономом (относительно выбранного порядка на мономах). Конкретно, пусть R – любое кольцо многочленов. Тогда множество M (мономических) мономов в R является базисом R, рассматриваемого как векторное пространство над полем коэффициентов. Следовательно, любой ненулевой полином p в R имеет единственное представление в виде линейной комбинации мономов, где S – конечное подмножество M, а коэффициенты cu все отличны от нуля. Когда порядок на мономах выбран, ведущим мономом является наибольший u в S, ведущим коэффициентом – соответствующий cu, а ведущим членом – соответствующий cuu. Термины "главный моном/коэффициент/член" иногда используются как синонимы "ведущий". Некоторые авторы используют "моном" вместо "члена" и "произведение степеней" вместо "моном". В данной статье под мономом подразумевается выражение без коэффициента. Определяющее свойство порядка на мономах влечет за собой сохранение порядка членов при умножении многочлена на моном. Кроме того, ведущий член произведения многочленов равен произведению ведущих членов сомножителей.
as a linear combination of monomials, where S is a finite subset of M and the cu are all nonzero. When a monomial order has been chosen, the leading monomial is the largest u in S, the leading coefficient is the corresponding cu, and the leading term is the corresponding cuu. Head monomial/coefficient/term is sometimes used as a synonym of "leading". Some authors use "monomial" instead of "term" and "power product" instead of "monomial". In this article, a monomial is assumed to not include a coefficient. The defining property of monomial orderings implies that the order of the terms is kept when multiplying a polynomial by a monomial. Also, the leading term of a product of polynomials is the product of the leading terms of the factors.
Примеры
На множестве степеней любой одной переменной x единственными мономиальными порядками являются естественный порядок 1 < x < x² < x³ < … и его обратный, последний из которых не является отношением полного порядка. Поэтому понятие мономиального порядка становится интересным только в случае нескольких переменных. Мономиальный порядок подразумевает порядок на отдельных неопределённостях. Можно упростить классификацию мономиальных порядков, предполагая, что неопределённости называются x₁, x₂, x₃, … в порядке убывания для рассматриваемого мономиального порядка, так что всегда 1 = x₁ > x₂ > x₃ > … (Если должно быть бесконечно много неопределённостей, эта конвенция несовместима с условием полного порядка, и необходимо использовать обратный порядок; однако случай многочленов от бесконечного числа переменных редко рассматривается.) В примере ниже мы используем x, y и z вместо x₁, x₂ и x₃. При этом соглашении всё ещё существует множество примеров различных мономиальных порядков.
Постепенный обратный лексикографический порядок
Определенный обратный лексикографический порядок (grevlex, или degrevlex для порядка обратного лексикографического по степени) сравнивает сначала общую степень, затем использует лексикографический порядок для разрешения равенства, но при этом меняет результат лексикографического сравнения так, что лексикографически большие мономы той же степени считаются меньше в degrevlex-порядке. Чтобы окончательный порядок соответствовал стандартному упорядочению неопределенных 1=x1 > x2 > … > xn, необходимо, чтобы лексикографический порядок, используемый для разрешения равенства до обращения, считал последний неопределенный элемент xn наибольшим, то есть начинал с него. Таким образом, конкретный алгоритм для определенного обратного лексикографического порядка заключается в следующем: сначала сравнить по общей степени, затем сравнить показатели последнего неопределенного элемента xn, но изменить результат (то есть мономы с меньшим показателем считаются большими в порядке), затем (только в случае равенства) аналогично сравнить xn−1 и так далее, заканчивая x1. Различия между определенным лексикографическим и определенным обратным лексикографическим порядками незначительны, поскольку они фактически совпадают для 1 и 2 неопределенных. Первое различие проявляется для мономов 2-й степени в 3 неопределенных, которые в определенном лексикографическом порядке упорядочиваются как , а в определенном обратном лексикографическом порядке – как . Общая тенденция заключается в том, что обратный порядок включает все переменные среди мономов наименьшей степени для заданной степени, в то время как в прямом порядке интервалы мономов наименьшей степени для заданной степени формируются только из наименьших переменных.
Приказ об устранении
Порядок блоков или порядок исключения (lexdeg) может быть определен для любого числа блоков, но для упрощения мы рассмотрим только случай двух блоков (однако, если число блоков равно числу переменных, этот порядок является просто лексикографическим). Для этого упорядочения переменные разделяются на два блока: x1, …, xh и y1, …, yk, и для каждого блока выбирается порядок мономов, обычно градуированный обратный лексикографический порядок. Два монома сравниваются путем сравнения их x-части, а в случае равенства – путем сравнения их y-части. Этот порядок важен, поскольку он позволяет проводить исключение, операцию, которая соответствует проекции в алгебраической геометрии.
Связанные понятия
Порядок устранения гарантирует, что мономиал, содержащий любой из набора неизвестных, всегда будет больше, чем мономиал, не содержащий ни одного из них. Порядок произведения является наиболее простым примером порядка устранения. Он заключается в объединении порядков мономов на непересекающихся множествах неизвестных в порядок мономов на их объединении. Он просто сравнивает показатели неизвестных в первом множестве, используя первый порядок мономов, а затем разрешает ничью, используя другой порядок мономов для неизвестных во втором множестве. Этот метод очевидно обобщается на любое непересекающееся объединение множеств неизвестных; лексикографический порядок может быть получен из сингулярных множеств {x1}, {x2}, {x3} (с единственным порядком мономов для каждого сингулярного множества). При использовании порядков мономов для вычисления базисов Грёбнера, различные порядки могут приводить к разным результатам, и сложность вычисления может значительно варьироваться. Например, градуированный обратный лексикографический порядок имеет репутацию почти всегда давать базисы Грёбнера, которые легче всего вычислить (это обусловлено тем фактом, что при достаточно общих условиях на идеале, многочлены в базисе Грёбнера имеют степень, которая в большинстве случаев экспоненциальна относительно числа переменных; подобного результата о сложности не существует для какого-либо другого порядка). С другой стороны, порядки устранения необходимы для задач исключения и относительных задач.