RANDOMIZED INTERPOLATION AND APPROXIMATION OF SPARSE POLYNOMIALS

作     者：MANSOUR, Y 

作者机构：IBM CORPTHOMAS J WATSON RES CTRYORKTOWN HTSNY 10598 HARVARD UNIVAIKEN COMPUTAT LABCAMBRIDGEMA 02138 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1995年第24卷第2期

页      面：357-368页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：POLYNOMIAL INTERPOLATION RANDOMIZED ALGORITHMS APPROXIMATION HARMONIC ANALYSIS 

摘      要：We present a randomized algorithm that interpolates a sparse polynomial in polynomial time in the bit complexity model. The algorithm can be also applied to approximate polynomials that can be approximated by sparse polynomials (the approximation is in the L(2) norm).