Faster Deterministic Sparse Interpolation Algorithms for Straight-Line Program Multivariate Polynomials.

Qiao-Long Huang, Xiao-Shan Gao2017

TL;DR

This paper introduces new deterministic and Monte Carlo algorithms for interpolating sparse multivariate polynomials represented by straight-line programs (SLPs). These algorithms offer improved computational complexity, particularly for sparse polynomials, and are the first to achieve linear complexity in the number of terms for Monte Carlo methods.

What Problem Does This Paper Address?

Interpolating sparse multivariate polynomials is a fundamental problem in computer algebra with applications in various fields. A common way to represent such polynomials is through straight-line programs (SLPs), which are sequences of arithmetic operations. The challenge lies in efficiently reconstructing the polynomial from its SLP representation, especially when the polynomial is sparse (has few non-zero terms). Existing methods often struggle with either computational complexity or the ability to handle general rings. This paper aims to develop faster and more general algorithms for this interpolation problem, focusing on both deterministic and probabilistic approaches.

Methods

The authors propose several novel techniques:

  • A Criterion for Term Testing: A method to determine if a specific term belongs to a polynomial, crucial for identifying and isolating terms.
  • Deterministic "Ok" Prime Finding: A deterministic algorithm to find a prime number p such that at least half of the polynomial's terms do not "collide" when the polynomial is evaluated modulo x^p - 1. This is a key step for reducing multivariate interpolation to univariate interpolation.
  • New Kronecker Substitution: A modified Kronecker substitution technique that reduces the degree of the intermediate univariate polynomials, leading to better complexity compared to previous methods. This is a core innovation for handling multivariate polynomials.
  • Deterministic Interpolation Algorithm: This algorithm leverages the "ok" prime finding and the new Kronecker substitution to achieve a deterministic solution with improved complexity, particularly quadratic in the number of variables n and terms T.
  • Monte Carlo Interpolation Algorithms: Two probabilistic algorithms are presented. The first offers improved complexity over existing Monte Carlo methods. The second, designed for finite fields, achieves linear complexity in n and T, making it optimal in that sense.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm development and analysis, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • The "Ok" Prime is Crucial: The concept of an "ok" prime, where a significant portion of terms don't collide, is central to making the reduction from multivariate to univariate interpolation efficient and deterministic.
  • Kronecker Substitution Refinement: The paper's novel Kronecker substitution is a key algorithmic improvement, reducing the degree of intermediate polynomials and thus the overall computational cost.
  • Linear Complexity for Monte Carlo: Achieving linear complexity in nT for Monte Carlo interpolation is a significant theoretical advancement, suggesting near-optimal performance for sparse polynomials.
  • Bridging Deterministic and Probabilistic: The paper presents both deterministic and probabilistic algorithms, offering a spectrum of solutions depending on the application's requirements for certainty and speed.

Key Results

  • Deterministic Algorithm: Achieves a complexity of O~(Ln²T² log² D + LnT log³ D) arithmetic operations, which is better than existing deterministic algorithms in most cases, especially for sparse polynomials.
  • Monte Carlo Algorithms:
    • The first Monte Carlo algorithm has a complexity of O~(LnT(log³ D + log D log μ⁻¹)) with high probability.
  • The second Monte Carlo algorithm (for finite fields) has a bit complexity of O~(LnT log² D(log D + log q) log μ⁻¹) and is linear and optimal in n and T in the "Soft-Oh" sense.

Limitations and Future Work

  • Soft-Oh Complexity: While the algorithms are efficient in the "Soft-Oh" sense (ignoring polylogarithmic factors), the actual performance might still be affected by these factors, as suggested by the experimental results.
  • Experimental Validation: The paper includes experimental results that generally align with theoretical bounds but notes that some logarithm factors can significantly impact running time. Further empirical studies could explore these impacts more deeply.
  • General Computable Rings: The algorithms are designed to work over general computable rings, which is a strength, but specific performance characteristics on different ring types are not deeply explored.
  • Future Work: The paper implicitly suggests exploring further optimizations and applications of these algorithms, particularly in the context of finite fields and for even larger or more complex polynomial structures.

Summary updated

BibTeX
@misc{huang2017faster,
  author = {Qiao-Long Huang and Xiao-Shan Gao},
  title = {{Faster Deterministic Sparse Interpolation Algorithms for Straight-Line Program Multivariate Polynomials.}},
  year = {2017},
}
Figure