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

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

-d*d*l*l*q-b*b*l*l*q+2*d*f*j*l*q+2*b*f*h*l*q-f*f*j*j*q-b*b*j*j*q+2*b*d*h*j*q-f*f*h*h*q-d*d*h*h*q+b*b*j*j*o*o-2*b*d*h*j*o*o+d*d*h*h*o*o-2*b*b*j*l*n*o+2*b*d*h*l*n*o+2*b*f*h*j*n*o-2*d*f*h*h*n*o+2*b*d*j*l*m*o-2*d*d*h*l*m*o-2*b*f*j*j*m*o+2*d*f*h*j*m*o+b*b*l*l*n*n-2*b*f*h*l*n*n+f*f*h*h*n*n-2*b*d*l*l*m*n+2*b*f*j*l*m*n+2*d*f*h*l*m*n-2*f*f*h*j*m*n+d*d*l*l*m*m-2*d*f*j*l*m*m+f*f*j*j*m*m

Мне нужно как можно быстрее выполнить их все в программе на языке C. Если вы внимательно посмотрите на любую из этих формул, очевидно, что мы можем оптимизировать их для скорости вычислений. Например, в вставленном выше полиноме я сразу вижу термины -d * d * l * l * q, 2 * d * f * j * l * q и -f * f * j * j * q, чтобы я мог заменить их сумму на -q * square (d * lf * j). Я считаю, что здесь можно много чего сделать. Я не верю (но, возможно, ошибаюсь), что какой-либо компилятор сможет найти эту оптимизацию, а может быть, более продвинутую. Я пытался попросить Maxima (CAS) сделать это за меня, но ничего не вышло (так как я новичок с максимумами, я, возможно, пропустил волшебную команду). Итак, мой первый вопрос: какой инструмент / алгоритм мы можем использовать для оптимизации полиномиального выражения для скорости вычислений?

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

С наилучшими пожеланиями,

P.S. : этот пост имеет некоторые сходства с "компьютерная алгебра софт, чтобы минимизировать количество операций в наборе многочленов", однако ответы, данные в этом одном, указывают на программы CAS, а не на то, как мы можем использовать их для достижения нашей цели.


