Деление многопеременных многочленов.

[Munin]

st4s1k в сообщении #1356832 писал(а):

Нет явно установленного алгоритма деления многопеременных многочленов.

Нет даже явно установленного определения, что считать результатом такого деления.

Для многочленов от одной переменной выбирается такое представление $P=QD+R,$ что $\operatorname{deg}R<\operatorname{deg}D$ (это всегда можно сделать), и отсюда приходят к выводу об однозначности $R$ и $Q.$

Для многочленов от нескольких переменных, например, $a^2+ab+b^2 : a+b,$ можно выбрать, например, представления

$a^2+ab+b^2=a(a+b)+b^2$
$a^2+ab+b^2=b(a+b)+a^2$

и не будет никакого критерия выбрать один из этих вариантов (или какой-то третий).

[st4s1k]

Munin в сообщении #1357064 писал(а):

и не будет никакого критерия выбрать один из этих вариантов (или какой-то третий).

Я кажется понял. А есть возможность просчитать все эти варианты?

Например, присвоить приоритет каждой переменной по алфавиту. Я пока не совсем уверен в том, о чём говорю, но конкретно для вашего примера:

Munin в сообщении #1357064 писал(а):

Для многочленов от нескольких переменных, например, $a^2+ab+b^2 : a+b,$ можно выбрать, например, представления
$a^2+ab+b^2=a(a+b)+b^2$
$a^2+ab+b^2=b(a+b)+a^2$

Сначала вывести $a$ за скобки, сохранить результат в масив, а потом вывести $b$ за скобки, и сохранить результат. И вот у нас уже массив из двух результатов.

То есть, начать с первой по алфавитному порядку переменной, найти все члены содержащие эту переменную, решить эту задачу исходя из этих условий. Это возможно? Я не против множества результатов, возможно я найду принцип отбора необходимого мне многочлена, это уже другой вопрос, в крайнем случае буду использовать первый "попавшийся".

[Dmitriy40]

st4s1k в сообщении #1357070 писал(а):

Например, присвоить приоритет каждой переменной по алфавиту.

Это бред: назову я переменные по другому - и получу совсем другой результат?! А если переменные из разных алфавитов и упорядочить их в один список просто нельзя?
Короче бред!
Если Вам зачем-то такого хочется - делайте, но это никоим образом не будет операцией деления. И лучше даже не называйте это так, не поймут-с.

[st4s1k]

Dmitriy40 в сообщении #1357120 писал(а):

Это бред: назову я переменные по другому - и получу совсем другой результат?!

Вы, в теории, получите тот же самый массив результатов, просто отсортированный в другом порядке.

[Dmitriy40]

st4s1k в сообщении #1357126 писал(а):

просто отсортированный в другом порядке

А порядок в массиве на смысл не влияет? Уверены? Зачем тогда его вообще сортировать? И зачем выносить за скобки переменные по алфавиту, давайте уж просто по порядку встречаемости в записи или вообще произвольном? И какое отношение это имеет к делению многочленов?
А если таки смысл от порядка зависит, то массив окажется другой.

[g______d]

Ну уж после ссылок-то можно было их посмотреть, а потом комментировать. Для деления многочленов от нескольких переменных, действительно, нужно ввести отношения порядка с некоторыми свойствами на множестве одночленов, и ответ от него будет зависеть.

https://en.wikipedia.org/wiki/Monomial_order

[Munin]

st4s1k в сообщении #1357070 писал(а):

А есть возможность просчитать все эти варианты?

Вроде бы, их бесконечно много.

[st4s1k]

Munin в сообщении #1357154 писал(а):

st4s1k в сообщении #1357070 писал(а):

А есть возможность просчитать все эти варианты?

Вроде бы, их бесконечно много.

Может есть какая нибудь возможность получить первый попавшийся результат. Либо получить один результат, соответствующий определённым критериям / условиям, продиктованными требованиями пользователя, например предпочтение какой либо переменной (очень грубо говоря).

Взять даже ваш пример:

Munin в сообщении #1357064 писал(а):

Для многочленов от нескольких переменных, например, $a^2+ab+b^2 : a+b,$ можно выбрать, например, представления
$a^2+ab+b^2=a(a+b)+b^2$
$a^2+ab+b^2=b(a+b)+a^2$ и не будет никакого критерия выбрать один из этих вариантов (или какой-то третий).

Все одночлены записываются в массив и сортируются по степени и алфавиту.

$$ \lbrack \begin{matrix} a^2 & b^2 & ab \end{matrix} \rbrack $$

Потом для первой, по алфавиту, переменной, в данном случае $a$ , осуществляется поиск всех одночленов содержащих эту переменную; эта переменная выводится "за скобки", а в скобках все одночлены делятся на эту переменную. Потом этот процесс повторяется рекурсивно для одночленов находящихся внутри этой скобки (или нет? я не знаю как правильно осуществлять факторизацию), после обрабатывается следующая переменная по алфавиту.

Не хотелось бы вовлекать рассуждения о способах реализации с точки зрения программирования, т.к. компьютерная программа лишь инструмент для реализации математических алгоритмов (в этом случае).

[Munin]

st4s1k в сообщении #1357190 писал(а):

