Computing minimal interpolation bases. (November 2017)

• Record Type: Journal Article
• Authors: Jeannerod, Claude-Pierre; Neiger, Vincent; Schost, Éric; Villard, Gilles
• Is Part Of: Journal of symbolic computation. Volume 83(2017)
• Page Start: 272
• Page End: 314
• Publication Date: 2017-11
• Subjects: M-Padé approximation -- Hermite–Padé approximation -- Polynomial interpolation -- Order basis -- Polynomial matrix; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2016.11.015
• Languages: English
• ISSNs: 0747-7171

Abstract

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é approximation problem inVan Barel and Bultheel (1992) and the rational interpolation problem inBeckermann and Labahn (2000) . Particular instances of this problem include the bivariate interpolation steps of Guruswami–Sudan hard-decision and Kötter–Vardy soft-decision decodings of Reed–Solomon codes, the multivariate interpolation step of list-decoding of folded Reed–Solomon codes, and Hermite–Padé 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 σ it uses O ˜ ( m ω − 1 ( σ + | s | ) ) field operations, where ω is the exponent of matrix multiplication, and | s | is the sum of the entries of the input shifts, 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é approximation.