fortran - 如何实现多元多项式的霍纳方案？

Question

背景

我需要使用 Horner's scheme 解决多个变量中的多项式在 Fortran90/95 中。这样做的主要原因是使用霍纳的方案来评估多项式时会提高效率和准确性。

我目前有一个霍纳的单变量/单变量多项式方案的实现。然而，事实证明，使用霍纳的方案开发一个函数来评估多元多项式已经超出了我的范围。

An example bivariate polynomial would be: 12x^2y^2+8x^2y+6xy^2+4xy+2x+2y which would factorised to x(x(y(12y+8))+y(6y+4)+2)+2y and then evaluated for particular values of 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 中实现，我将不胜感激。

Answer 1

对于两个变量，可以将多项式系数存储在 rank=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 中.