Все одночлены записываются в массив и сортируются по степени и алфавиту.

$$ \lbrack \begin{matrix} a^2 & b^2 & ab \end{matrix} \rbrack $$

Скорее если уж сортировать, то именно в порядке $a^2\prec ab\prec b^2$: суммарная степень везде 2, а степень переменной $a$ постепенно понижается. Такой порядок можно ввести на любых одночленах одинаковой степени, например, $a^2b\prec ab^2\prec abc.$

То, что вы дальше описываете, схоже с предложением Xaositect в post1356815.html#p1356815 .

[st4s1k]

Munin в сообщении #1357201 писал(а):

Скорее если уж сортировать, то именно в порядке $a^2\prec ab\prec b^2$: суммарная степень везде 2, а степень переменной $a$ постепенно понижается. Такой порядок можно ввести на любых одночленах одинаковой степени, например, $a^2b\prec ab^2\prec abc.$

Да, вы правы, я не заметил.

Munin в сообщении #1357201 писал(а):

То, что вы дальше описываете, схоже с предложением Xaositect в post1356815.html#p1356815 .

Я не совсем понял его предложение, поэтому не стал ничего отвечать. Если можно было бы пример самый простой, чтоб я принцип понял.

-- 27.11.2018, 21:26 --

g______d в сообщении #1357043 писал(а):

По поводу теории нужно начать отсюда:
https://en.wikipedia.org/wiki/Gröbner_basis#Reduction

Мне показалось довольно интересно и по делу.

Вот что я ещё нашёл, тоже вроде касается моей проблемы довольно плотно:
https://www.usna.edu/Users/cs/roche/cou ... mvpoly.pdf

Тут так же говорится о переходе от многопеременных к однопеременным многочленам, только мне почему-то сложно даётся это понять:

Цитата:

Note that if the array is stored contiguously in row-major order, the representation of $f \left (x_1, x_2, ... , x_n \right )$ is the same as that for the dense univariate polynomial over $F \left (y \right )$ given by

$$f \left (y^{d_2 d_3 ... d_n},y^{d_3 d_4 ... d_n}, ... , y^{d_n}, y \right )$$

If we set the dimensions high enough to make room for the result, converting from multivariate
to univariate in this fashion is the most obvious way of using fast univariate arithmetic methods
for multivariate computation (known as “Kronecker substitution”).

[st4s1k]

Я нашёл ПО под линукс, схожее с Wolfram Mathematica, Sage называется, и "скормил" ему пример, который описал в шапке темы.

st4s1k в сообщении #1356774 писал(а):

Пример:

$$f(a, b, c, d) = 4ac^3 + 3.14b^3cd+2abd+a+1$$

$$g(a, b, d) = 3a^2 + 2ad + b^2 + d$$

Чему будет равно:

$$h(a, b, c, d) = \frac {f(a, b, c, d)} {g(a, b, d)} = \frac {4ac^3 + 3.14b^3cd+2abd+a+1} {3a^2 + 2ad + b^2 + d} = ? $$

Результат этого деления, ПО отображает как массив из двух элементов, неполное частное и остаток:
$\left \lbrack \frac { \left ( 3.14 \cdot b^3 \cdot c + 2 \cdot a \cdot b \right ) } { \left ( 2 \cdot a + 1 \right ) } , \frac { \left ( -3.14 \cdot b^5 \cdot c - 6 \cdot a^3 \cdot b - \left ( 9.42 \cdot a^2 \cdot c + 2 \cdot a \right ) \cdot b^3 + 2 \cdot \left ( 4 \cdot c^3 + 1 \right ) \cdot a^2 + \left ( 4 \cdot c^3 + 3 \right ) \cdot a + 1 \right ) }{ \left ( 2 \cdot a + 1 \right ) } \right \rbrack$

$$q = \frac { \left ( 3.14 \cdot b^3 \cdot c + 2 \cdot a \cdot b \right ) } { \left ( 2 \cdot a + 1 \right ) }$$

$$r = \frac { \left ( -3.14 \cdot b^5 \cdot c - 6 \cdot a^3 \cdot b - \left ( 9.42 \cdot a^2 \cdot c + 2 \cdot a \right ) \cdot b^3 + 2 \cdot \left ( 4 \cdot c^3 + 1 \right ) \cdot a^2 + \left ( 4 \cdot c^3 + 3 \right ) \cdot a + 1 \right ) }{ \left ( 2 \cdot a + 1 \right ) }$$

$$h = q + r = \frac { \left ( 3.14 \cdot b^3 \cdot c + 2 \cdot a \cdot b \right ) } { \left ( 2 \cdot a + 1 \right ) } + \frac { \left ( -3.14 \cdot b^5 \cdot c - 6 \cdot a^3 \cdot b - \left ( 9.42 \cdot a^2 \cdot c + 2 \cdot a \right ) \cdot b^3 + 2 \cdot \left ( 4 \cdot c^3 + 1 \right ) \cdot a^2 + \left ( 4 \cdot c^3 + 3 \right ) \cdot a + 1 \right ) }{ \left ( 2 \cdot a + 1 \right ) }$$

Хотелось бы добиться такого результата.