计算机工程与科学

作者：唐敏, 戚妞妞, 邓国强

单位：（桂林电子科技大学数学与计算科学学院广西高校数据分析与计算重点实验室，广西 桂林 541004）

关键词：稀疏多元多项式插值,系数解析,Ben-Or/Tiwari算法,模算术,

基金：国家自然科学基金（11761024）；广西科技基地和人才专项（AD18281024）；桂林电子科技大学研究生优秀学位论文培养项目（2020YJSPYB02）

稀疏多元多项式插值是利用多项式的稀疏结构及其给定的插值点信息重构黑盒函数的一种有效策略，被广泛应用于科学和工程领域。传统的基于Prony方法的稀疏插值算法，其复杂度与多项式项数和次数相关，遇到大规模问题时由于执行多个高阶代数运算而效率较低。提出一种新的求解稀疏多元多项式插值问题的算法，核心操作是利用模算术解析单变元多项式的系数，避免了传统方法必需的高阶方程组求解、高次方程求根等。该算法设定一变元为主元，将黑盒多元多项式视为该主元的单变元多项式，通过解析主元的系数多项式在不同插值点处的函数值，进而重构这些系数多项式以恢复整个多元多项式。理论分析和数值实验表明了算法的有效性和可行性。

来源：2023年第4期

《计算机工程与科学》期刊编辑部

查看计算机工程与科学杂志2023年第4期