Как реализовать схему Хорнера для многомерных полиномов? - PullRequest
Новая
       11

Как реализовать схему Хорнера для многомерных полиномов?

4 голосов
/ 17 июня 2010

Фон

Мне нужно решить многочлены от нескольких переменных, используя Схема Хорнера в Fortran90 / 95.Основной причиной для этого является повышенная эффективность и точность, возникающая при использовании схемы Хорнера для оценки полиномов.

В настоящее время у меня есть реализация схемы Хорнера для одномерных / полиномов с одной переменной.Однако разработка функции для оценки многомерных многочленов с использованием схемы Хорнера оказывается за пределами моего понимания.

Примером двумерного многочлена будет: 12x ^ 2y ^ 2 + 8x ^ 2y + 6xy ^ 2 + 4xy+ 2x + 2y, которые будут разложены на x (x (y (12y + 8)) + y (6y + 4) +2) + 2y, а затем оценены для конкретных значений x & y.

Исследования

Я провел исследование и обнаружил ряд статей, таких как:
staff.ustc.edu.cn/~xinmao/ISSAC05/pages/bulletins/articles/147/hornercorrected.pdf
citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.40.8637&rep=rep1&type=pdf
www.is.titech.ac.jp/~kojima/articles/B-433.pdf

Задача

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

Что касаетсяЯ могу сказать, что основная стратегия состоит в том, чтобы превратить многомерный многочлен в отдельные одномерные многочлены и вычислить его таким образом.

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

Ответы [ 2 ]

6 голосов
/ 15 июля 2010

Для двух переменных можно хранить коэффициенты полинома в матрице ранга = 2 K(n+1,n+1), где n - порядок полинома.Затем соблюдайте следующую схему (в псевдокоде) 

p(x,y) =     (K(1,1)+y*(K(1,2)+y*(K(1,3)+...y*K(1,n+1))) +
           x*(K(2,1)+y*(K(2,2)+y*(K(2,3)+...y*K(2,n+1))) +
         x^2*(K(3,1)+y*(K(3,2)+y*(K(3,3)+...y*K(3,n+1))) +
         ...
         x^n*(K(n+1,1)+y*(K(n+1,2)+y*(K(n+1,3)+...y*K(n+1,n+1)))

Каждая строка представляет собой схему отдельного Гомера в терминах y, а все вместе - схема окончательного Гомера в терминах x.

Для кодирования на FORTRAN или любом другом языке создайте промежуточный вектор z(n+1) такой, что 

z(i) = homers(y,K(i,1:n+1))

и 

p = homers(x,z(1:n+1))

, где homers(value,vector) - реализацияоценка одной переменной с полиномиальными коэффициентами, хранящимися в vector.

0 голосов
/ 08 ноября 2018

Я реализовал это в Python: multivar_horner

Вы можете посмотреть на используемый там подход и перенести его на Фортран.

ПРИМЕЧАНИЕ. Насколько мне известно, не существует известного алгоритма для нахождения оптимальной разложенности множителей многомерного полинома. Лучшее, что можно сделать, - это использовать умную эвристику, чтобы найти «хорошие» факторизации. Я реализовал жадную эвристику, подобную описанной в статье « Жадные алгоритмы для оптимизации многомерных схем Хорнера ».

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

...