测试一组高次多项式,其系数在 {-1,0,1}

计算科学 数值分析 并行计算 多项式
2021-12-09 06:56:43

我正在寻找实现以下算法的最佳方法:考虑所有具有高次数(例如,30 次)的多项式的集合,其系数范围从给定的一组值(例如,{-1,0,1} )。对于这个集合的任何多项式,我想应用一些测试(比如,验证它的所有根是否都是实数)。如果多项式在测试中通过,我想打印它及其根(数值计算)。如果没有通过,什么也不做。(实际上,我的测试比这要复杂一些,但这足以澄清我的观点)。

在上面的例子中,我不需要评估集合中每个多项式的根来验证它的根是否都是实数,因为我可以使用Sturm theorem或一些数值算法来隔离根区间,以及其他中间过滤器测试,如笛卡尔的符号规则等。只有当多项式通过所有这些测试时——我确信它的所有根都是实数——我才想打印多项式及其根。

问题如下:由于度数非常高,要测试的多项式太多。即使只运行列表,这也需要很长的计算时间。因此,我想知道实现代码的最佳语言是什么,以及生成运行测试的多项式列表的最佳方法是什么。目前,我通过嵌套循环结构(每个多项式系数一个 for 循环)在 Maple 上实现了代码,但我相信有一种更聪明的方法可以做到这一点。也许某种并行化循环的方式是可取的。

我不会掌握任何编程语言,但我可以学得很快。我对 Maple、Mathematica 很满意,而且我正在学习 SageMath。我也了解一点 Python,我认为 Cython 是实现代码的好主意,但我不确定......任何帮助都将非常受欢迎,我提前感谢大家。

1个回答

您可以使用回溯来生成多项式。这几乎可以用您选择的任何语言并行化。您可能还想从脚本中调用FLINT 库中的 Sturm 序列查找器以提高速度。