Computing minimal interpolation bases

DOI10.1016/J.JSC.2016.11.015MaRDI QIDQ2628323zbMATH OpenOpenAlexFDO

Authors Claude-Pierre Jeannerod, Vincent Neiger, Éric Schost, Gilles Villard

Publication date 1 June 2017

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.03503

zbMATH Keywords

bivariate interpolationcomplexityHermite-Padé approximationiterative algorithmM-Padé approximationorder basispolynomial interpolationpolynomial matrixrational interpolationrecurrence relation

Mathematics Subject Classification ID

Matrices over function rings in one or more variables (15A54) Interpolation in approximation theory (41A05) Approximation by polynomials (41A10) Approximation by rational functions (41A20) Padé approximation (41A21) Multidimensional problems (41A63) Numerical interpolation (65D05) Numerical aspects of recurrence relations (65Q30) Complexity and performance of numerical algorithms (65Y20)

Abstract: We consider the problem of computing univariate polynomial matrices over a field that represent minimal solution bases for a general interpolation problem, some forms of which are the vector M-Pad'e approximation problem in [Van Barel and Bultheel, Numerical Algorithms 3, 1992] and the rational interpolation problem in [Beckermann and Labahn, SIAM J. Matrix Anal. Appl. 22, 2000]. Particular instances of this problem include the bivariate interpolation steps of Guruswami-Sudan hard-decision and K"otter-Vardy soft-decision decodings of Reed-Solomon codes, the multivariate interpolation step of list-decoding of folded Reed-Solomon codes, and Hermite-Pad'e approximation. In the mentioned references, the problem is solved using iterative algorithms based on recurrence relations. Here, we discuss a fast, divide-and-conquer version of this recurrence, taking advantage of fast matrix computations over the scalars and over the polynomials. This new algorithm is deterministic, and for computing shifted minimal bases of relations between $m$ vectors of size $sigma$ it uses $O(m^{omega-1}(sigma+|s|))$ field operations, where $omega$ is the exponent of matrix multiplication, and $|s|$ is the sum of the entries of the input shift $s$, with $min(s)=0$. This complexity bound improves in particular on earlier algorithms in the case of bivariate interpolation for soft decoding, while matching fastest existing algorithms for simultaneous Hermite-Pad'e approximation.

Recommendations

• Fast Computation of Minimal Interpolation Bases in Popov Form for Arbitrary Shifts
• scientific article; zbMATH DE number 2081134
• Interpolation in list decoding of Reed-Solomon codes
• On the scalar rational interpolation problem
• Gröbner basis solutions of constrained interpolation problems

Cites work

• A characterization of parenthesis languages
• A displacement approach to efficient decoding of algebraic-geometric codes
• A general module theoretic framework for vector M-Padé and matrix rational interpolation
• A new method for computing a column reduced polynomial matrix
• A recursive algorithm for Padé-Hermite approximations
• A reliable method for computing M-Padé approximants on arbitrary staircases
• A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants
• Algebraic soft- and hard-decision decoding of generalized Reed-Solomon and cyclic codes
• Algebraic soft-decision decoding of reed-solomon codes
• An Interpolation Procedure for List Decoding Reed–Solomon Codes Based on Generalized Key Equations
• Approximate common divisors via lattices
• Computing minimal nullspace bases
• Decoding of Reed Solomon codes beyond the error-correction bound
• Efficient algorithms for order basis computation
• Efficient decoding of Reed-Solomon codes beyond half the minimum distance
• Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy
• Fast algorithms for the characteristic polynomial
• Fast computation of continued fraction expansions.
• Fast generalized minimum-distance decoding of algebraic-geometry and Reed-Solomon codes
• Fast projection methods for minimal design problems in linear system theory
• Fast solution of toeplitz systems of equations and computation of Padé approximants
• Faster Algorithms for Multivariate Interpolation With Multiplicities and Simultaneous Polynomial Approximations
• Fraction-free computation of matrix rational interpolants and matrix GCDs
• scientific article; zbMATH DE number 1970438 (Why is no real title available?)
• scientific article; zbMATH DE number 1461545 (Why is no real title available?)
• scientific article; zbMATH DE number 2151192 (Why is no real title available?)
• scientific article; zbMATH DE number 3270061 (Why is no real title available?)
• Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding
• Improved decoding of Reed-Solomon and algebraic-geometry codes
• Key equations for list decoding of Reed-Solomon codes and how to solve them
• Linear Diophantine Equations Over Polynomials and Soft Decoding of Reed–Solomon Codes
• List decoding of Reed-Solomon codes from a Gröbner basis perspective
• Matrix multiplication via arithmetic progressions
• Modern computer algebra
• Normal forms for general polynomial matrices
• On fast multiplication of polynomials over arbitrary algebras
• On lattice reduction for polynomial matrices
• Powers of tensors and fast matrix multiplication
• Recurrence relations in Padé-Hermite approximation
• Simplified High-Speed High-Distance List Decoding for Alternant Codes
• Solving structured linear systems with large displacement rank
• The computation of non-perfect Padé-Hermite approximants
• Triangular \(x\)-basis decompositions and derandomization of linear algebra algorithms over \(K[x]\)

Cited in

(13)

• Computing Riemann-Roch spaces via Puiseux expansions
• Computing syzygies in finite dimension using fast linear algebra
• Symbolic computations of first integrals for polynomial vector fields
• Algorithms for simultaneous Hermite-Padé approximations
• Deterministic computation of the characteristic polynomial in the time of matrix multiplication
• Fast computation of approximant bases in canonical form
• Fast Computation of Minimal Interpolation Bases in Popov Form for Arbitrary Shifts
• Minimal realizations interpolating first- and second-order information
• Computing minimal interpolants in \(C^{1,1}(\mathbb{R}^d)\)
• Computing minimal nullspace bases
• Fast Kötter-Nielsen-Høholdt interpolation over skew polynomial rings and its application in coding theory
• Computing Krylov iterates in the time of matrix multiplication
• A new algorithm for a recursive construction of the minimal interpolation space

This page was built for publication: Computing minimal interpolation bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2628323)