A deterministic multivariate interpolation algorithm for small finite fields
Tóm tắt
We present a new multivariate interpolation algorithm over arbitrary fields which is primarily suited for small finite fields. Given function values at arbitrary t points, we show that it is possible to find an n-variable interpolating polynomial with at most t terms, using the number of field operations that is polynomial in t and n. The algorithm exploits the structure of the multivariate generalized Vandermonde matrix associated with the problem. Relative to the univariate interpolation, only the minimal degree selection of terms cannot be guaranteed and several term selection heuristics are investigated toward obtaining low-degree polynomials. The algorithms were applied to obtain Reed-Muller and related transforms for incompletely specified functions.
Từ khóa
#Interpolation #Galois fields #Polynomials #Discrete transforms #Decoding #Testing #Circuits #Lagrangian functionsTài liệu tham khảo
von zur gathen, 1999, Modern Computer Algebra
10.1007/BF01438278
knuth, 1980, The Art of Computer Programming second ed vol 2 Seminumerical Algorithms
10.1145/345542.345629
10.1109/TC.2002.1032628
10.1137/0220019
zilic, 1997, Towards Spectral Synthesis: Field Expansions for Partial Functions and Logic Modules for FPGAs
10.1145/62212.62241
10.1137/0219073
10.1137/0222046
10.1007/978-94-015-8169-1
zilic, 1998, Don't Care Minimization by Interpolation, Proc Int'l Workshop Logic Synthesis (IWLS '98), 353
10.1109/12.403717
10.1090/S0025-5718-1992-1122061-0
10.1109/SFCS.1998.743426
10.1109/12.24287
schapire, 1993, Learning Sparse Multivariate Polynomials over a Field with Queries and Counterexamples, Proc Symp Computational Learning Theory (COLT '93), 17
10.1109/VTEST.2000.843855
10.1049/ip-e.1987.0038
10.1007/s002110050304
zakrevskij, 1995, Minimum Polynomial Implementations of Systems of Incompletely Specified Boolean Functions, Proc Second Workshop Applications of the Reed-Muller Expansions in Circuit Design
10.1109/12.663768
10.1016/0304-3975(91)90157-W
10.1016/S0747-7171(08)80018-1