2014 dxdy logo

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

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




 
 Недостатки различных систем при факторизации полиномов
Сообщение11.03.2015, 03: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 
Аватара пользователя
Маткад на помойку, это раз.
Далее про Wolfram Mathematica.
Функция Factor напрямую предоставляет возможность указания этого самого $p$.
В M. автоматически параллелится всё, что может параллелиться. Если что-то не параллелится, попытайтесь распараллелить его функцией Parallelize.
Большие коэффициенты и степени M. по барабану. Она сжуёт всё, что ей подложат. Но потребует соответствующего процессора и объёма оперативной памяти.

 
 
 
 Re: Недостатки различных систем при факторизации полиномов
Сообщение05.06.2015, 17:51 
Функция Factor предоставляет не возможность указания числа $p$, а факторизацию по модулю. Это разные вещи. Мне нужно факторизовать полином с коэффициентами из кольца целых чисел, а не в полях Галуа. Просто один из этапов этой факторизации, это разложить его алгоритмом Берлекампа или Кантора-Цассенхауса в поле по модулю простого числа, именно его я и хотел задавать руками, так как есть настолько сложные случаи, что там желательно подключать ручное управление факторизацией.

Далее.

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

Фигня.

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

 
 
 
 Re: Недостатки различных систем при факторизации полиномов
Сообщение05.06.2015, 20:53 
Аватара пользователя
Что ж, вы заставили меня признать, что не всё так просто. Возможно, требуется некоторая оптимизация кода. buti, если вы приведёте конкретные примеры задач по факторизации, с которыми Мэйпл справляется на порядки быстрее M, я, пожалуй, озадачу ими разработчиков и прочих людей, приближённых к WRI.

 
 
 
 Re: Недостатки различных систем при факторизации полиномов
Сообщение06.06.2015, 00:37 
Залил на файлообменник: http://rghost.ru/8qmG6Mw84

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

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group