Faster sparse interpolation of straight-line programs
From MaRDI portal
Abstract: We give a new probabilistic algorithm for interpolating a "sparse" polynomial f given by a straight-line program. Our algorithm constructs an approximation f* of f, such that their difference probably has at most half the number of terms of f, then recurses on their difference. Our approach builds on previous work by Garg and Schost (2009), and Giesbrecht and Roche (2011), and is asymptotically more efficient in terms of the total cost of the probes required than previous methods, in many cases.
Recommendations
- Faster sparse multivariate polynomial interpolation of straight-line programs
- Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs
- Interpolation of polynomials given by straight-line programs
- Sparse interpolation over finite fields via low-order roots of unity
- Sparse polynomial interpolation over fields with large or zero characteristic
Cited in
(11)- Interpolation of polynomials given by straight-line programs
- Early termination in sparse interpolation algorithms
- Sparse polynomial interpolation based on derivatives
- Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs
- Faster sparse multivariate polynomial interpolation of straight-line programs
- Sparse interpolation over finite fields via low-order roots of unity
- On the evaluation of some sparse polynomials
- Randomized Interpolation and Approximation of Sparse Polynomials
- A sparse polynomial interpolation based on racing strategy
- Sparse polynomials in FLINT
- On exact division and divisibility testing for sparse polynomials
This page was built for publication: Faster sparse interpolation of straight-line programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5168460)