optimization performance algorithm polynomials computer-algebra-systems
person S. Piérard    schedule 30.01.2015    source источник
comment
Это такая основная и часто встречающаяся проблема, что я был бы очень удивлен, если бы большинство CAS не смогли сделать за вас хотя бы частичное упрощение.   -  person biziclop    schedule 30.01.2015
comment
Я скорее согласен с @biziclop и отмечу, что OP пишет: Я новичок с максимами. Возможно, частичное решение заключается в более близком знакомстве с максимумами.   -  person High Performance Mark    schedule 30.01.2015
comment
Помимо оптимизации вычисления одного полинома, можно изучить возможность использования общих подвыражений для нескольких полиномов в вашем наборе. Однако вы привели только один пример.   -  person hardmath    schedule 30.01.2015
comment
Спасибо за быстрые ответы. Я добавлю, что я, конечно, прочитал список доступных функций на maxima.sourceforge .net / docs / manual / maxima_14.html. Когда я говорю, что «ничего не вышло», я имею в виду, что у меня есть «фактор», «факторум», «фактоут» (даже если это нельзя рассматривать как автоматическое решение) и «комбинировать». Мои многочлены не могут быть выражены как произведение более простых многочленов. Но это не значит, что невозможно найти способ записать их так, чтобы вычисления стали быстрее.   -  person S. Piérard    schedule 30.01.2015
comment
@biziclop, я не ожидаю найти метод «write_polynomial_in_the_best_way_for_a_computer» в CAS, поскольку они совершенно не связаны со временем выполнения (которое, как я ожидаю, будет больше изучено лицами, связанными с компиляторами), и это не поможет при все математики. Я упомянул, что пробовал использовать максимумы, чтобы указать, что я был бы доволен почти оптимальным решением, даже если бы предпочел алгоритм, обеспечивающий оптимальное.   -  person S. Piérard    schedule 30.01.2015
comment
@hardmath: это правда, но разве поможет, если в посте будет куча таких уродливых выражений? Если да, то я могу привести некоторые другие, но это будет лишь частный случай общего вопроса. Я поместил один многочлен, чтобы читатель мог выполнить копипаст в имеющееся у него программное обеспечение и опробовать свою идею перед ответом.   -  person S. Piérard    schedule 30.01.2015
comment
Всегда ли проблема в форме sum(constant*a^x*b^y*c^z...)?   -  person biziclop    schedule 30.01.2015
comment
@biziclop, да. Мои многочлены могут быть любой степени (даже если я был бы доволен решением для многочленов степени 2, как в моем примере) и от многих переменных (у меня изначально была проблема с 17 переменными, поэтому я использую буквы от а до q для имен моих переменных). Предлагаемую вами форму всегда можно легко получить, например, используя «развернуть» в максимуме. Таким образом, это предположение не ограничивает общности и, конечно, может быть выполнено.   -  person S. Piérard    schedule 30.01.2015
comment
Я надеюсь, что два примера многочленов дадут читателям лучшее представление о диапазоне общих подвыражений. Могу помочь с их форматированием.   -  person hardmath    schedule 30.01.2015
comment
@hardmath: вот второй из моего набора. -ccllq-aallq + 2cejlq + 2aehlq-eejjq-aajjq + 2achjq-eehhq-cchhq + aajjoo-2achjoo + cchhoo-2aajlno + 2achlno + 2aehjno-2cehhno + 2acjmojlmojlmo +-2cchhoo-2cehlno + 2acjmojlmojlmo +-2cchhoo-2cehhno + 2chjmojlmojlmo + -2cchhoo + 2cehlmn-2eehjmn + ccllmm-2cejlmm + eejjmm   -  person S. Piérard    schedule 30.01.2015
comment
@hardmath: вот и третий из моего набора. -2cdllq-2abllq + 2cfjlq + 2dejlq + 2afhlq + 2behlq-2efjjq-2abjjq + 2adhjq + 2bchjq-2efhhq-2cdhhq + 2abjjoo-2adhjoo-2bchjoo + 2cdhhoo-4abjlno + 2adhlno + 2bchlno + 2afhjno + 2behjno-2cfhhno-2dehhno + 2adjlmo + 2bcjlmo -4cdhlmo-2afjjmo-2bejjmo + 2cfhjmo + 2dehjmo + 2abllnn-2afhlnn-2behlnn + 2efhhnn-2adllmn-2bcllmn + 2afjlmn + 2bejlmn + 2cfhlmn + 2dehlmn-2cefjllmmmm-2cefjllmmmm-2cefjllmmmm-2cefhjlmm   -  person S. Piérard    schedule 30.01.2015
comment
Я думаю, что эта проблема может быть NP-полной - она ​​похожа на минимальное количество сдвигов-и-сложений, необходимых для умножения на константу, которая, если я правильно помню из лекций в колледже, является NP-полной (но все же решаемой для небольших константы, поэтому компиляторы иногда проводят исчерпывающий тест). Так что вы можете просто написать жадный подход с обратным отслеживанием, и если он не работает, попробуйте найти дополнительные ограничения, которые позволят вам завершить тест раньше. (Я не уверен, что именно, но это действительно похоже на проблему удовлетворения ограничений, поэтому, возможно, вы можете использовать стандартную эвристику.)   -  person user541686    schedule 30.01.2015
comment
В зависимости от того, что вы используете, объем оптимизации, которую компилятор может сделать для чего-то вроде этого, может вас удивить. Если вы хотите попробовать свои силы в написании программы, которая делает такое же упрощение, как продвинутый компилятор, вам следует погуглить dags и common subexpressions.   -  person 500 - Internal Server Error    schedule 30.01.2015
comment
@ 500 - Внутренняя ошибка сервера, я согласен с вами в отношении определения общих подвыражений, но я не ожидал бы, что компиляторы будут выполнять расширенные функции по умолчанию, и поэтому много усилий будет приложено к типу оптимизаций, который я ищу. Причина в том, что они не могут изменять входную программу, не давая гарантии, что она во всех случаях будет делать то же самое, что и исходная. Но могут быть переполнения и потери значимости, а точность чисел с плавающей запятой ограничена. Фактически, это нарушит стандарты таких языков, как ISO C и C ++ (см. Параметр -fassociative-math в gcc).   -  person S. Piérard    schedule 01.02.2015
comment
@ 500 - внутренняя ошибка сервера, которая уже обсуждалась, например, в stackoverflow.com/questions/6430448/. Таким образом, можно сделать вывод, что программист несет ответственность за этот тип оптимизации, но не компилятор. Поэтому программистам для этого нужен инструмент.   -  person S. Piérard    schedule 01.02.2015

