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

Question

背景

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

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

一个示例二元多项式为：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/horner Corrected.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) 是使用存储在向量中的多项式系数实现单变量评估。