2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Недостатки различных систем при факторизации полиномов
Сообщение11.03.2015, 03:21 


07/02/13
21
Вопрос обращён к тем, кто имеет большой стаж работы (более пяти лет) с различными системами компьютерной алгебры, а также, возможно, математическими пакетами.

Скажите, какие недостатки вы встречали у функции факторизации полиномов в этих системах? К примеру, вот основные недостатки функции factor из системы Maple:
  • функция factor не предоставляет возможности выбора простого числа $p$ (можно указать только полином), которое необходимо для факторизации в поле по модулю $p$. Это число подбирается автоматически посредством внутренних механизмов функции factor. Это ограничивает возможности исследователя, так как иногда необходимо выбирать модуль вручную, чтобы добиться большей скорости при нахождении разложения полинома.
  • функция factor не имеет современного (соответствующего новым стандартам Maple) дебаг-вывода, что также усложняет отслеживание хода факторизации. Иногда функция может просто вернуться с ошибкой, но из этого нельзя сделать никаких выводов о том, что же не получилось сделать при факторизации.
  • функция factor не параллелится. В последние годы в Maple активно развиваются средства поддержки распределённых и многоядерных вычислений. Так, например, пакет Threads в системе Maple предоставляет интерфейс пользовательского уровня для написания параллельного кода, но функция factor не переписана под современные стандарты системы Maple.
  • система Maple не справляется с очень большими коэффициентами в сочетании с большой степенью полинома, функция factor просто "умирает". К примеру, степень полинома 30 тысяч и более, а коэффициенты порядка $10^{100}$ знаков (говорю навскидку, сам границу не выводил, размер таких полиномов при сохранении в текстовый файл может достигать гигабайтов).

К примеру, меня интересуют следующие системы: Mathematica, MatLab, MathCad, Maxima и другие, где есть такой функционал.

 Профиль  
                  
 
 Re: Недостатки различных систем при факторизации полиномов
Сообщение11.03.2015, 18:49 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Маткад на помойку, это раз.
Далее про Wolfram Mathematica.
Функция Factor напрямую предоставляет возможность указания этого самого $p$.
В M. автоматически параллелится всё, что может параллелиться. Если что-то не параллелится, попытайтесь распараллелить его функцией Parallelize.
Большие коэффициенты и степени M. по барабану. Она сжуёт всё, что ей подложат. Но потребует соответствующего процессора и объёма оперативной памяти.

 Профиль  
                  
 
 Re: Недостатки различных систем при факторизации полиномов
Сообщение05.06.2015, 17:51 


07/02/13
21
Функция Factor предоставляет не возможность указания числа $p$, а факторизацию по модулю. Это разные вещи. Мне нужно факторизовать полином с коэффициентами из кольца целых чисел, а не в полях Галуа. Просто один из этапов этой факторизации, это разложить его алгоритмом Берлекампа или Кантора-Цассенхауса в поле по модулю простого числа, именно его я и хотел задавать руками, так как есть настолько сложные случаи, что там желательно подключать ручное управление факторизацией.

Далее.

Цитата:
Большие коэффициенты и степени M. по барабану.

Фигня.

К примеру, полином 336 степени с длинной коэффициентов 556 цифр и 16 неприводимыми множителями Maple считает 0.3 секунды, а Математика 11 секунд. Следующий полином математика у меня считает уже больше 2400 секунд (40 минут), в то время как Maple с ним разобрался за 32 секунды. Всё считалось на одном компьютере.

 Профиль  
                  
 
 Re: Недостатки различных систем при факторизации полиномов
Сообщение05.06.2015, 20:53 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Что ж, вы заставили меня признать, что не всё так просто. Возможно, требуется некоторая оптимизация кода. buti, если вы приведёте конкретные примеры задач по факторизации, с которыми Мэйпл справляется на порядки быстрее M, я, пожалуй, озадачу ими разработчиков и прочих людей, приближённых к WRI.

 Профиль  
                  
 
 Re: Недостатки различных систем при факторизации полиномов
Сообщение06.06.2015, 00:37 


07/02/13
21
Залил на файлообменник: http://rghost.ru/8qmG6Mw84

P5 в Математике 9 считался около 3500 секунд, Мэпл 17 версии (хотя сама факторизация там с Мэпла 6) делает это за 2.3 секунды. Всё запускалось в ОС Linux.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



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

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


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

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