Computing minimal interpolation bases
From MaRDI portal
iterative algorithmcomplexitypolynomial interpolationrational interpolationrecurrence relationbivariate interpolationpolynomial matrixorder basisHermite-Padé approximationM-Padé approximation
Complexity and performance of numerical algorithms (65Y20) Multidimensional problems (41A63) Numerical interpolation (65D05) Interpolation in approximation theory (41A05) Approximation by polynomials (41A10) Approximation by rational functions (41A20) Padé approximation (41A21) Matrices over function rings in one or more variables (15A54) Numerical aspects of recurrence relations (65Q30)
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 vectors of size it uses field operations, where is the exponent of matrix multiplication, and is the sum of the entries of the input shift , with . 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
Cites work
- 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?)
- A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants
- 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
- 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
- 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)- Symbolic computations of first integrals for polynomial vector fields
- Fast Computation of Minimal Interpolation Bases in Popov Form for Arbitrary Shifts
- A new algorithm for a recursive construction of the minimal interpolation space
- Minimal realizations interpolating first- and second-order information
- Deterministic computation of the characteristic polynomial in the time of matrix multiplication
- Computing Krylov iterates in the time of matrix multiplication
- Algorithms for simultaneous Hermite-Padé approximations
- Computing Riemann-Roch spaces via Puiseux expansions
- Computing syzygies in finite dimension using fast linear algebra
- Computing minimal nullspace bases
- Computing minimal interpolants in \(C^{1,1}(\mathbb{R}^d)\)
- Fast Kötter-Nielsen-Høholdt interpolation over skew polynomial rings and its application in coding theory
- Fast computation of approximant bases in canonical form
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)