Ответы (1)


arrow_upward
0
arrow_downward

В качестве первой попытки я бы, наверное, попробовал жадный подход.

Итак, используя ваш первый пример, мы начнем с этого:

 -1*d*d*l*l*q
 -1*b*b*l*l*q
  2*d*f*j*l*q
  2*b*f*h*l*q
 -1*f*f*j*j*q
 ...

Теперь попробуйте найти в терминах наиболее повторяющуюся закономерность. Это q, который, к счастью, присутствует во всех них. Давайте удалим его, и у нас останется

 -1*d*d*l*l
 -1*b*b*l*l
  2*d*f*j*l
  2*b*f*h*l
 -1*f*f*j*j
 ...

Теперь проделайте то же самое еще раз, на этот раз мы получили l, и проблема разбивается на две подзадачи.

 -1*d*d*l
 -1*b*b*l
  2*d*f*j
  2*b*f*h
  ---------
 -1*f*f*j*j
 ...

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

 q*(l*<first subproblem>+<second subproblem>)

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

person biziclop    schedule 30.01.2015
comment
Мне нравится ваш подход, поскольку он отлично работает для одного полинома от одной переменной x. Например, a * x * x * x + b * x * x + c * x + d даст x * (x ** (x * a) + b) + c) + d, что кажется оптимальным. Однако легко найти очень простые примеры, в которых ваш ответ не является оптимальным. Например, a * d + b * d + c * d + b * x + c * x даст (a + b + c) * d + (b + c) * x, но мы можем найти a * d + (b + c) * (d + x), что требует на одну операцию меньше. Я ожидаю (на самом деле, я думаю), что неоптимальность вашего решения станет гораздо более важной с большим количеством терминов и переменных. - person S. Piérard; 01.02.2015
comment
@ S.Piérard Я подозреваю, что проблема в целом NP-сложная, так что, возможно, вы не можете ожидать многого от жадного алгоритма. Но, начиная с того же подхода, вы можете расширить его, чтобы сгенерировать множество деревьев выражений, и с помощью некоторой умной обрезки вы можете улучшить его. Очевидное улучшение, например, состоит в том, чтобы попробовать каждую перестановку для подзадачи ниже определенного размера. Или изучить 3 наиболее часто повторяемых термина, а не только 1. - person biziclop; 01.02.2015
comment
@ S.Piérard Прочитав комментарии, я понял, что вы, вероятно, смотрите на вычисления с плавающей запятой (я предполагал, что это была фиксированная точка), и в этом случае стоимость операции + не является незначительной. Это означает, что мне нужно переосмыслить алгоритм, который был направлен только на минимизацию умножений. - person biziclop; 01.02.2015
comment
Мой вопрос был общим. Даже если это выходит за рамки исходного вопроса, я могу сказать вам, что я пытался увидеть скорость сложения и умножения чисел с плавающей запятой с помощью процессора i7. В результате моего эксперимента, как и ожидалось, сложение обходится дешевле, чем умножение. Таким образом, ваш подход является хорошей отправной точкой даже для арифметики с плавающей запятой. - person S. Piérard; 01.02.2015