2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Факторизация многомерных полиномов
Сообщение07.10.2015, 11:19 


07/10/15

2400
Известно, что любой полином одной переменной может быть
представлен в виде:
$(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 $- комплексные коэффициенты
(очевидно что для действительных коэффициентов это в общем случае невозможно)

 Профиль  
                  
 
 Re: Факторизация многомерных полиномов
Сообщение07.10.2015, 11:49 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Факторизация многомерных полиномов
Сообщение07.10.2015, 12:35 


07/10/15

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

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

-- 07.10.2015, 13:59 --

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

 Профиль  
                  
 
 Posted automatically
Сообщение07.10.2015, 13:09 
Модератор


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

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

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

 Профиль  
                  
 
 Posted automatically
Сообщение07.10.2015, 22:15 
Модератор


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

 Профиль  
                  
 
 Re: Факторизация многомерных полиномов
Сообщение07.10.2015, 22:40 
Заслуженный участник
Аватара пользователя


06/10/08
6422
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 писал(а):
в дополнение к вышеизложенному хочу сообщить, что многочлены получаются при вычислении определителя матрицы, элементами которой являются линейные многочлены
В виде такого определителя можно на самом деле представить любой многочлен, так что без конкретики это уточнение не особо помогает.

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

 Профиль  
                  
 
 Re: Факторизация многомерных полиномов
Сообщение07.10.2015, 23:31 


07/10/15

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

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

 Профиль  
                  
 
 Re: Факторизация многомерных полиномов
Сообщение08.10.2015, 17:29 
Заслуженный участник
Аватара пользователя


01/03/06
13619
Москва
Andrey_Kireew в сообщении #1060354 писал(а):
весьма заманчивым на мой взгляд является представление многочленов в виде представленной мной ранее факторизации

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

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

 Профиль  
                  
 
 Re: Факторизация многомерных полиномов
Сообщение08.10.2015, 19:40 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Факторизация многомерных полиномов
Сообщение09.10.2015, 00:42 


07/10/15

2400
Brukvalub в сообщении #1060536 писал(а):
Andrey_Kireew в сообщении #1060354 писал(а):
весьма заманчивым на мой взгляд является представление многочленов в виде представленной мной ранее факторизации

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

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

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

 Профиль  
                  
 
 Re: Факторизация многомерных полиномов
Сообщение09.10.2015, 00:55 
Заслуженный участник
Аватара пользователя


23/07/05
17731
Москва
Andrey_Kireew в сообщении #1060679 писал(а):
несложно показать что она к таковой сводится, думаю нет смысла расписывать тривиальные вещи
А Вы всё-таки распишите.

 Профиль  
                  
 
 Re: Факторизация многомерных полиномов
Сообщение09.10.2015, 01:29 


07/10/15

2400
Если вы под 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))$

 Профиль  
                  
 
 Re: Факторизация многомерных полиномов
Сообщение09.10.2015, 08:10 
Заслуженный участник
Аватара пользователя


23/07/05
17731
Москва
Но в правой части у Вас не многочлены. Так не интересно.

 Профиль  
                  
 
 Re: Факторизация многомерных полиномов
Сообщение09.10.2015, 08:53 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Факторизация многомерных полиномов
Сообщение09.10.2015, 09:32 
Заслуженный участник
Аватара пользователя


06/10/08
6422
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$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group