Polynomial evaluation and interpolation on special sets of points
From MaRDI portal
Publication:2387413
DOI10.1016/j.jco.2004.09.009zbMath1101.68039OpenAlexW2042513324WikidataQ107417338 ScholiaQ107417338MaRDI QIDQ2387413
Publication date: 2 September 2005
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jco.2004.09.009
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Symbolic computation and algebraic computation (68W30) Polynomials, factorization in commutative rings (13P05)
Related Items
Fast Lagrange-Newton transformations ⋮ Lifting and recombination techniques for absolute factorization ⋮ Algebraic diagonals and walks: algorithms, bounds, complexity ⋮ Deterministic root finding over finite fields using Graeffe transforms ⋮ On the complexity of integer matrix multiplication ⋮ On the complexity exponent of polynomial system solving ⋮ On the complexity of the generalized MinRank problem ⋮ Fast computation of the \(N\)-th term of a \(q\)-holonomic sequence and applications ⋮ On Matrices With Displacement Structure: Generalized Operators and Faster Algorithms ⋮ An algorithm to recognize regular singular Mahler systems ⋮ Fast systematic encoding of multiplicity codes ⋮ Multi-point evaluation in higher dimensions ⋮ Genus 2 point counting over prime fields ⋮ Efficient computation of Cantor's division polynomials of hyperelliptic curves over finite fields ⋮ Polynomial root finding over local rings and application to error correcting codes ⋮ An efficient algorithm for multivariate Maclaurin-Newton transformation ⋮ Fast transforms over finite fields of characteristic two ⋮ Inverse linear difference operators ⋮ Verification protocols with sub-linear communication for polynomial matrix operations ⋮ Essentially optimal computation of the inverse of generic polynomial matrices ⋮ Asymptotically fast polynomial matrix algorithms for multivariable systems ⋮ On the complexities of multipoint evaluation and interpolation ⋮ Newton's method and FFT trading ⋮ Fast algorithms for multivariate interpolation and evaluation at special points ⋮ Basis-Independent Polynomial Division Algorithm Applied to Division in Lagrange and Bernstein Basis ⋮ Fast convolutions meet Montgomery ⋮ Fast multivariate multi-point evaluation revisited ⋮ Fast computation of approximant bases in canonical form ⋮ Fast Hermite interpolation and evaluation over finite fields of characteristic two ⋮ On the Differential and Full Algebraic Complexities of Operator Matrices Transformations ⋮ Deformation techniques for sparse systems ⋮ Truncation bounds for differentially finite series ⋮ On the complexity of skew arithmetic
Uses Software
Cites Work
- A uniform approach for Hermite Padé and simultaneous Padé approximants and their matrix-type generalizations
- Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm
- On fast multiplication of polynomials over arbitrary algebras
- Hypergeometric solutions of linear recurrences with polynomial coefficients
- A fast method for interpolation using preconditioning
- Fast modular transforms
- Fast multiplication of polynomials over fields of characteristic 2
- Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey
- The middle product algorithm. I: Speeding up the division and square root of power series
- Greatest factorial factorization and symbolic summation
- Fast multiplication of large numbers
- Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
- Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm
- Evaluating Polynomials at Fixed Sets of Points
- A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants
- On polynomial interpolation at the points of a geometric progression
- On the Foundations of Combinatorial Theory IV Finite Vector Spaces and Eulerian Generating Functions
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
