Факторизация многомерных полиномов

[Andrey_Kireew]

Известно, что любой полином одной переменной может быть
представлен в виде:
$(x-r_1)(x-r_2)...(x-r_n)=0$ , где $r_1 ... r_n$ - комплексные корни
справедливо ли это для многомерных полиномов, т.е. можно ли представить многомерный полином в виде
$(1-a_1x_1-a_2x_2-a_3x_3...a_nx_n)(1-b_1x_1-b_2x_2-...b_nx_n)...(1-c_1x_1-..c_nx_n)$, где $a_1..a_n..c_n $- комплексные коэффициенты
(очевидно что для действительных коэффициентов это в общем случае невозможно)

[Xaositect]

Нет. Любой многочлен такого вида, который Вы написали, обращается в 0 на объединении гиперплоскостей $a_1 x_1 + \dots + a_n x_n = 1$ и т.п. Значит, многочлены, у которых множество нулей не имеет такого вида, не могут таким образом раскладываться. Простейший пример - $x^2 + y^2 + 1$.

[Andrey_Kireew]

большое спасибо
проверив Ваш контрпример убедился что это действительно так - и это весьма неприятно

в таком случае у меня возникает вопросы: существуют ли критерии приводимости многомерных многочленов над полем комплексных чисел?
можно ли аппроксимировать произвольный многомерный многочлен с помощью такой факторизации?

-- 07.10.2015, 13:59 --

в дополнение к вышеизложенному хочу сообщить, что многочлены получаются при вычислении определителя матрицы, элементами которой являются линейные многочлены
многочлен определителя в простейшем случае содержит более 200000 элементов и возникает необходимость его факторизации с целью дальнейшего анализа
попытки использовать символьные вычисления в Maple ни к чему не привели, комп через 2 суток усердной работы намертво завис

[Lia]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[Xaositect]

Andrey_Kireew в сообщении #1060160 писал(а):

в таком случае у меня возникает вопросы: существуют ли критерии приводимости многомерных многочленов над полем комплексных чисел?

Насколько мне известно, простых критериев нет. Вот статья по алгоритмам факторизации, может, найдете там в ссылках что-нибудь полезное: http://lecerf.perso.math.cnrs.fr/public ... idmpfa.pdf . Насколько я понял, основной факт в существующих алгоритмах факторизации это теорема Рупперта: многочлен $f$ можно разложить на множители, если имеется нетривиальное решение уравнений $\frac{\partial}{\partial x_i} (f_i/f) = \frac{\partial}{\partial x_j} (f_j/f)$, при этом степень $f_i$ можно ограничить и потому эту систему можно свести к системе линейных уравнений, правда, очень большой.

Andrey_Kireew в сообщении #1060160 писал(а):

можно ли аппроксимировать произвольный многомерный многочлен с помощью такой факторизации?

Нет. Многочлены указанного вида образуют замкнутое алгебраическое подмножество в пространстве всех многочленов.

Andrey_Kireew в сообщении #1060160 писал(а):

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

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

В общем, если идти в эту сторону, то все плохо. В чем у Вас исходная задача состоит?

[Andrey_Kireew]

Есть матричное уравнение
$Y=V+LA^{-1}L^T$, где V, A, L - матрицы, все элементы которых - линейные многомерные многочлены, Y - комплексная матрица
уравнение решается итеративно, методом Ньютона-Рафсона, и другими подобными методами, но алгоритмы очень трудоёмкие даже для простейших моделей
возникла идея свести это уравнение к СНАУ. Для этого я преобразую исходное уравнение к виду
$det(A)Y=det(A)V+LA^*L^T$, где $A^*$ - союзная матрица
элементы союзной матрицы, так же как и сам определитель уже многомерные многочлены
в итоге СНАУ в принципе получена, но оказалась чрезвычайно громоздкой. в принципе её можно решать методом Зейделя, но выигрыш перед непосредственным решением матричного уравнения представляется сомнительным

весьма заманчивым на мой взгляд является представление многочленов в виде представленной мной ранее факторизации,
это позволит получить обозримые результаты и упростить их интерпретацию, решить систему в факторизованном виде разумеется тоже значительно проще
мои предположения основаны на теореме Колмогорова из которой следует что любая функция многих переменных может быть представлена суперпозицией одномерных функций, число которых $2N+1$ - где N - число переменных, т.е. видимо есть возможность существенно сократить размеры этих полиномов, если даже не точно, то аппроксимировать их с заданной точностью,
но мне не хотелось бы использовать для этого нейросетевой подход, а желательно перейти от исходных многочленов к новым функциям аналитически

[Brukvalub]

Andrey_Kireew в сообщении #1060354 писал(а):

