首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Fast amortized multi-point evaluation
Institution:1. CNRS (UMI 3069, PIMS), Department of Mathematics, Simon Fraser University, 8888 University Drive, Burnaby, British Columbia, V5A 1S6, Canada;2. CNRS, École polytechnique, Institut Polytechnique de Paris, Laboratoire d''Informatique de l''École Polytechnique (LIX, UMR 7161), Bâtiment Alan Turing, CS35003, 1, rue Honoré d''Estienne d''Orves, 91120 Palaiseau, France;1. Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Altenbergerstr. 69, 4040 Linz, Austria;2. Institut für Finanzmathematik und Angewandte Zahlentheorie, Johannes Kepler Universität Linz, Altenbergerstr. 69, 4040 Linz, Austria;1. University of South Carolina, United States of America;2. Steklov Institute of Mathematics, Russia;3. Lomonosov Moscow State University, Russia;4. Moscow Center for Fundamental and Applied Mathematics, Russia;5. Faculty of Mathematics, 09107 Chemnitz, Germany
Abstract:The efficient evaluation of multivariate polynomials at many points is an important operation for polynomial system solving. Kedlaya and Umans have recently devised a theoretically efficient algorithm for this task when the coefficients are integers or when they lie in a finite field. In this paper, we assume that the set of points where we need to evaluate is fixed and “sufficiently generic”. Under these restrictions, we present a quasi-optimal algorithm for multi-point evaluation over general fields. We also present a quasi-optimal algorithm for the opposite interpolation task.
Keywords:Complexity  Algorithm  Computer algebra  Multivariate polynomial  Evaluation  Interpolation
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号