检索结果-内蒙古大学图书馆

44th ACM International Symposium on Symbolic and Algebraic Computation (ISSAC)

作者： Huang, Qiao-Long Univ Waterloo Cheriton Sch Comp Sci Waterloo ON Canada

ISBN: (纸本)9781450360845

In this paper, we propose a new interpolation algorithm for a sparse multivariate polynomial represented by a straight-line program (SLP). Our algorithm is a Monte Carlo randomized algorithm and works over fields with large or zero characteristic. Let f be an n-variate polynomial given by a straight-line program, which has a degree bound D and a term bound T. For fields of large characteristic, the bit complexity of our algorithm is linear in n, T, log D in the Soft-Oh sense. Since n, T, log D are factors of the size of f, our algorithm is optimal in n, T and log D in the Soft-Oh sense. For fields of characteristic 0, the arithmetic complexity of our algorithm is also linear in n, T, log D in the Soft-Oh sense. But the arithmetic complexity does not account for coefficient growth and therefore might be a poor reflection of reality.

关键词： sparse polynomial interpolation derivative straight-line program randomized Kronecker substitution

来源：评论

学校读者我要写书评

暂无评论

sparse polynomial interpolation with Finitely Many Values for the Coefficients 1

引用

19th International Workshop on Computer Algebra in Scientific Computing (CASC)

作者： Huang, Qiao-Long Gao, Xiao-Shan Chinese Acad Sci Acad Math & Syst Sci UCAS KLMM Beijing 100190 Peoples R China

ISBN: (数字)9783319663203

ISBN: (纸本)9783319663203;9783319663197

In this paper, we give new sparse interpolation algorithms for black box polynomial f whose coefficients are from a finite set. In the univariate case, we recover f from one evaluation f (/3) for a sufficiently large number /3. In the multivariate case, we introduce the modified Kronecker substitution to reduce the interpolation of a multivariate polynomial to that of the univariate case. Both algorithms have polynomial bit -size complexity.

关键词： sparse polynomial interpolation Modified Kronecker substitution polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Model Reduction Using sparse polynomial interpolation for the Incompressible Navier-Stokes Equations

引用

VIETNAM JOURNAL OF MATHEMATICS 2023年第1期51卷 199-211页

作者： Hess, Martin Rozza, Gianluigi SISSA MathLab Via Bonomea 265 I-34136 Trieste Italy

This work investigates the use of sparse polynomial interpolation as a model order reduction method for the parametrized incompressible Navier-Stokes equations. Numerical results are presented underscoring the validity of sparse polynomial approximations and comparing with established reduced basis techniques. Two numerical models serve to assess the accuracy of the reduced order models (ROMs), in particular parametric nonlinearities arising from curved geometries are investigated in detail. Besides the accuracy of the ROMs, other important features of the method are covered, such as offline-online splitting, run time and ease of implementation. The findings provide a clear indication that sparse polynomial interpolation is a valid instrument in the toolbox of ROM methods.

关键词： Model order reduction sparse polynomial interpolation Navier-stokes equations Parametric systems Curved geometries 76Bxx 65Mxx

来源：评论

学校读者我要写书评

暂无评论

Revisit sparse polynomial interpolation Based on Randomized Kronecker Substitution 1

引用

21st International Workshop on Computer Algebra in Scientific Computing (CASC)

作者： Huang, Qiao-Long Gao, Xiao-Shan Chinese Acad Sci Acad Math & Syst Sci UCAS KLMM Beijing Peoples R China Univ Waterloo Cheriton Sch Comp Sci Waterloo ON Canada

ISBN: (数字)9783030268312

ISBN: (纸本)9783030268312;9783030268305

In this paper, a new reduction based interpolation algorithm for general black-box multivariate polynomials over finite fields is given. The method is based on two main ingredients. A new Monte Carlo method is given to reduce the black-box multivariate polynomial interpolation problem to the black-box univariate polynomial interpolation problem over any ring. The reduction algorithm leads to multivariate interpolation algorithms with better or the same complexities in most cases when combining with various univariate interpolation algorithms. A modified univariate Ben-Or and Tiwari algorithm over the finite field is proposed, which has better total complexity than the Lagrange interpolation algorithm. Combining our reduction method and the modified univariate Ben-Or and Tiwari algorithm, we give a Monte Carlo multivariate interpolation algorithm, which has better total complexity in most cases for sparse interpolation of black-box polynomial over finite fields.