весьма заманчивым на мой взгляд является представление многочленов в виде представленной мной ранее факторизации

Andrey_Kireew в сообщении #1060354 писал(а):

мои предположения основаны на теореме Колмогорова из которой следует что любая функция многих переменных может быть представлена суперпозицией одномерных функций, число которых $2N+1$ - где N - число переменных

Интересно, вы считаете, что факторизация и суперпозиция - это одно и то же?

[Xaositect]

Стоп, у нас же численные методы. Разве нельзя при конкретных значениях $x$ искать определитель и присоединенную матрицу без расписывания полиномов?

[Andrey_Kireew]

Brukvalub в сообщении #1060536 писал(а):

Andrey_Kireew в сообщении #1060354 писал(а):

весьма заманчивым на мой взгляд является представление многочленов в виде представленной мной ранее факторизации

Andrey_Kireew в сообщении #1060354 писал(а):

мои предположения основаны на теореме Колмогорова из которой следует что любая функция многих переменных может быть представлена суперпозицией одномерных функций, число которых $2N+1$ - где N - число переменных

Интересно, вы считаете, что факторизация и суперпозиция - это одно и то же?

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

[Someone]

Andrey_Kireew в сообщении #1060679 писал(а):

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

А Вы всё-таки распишите.

[Andrey_Kireew]

Если вы под X имеете ввиду начальное приближение - то да, можно, такие алгоритмы я уже составил, планирую в скором времени их исследовать на предмет сходимости, но изначально понятно, что они очень трудоёмкие, так как требуют вычисления обратной матрицы на каждой новой итерации, а размер этой матрицы приличный.
Чтобы этого избежать я предпринял попытку аналитического обращения этой матрицы и пришел к многочленам, однако как оказалось позднее от них мало пользы в таком виде как они есть (определитель у меня занял 1,5ГБ оперативной памяти, и это только с двумя значащими цифрами коэффициентов, союзную матрицу я уже не стал рассчитывать, так как в мой комп она не поместится),
тогда и возникла идея замены этих многочленов более компактными функциями
факторизация, как я теперь понимаю, в общем случае здесь не подходит, хотя это был бы лучший вариант

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

-- 09.10.2015, 02:55 --

Someone в сообщении #1060681 писал(а):

Andrey_Kireew в сообщении #1060679 писал(а):

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

А Вы всё-таки распишите.

$(1-a_1x_1-a_2x_2...a_nx_n)(1-b_1x_1-b_2x_2...b_nx_n)...(1-c_1x_1-c_2x_2...c_nx_n)=exp(ln(1-a_1x_1-a_2x_2...a_nx_n)+...ln(1-c_1x_1-c_2x_2...c_nx_n))$

[Someone]

Но в правой части у Вас не многочлены. Так не интересно.

[Brukvalub]

Так ведь в предложенном Колмогоровым и Арнольдом решении 13-й проблемы Гильберта, во-первых, речь идет о вещественном случае, во-вторых, никак не оговариваются условия на конкретный вид участвующих в суперпозиции функций, гарантируется только их непрерывность.
Требуется недюжинная фантазия, чтобы увидеть в основном логарифмическом тождестве 13-ю проблему Гильберта!

[Xaositect]

Andrey_Kireew в сообщении #1060690 писал(а):

Чтобы этого избежать я предпринял попытку аналитического обращения этой матрицы и пришел к многочленам, однако как оказалось позднее от них мало пользы в таком виде как они есть (определитель у меня занял 1,5ГБ оперативной памяти, и это только с двумя значащими цифрами коэффициентов, союзную матрицу я уже не стал рассчитывать, так как в мой комп она не поместится),
тогда и возникла идея замены этих многочленов более компактными функциями

Попробуйте какие-нибудь тензорные разложения. Если представить Ваш многочлен в виде $\sum c_{i_1 \dots i_d} x_{i_1}\dots x_{i_d}$ (для неоднородного надо добавить фиктивную переменную равную $1$ для одночленов, у которых степень меньше степени многочлена). $c_{i_1 \dots i_d}$ - это какой-то тензор, с которым уже можно разбираться. Каноническое разложение этого тензора - это представление в виде $c_{i_1\dots i_d} = \sum_s a^{(1)}_{s i_1}\dots a^{(d)}_{s i_d}$, то есть представление Вашего многочлена в виде суммы таких, про которые Вы спрашивали. Tensor-train разложение Оселедца - это представление в виде $\sum_{s_1 \dots s_{d-1}} a^{(1)}_{i_1 s_1} a^{(2)}_{s_1 i_2 s_2} \dots a^{(d)}_{s_{d-1} i_d}$, позволяет сократить место для больших $d$.