• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学 ›› 2023, Vol. 45 ›› Issue (04): 599-606.

• 高性能计算 • 上一篇    下一篇

基于模算术系数解析的稀疏插值算法

唐敏,戚妞妞,邓国强   

  1. (桂林电子科技大学数学与计算科学学院广西高校数据分析与计算重点实验室,广西 桂林 541004)
  • 收稿日期:2022-01-20 修回日期:2022-06-03 接受日期:2023-04-25 出版日期:2023-04-25 发布日期:2023-04-13
  • 基金资助:
    国家自然科学基金(11761024);广西科技基地和人才专项(AD18281024);桂林电子科技大学研究生优秀学位论文培养项目(2020YJSPYB02)

A sparse interpolation algorithm based on modular arithmetic coefficient parsing

TANG Min,QI Niu-niu,DENG Guo-qiang   

  1. (Guangxi Colleges and Universities Key Laboratory of Data Analysis and Computation,
    School of Mathematics & Computing Science,Guilin University of Electronic Technology,Guilin  541004,China)
  • Received:2022-01-20 Revised:2022-06-03 Accepted:2023-04-25 Online:2023-04-25 Published:2023-04-13

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

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

Abstract: Sparse multivariate polynomial interpolation is an effective strategy to reconstruct black box functions by using the sparse structure of polynomials and the given interpolation point information, which is widely used in science and engineering fields. The complexity of the traditional sparse interpolation algorithm based on Prony method is related to the number and degree of polynomial terms, and the efficiency is low when en-countering large-scale problems due to the execution of multiple high-order algebraic operations. Therefore, this paper proposes a sparse multivariate polynomial interpolation algorithm based on polynomial coefficient parsing. The core operation is to resolve the coefficients of univariate polynomials by using modular arithmetic, which avoids the solution of higher-order equations and finding the roots of higher order equation in the traditional method. In this method, black box polynomial is regarded as a univariate polynomial with one variable as the principal component, and the multivariate polynomial is recovered by parsing the values of the coefficient polynomials of the principal component at different interpolation point. Theoretical analysis and numerical experiments show that the algorithm is effective and feasible.

Key words: sparse multivariate polynomial interpolation, coefficient parsing, Ben-Or/Tiwari algorithm, modular arithmetic