关键词： Randomized Kronecker substitution sparse polynomial interpolation Black-box Finite field Monte Carlo algorithm

来源：评论

学校读者我要写书评

暂无评论

Surrogate model based on hierarchical sparse polynomial interpolation for the phosphate ore dissolution

引用

COMPUTERS & CHEMICAL ENGINEERING 2023年 173卷

作者： Elmisaoui, Sanae Benjelloun, Saad Chkifa, Moulay Abdellah Latifi, Abderrazak M. Mohammed VI Polytech Univ Lot 990 Hay Moulay Rachid Benguerir 43150 Morocco Univ Lorraine Lab React & Genie Proc CNRS ENS 1 Rue GrandvilleBP20451 F-54001 Nancy France Mohammed V Univ Mohammadia Sch Engineers POB 765 Rabat Morocco

This paper deals with the development of accurate surrogate models for first-principles models constructed for the dissolution of phosphate ore in a phosphoric acid solution. The surrogate models are based on sparse multivariate polynomial interpolation. The main goal is to reduce the computational time of the first-principles model while preserving its properties, namely the outputs' monotonicity and positivity. The temporal profiles of the concentrations of the different components involved in the liquid phase and in the ore particles, the particle size, and the thickness of the liquid film surrounding the particles are approximated by the surrogate models. The inputs of the models are the particle size distribution, the initial acid concentration, and the hydrodynamic conditions. A design of experiments method is used to produce the required sampling points for the surrogate models and several simulations are conducted in the MATLAB environment. A final comparison of the proposed surrogate models' performance demonstrates high efficiency, both in terms of accuracy as well as computation time, and highlights the strength of the introduced surrogate modeling methodology.

关键词： Dissolution of phosphate ore particles Shrinking core model sparse polynomial interpolation Phosphoric acid Surrogate model

来源：评论

学校读者我要写书评

暂无评论

Fast interpolation of multivariate polynomials with sparse exponents

引用

JOURNAL OF COMPLEXITY 2025年 87卷

作者： van der Hoeven, Joris Lecerf, Gregoire CNRS Ecole Polytech Inst Polytech Paris Lab Informat Ecole Polytech LIXUMR 7161 Batiment Alan TuringCS350031 Rue Honore Estienne F-91120 Palaiseau France

Consider a sparse multivariate polynomial f with integer coefficients. Assume that f is represented as a "modular black box polynomial", e.g. via an algorithm to evaluate fat arbitrary integer points, modulo arbitrary positive integers. The problem of sparse interpolation is to recover fin its usual sparse representation, as a sum of coefficients times monomials. For the first time we present a quasi-optimal algorithm for this task in term of the product of the number of terms of f by the maximum of the bit-size of the terms of f. (c) 2024 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： sparse polynomial interpolation Computer algebra Complexity Algorithm

来源：评论

学校读者我要写书评

暂无评论

Newton-Hensel interpolation lifting

引用

FOUNDATIONS OF COMPUTATIONAL MATHEMATICS 2006年第1期6卷 81-120页

作者： Avendaño, M Krick, T Pacetti, A Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Matemat RA-1428 Buenos Aires DF Argentina

The main result of this paper is a new version of Newton-Hensel lifting that relates to interpolation questions. It allows one to lift polynomials in Z[x] from information modulo a prime number p not equal 2 to a power p(k) for any k, and its originality is that it is a mixed version that not only lifts the coefficients of the polynomial but also its exponents. We show that this result corresponds exactly to a Newton-Hensel lifting of a system of 2t generalized equations in 2t unknowns in the ring of p-adic integers Z(p). Finally, we apply our results to sparse polynomial interpolation in Z[x].

关键词： Newton-Hensel lifting p-adic integers sparse polynomial interpolation

来源：评论

学校读者我要写书评

暂无评论

sparse interpolation With Errors in Chebyshev Basis Beyond Redundant-Block Decoding

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2021年第1期67卷 232-243页

作者： Kaltofen, Erich L. Yang, Zhi-Hong North Carolina State Univ Dept Math Raleigh NC 27695 USA Duke Univ Dept Comp Sci Durham NC 27708 USA

We present sparse interpolation algorithms for recovering a polynomial with = 222. Ourmethod shows how to correct 2 errors in a block of 4B points for standard basis and how to correct 1 error in a block of 3B points ... 详细信息

We present sparse interpolation algorithms for recovering a polynomial with <= B terms from N evaluations at distinct values for the variable when <= E of the evaluations can be erroneous. Our algorithms perform exact arithmetic in the field of scalars K and the terms can be standard powers of the variable or Chebyshev polynomials, in which case the characteristic of K is not equal 2. Our algorithms return a list of valid sparse interpolants for the N support points and run in polynomial-time. For standard power basis our algorithms sample at N = [4/3 E + 2]B points, which are fewer points than N = 2(E + 1)B - 1 given by Kaltofen and Pernet in 2014. For Chebyshev basis our algorithms sample at N = [3/2 E+2]B points, which are also fewer than the number of points required by the algorithm given by Arnold and Kaltofen in 2015, which has N = 74[E/13 +1] for B = 3a nd E >= 222. Ourmethod shows how to correct 2 errors in a block of 4B points for standard basis and how to correct 1 error in a block of 3B points for Chebyshev Basis.

关键词： sparse polynomial interpolation error correction black box polynomial list-decoding

来源：评论

学校读者我要写书评

暂无评论

Error-Correcting sparse interpolation in the Chebyshev Basis 15

Error-Correcting Sparse Interpolation in the Chebyshev Basis

引用

ACM International Symposium on Symbolic and Algebraic Computation (ISSAC)

作者： Arnold, Andrew Kaltofen, Erich L. Univ Waterloo Symbol Computat Grp Waterloo ON Canada North Carolina State Univ Dept Math Raleigh NC 27695 USA

ISBN: (纸本)9781450334358

We present an error-correcting interpolation algorithm for a univariate black-box polynomial that has a sparse representation using Chebyshev polynomials as a term basis. Our algorithm assumes that an upper bound on the number of erroneous evaluations is given as input. Our method is a generalization of the algorithm by Lakshman and Saunders [SIAM J. Comput., vol. 24 (1995)] for interpolating sparse Chebyshev polynomials, as well as techniques in error-correcting sparse interpolation in the usual basis of consecutive powers of the variable due to Comer, Kaltofen, and Pernet [Proc. ISSAC 2012, 2014]. We prove the correctness of our list-decoder-based algorithm with a Descartes-rule-of-signs-like property for sparse polynomials in the Chebyshev basis. We show that this list decoder requires fewer evaluations than a naive majority-rule block decoder in the case when the interpolant is known to have at most two terms. We also give a new algorithm that reduces sparse interpolation in the Chebyshev basis to that in the power basis, thus making the many techniques for the sparse interpolation in the power basis, for instance, supersparse (lacunary) interpolation over large finite fields, available to interpolation in the Chebyshev basis. Furthermore, we can customize the randomized early termination algorithms from Kaltofen and Lee [J. Symb. Comput., vol. 36 (2003)] to our new approach.

关键词： sparse polynomial interpolation Prony's algorithm Chebyshev polynomials Descartes' rule of signs orthogonal basis error-correcting code

来源：评论

学校读者我要写书评

暂无评论

A fast parallel sparse polynomial GCD algorithm

引用

JOURNAL OF SYMBOLIC COMPUTATION 2021年 105卷 28-63页

作者： Hu, Jiaxiong Monagen, Michael Simon Fraser Univ Dept Math Burnaby BC Canada

We present a parallel GCD algorithm for sparse multivariate polynomials with integer coefficients. The algorithm combines a Kronecker substitution with a Ben-Or/Tiwari sparse interpolation modulo a smooth prime to determine the support of the GCD. We have implemented our algorithm in C for primes of various sizes and have parallelized it using Cilk C. We compare our implementation with Maple and Magma's serial implementations of Zippel's GCD algorithm. (C) 2020 Elsevier Ltd. All rights reserved.

关键词： polynomial GCD computation sparse polynomial interpolation Modular algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：