×

Computing minimal interpolation bases. (English) Zbl 1375.65013

Summary: 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 in [M. Van Barel and A. Bultheel, Numer. Algorithms 3, No. 1–4, 451–461 (1992; Zbl 0780.41014)] and the rational interpolation problem in [B. Beckermann and G. Labahn, SIAM J. Matrix Anal. Appl. 22, No. 1, 114–144 (2000; Zbl 0973.65007)]. 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 \(\sigma\) it uses \(\mathcal{O}^\sim(m^{\omega - 1}(\sigma + | \mathbf{s}|))\) field operations, where \(\omega\) is the exponent of matrix multiplication, and \(| \mathbf{s}|\) is the sum of the entries of the input shift \(\mathbf{s}\), with \(\min(\mathbf{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.

MSC:

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

References:

[1] Alekhnovich, M., Linear Diophantine equations over polynomials and soft decoding of Reed-Solomon codes, (FOCS’02 (2002), IEEE), 439-448
[2] Alekhnovich, M., Linear Diophantine equations over polynomials and soft decoding of Reed-Solomon codes, IEEE Trans. Inf. Theory, 51, 7, 2257-2265 (Jul. 2005)
[3] Beckermann, B., Zur Interpolation mit polynomialen Linearkombinationen beliebiger Funktionen (1990), Department of Applied Mathematics, University of Hannover: Department of Applied Mathematics, University of Hannover Germany, PhD thesis
[4] Beckermann, B., A reliable method for computing M-Padé approximants on arbitrary staircases, J. Comput. Appl. Math., 40, 1, 19-42 (1992) · Zbl 0810.65014
[5] Beckermann, B.; Labahn, G., Fraction-free computation of matrix rational interpolants and matrix gcds, SIAM J. Matrix Anal. Appl., 22, 1, 114-144 (2000) · Zbl 0973.65007
[6] Beckermann, B.; Labahn, G., A uniform approach for the fast computation of matrix-type Padé approximants, SIAM J. Matrix Anal. Appl., 15, 3, 804-823 (Jul. 1994)
[7] Beckermann, B.; Labahn, G.; Villard, G., Normal forms for general polynomial matrices, J. Symb. Comput., 41, 6, 708-737 (2006) · Zbl 1128.15005
[8] Beelen, P.; Brander, K., Key equations for list decoding of Reed-Solomon codes and how to solve them, J. Symb. Comput., 45, 7, 773-786 (2010) · Zbl 1191.94129
[9] Beelen, T. G.J.; van den Hurk, G. J.; Praagman, C., A new method for computing a column reduced polynomial matrix, Syst. Control Lett., 10, 4, 217-224 (1988) · Zbl 0646.65040
[10] Bernstein, D. J., Simplified high-speed high-distance list decoding for alternant codes, (PQCrypto’11. PQCrypto’11, Lect. Notes Comput. Sci., vol. 7071 (2011), Springer), 200-216 · Zbl 1298.94140
[11] Bostan, A.; Jeannerod, C.-P.; Schost, E., Solving structured linear systems with large displacement rank, Theor. Comput. Sci., 407, 1-3, 155-181 (2008) · Zbl 1169.65023
[12] Brander, K., Interpolation and List Decoding of Algebraic Codes (2010), Technical University of Denmark, PhD thesis
[13] Brent, R. P.; Gustavson, F. G.; Yun, D. Y.Y., Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. Algorithms, 1, 3, 259-295 (1980) · Zbl 0475.65018
[14] Busse, P., Multivariate List Decoding of Evaluation Codes with a Gröbner Basis Perspective (2008), University of Kentucky, PhD thesis
[15] Cantor, D. G.; Kaltofen, E., On fast multiplication of polynomials over arbitrary algebras, Acta Inform., 28, 7, 693-701 (1991) · Zbl 0766.68055
[16] Chowdhury, M.; Jeannerod, C.-P.; Neiger, V.; Schost, E.; Villard, G., Faster algorithms for multivariate interpolation with multiplicities and simultaneous polynomial approximations, IEEE Trans. Inf. Theory, 61, 5, 2370-2387 (2015) · Zbl 1359.94683
[17] Cohn, H.; Heninger, N., Approximate common divisors via lattices, (Tenth Algorithmic Number Theory Symposium (2013), Mathematical Sciences Publishers (MSP)), 271-293 · Zbl 1344.11085
[18] Cohn, H.; Heninger, N., Ideal forms of Coppersmith’s theorem and Guruswami-Sudan list decoding, Adv. Math. Commun., 9, 3, 311-339 (2015) · Zbl 1355.65064
[19] Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, J. Symb. Comput., 9, 3, 251-280 (1990) · Zbl 0702.65046
[20] Devet, C.; Goldberg, I.; Heninger, N., Optimally robust private information retrieval, (USENIX Security 12 (2012), USENIX), 269-283
[21] Dummit, D. S.; Foote, R. M., Abstract Algebra (2004), John Wiley & Sons · Zbl 1037.00003
[22] Giorgi, P.; Jeannerod, C.-P.; Villard, G., On the complexity of polynomial matrix computations, (ISSAC’03 (2003), ACM), 135-142 · Zbl 1072.68708
[23] Gupta, S.; Sarkar, S.; Storjohann, A.; Valeriote, J., Triangular \(x\)-basis decompositions and derandomization of linear algebra algorithms over \(K [x]\), J. Symb. Comput., 47, 4, 422-453 (2012) · Zbl 1268.68172
[24] Guruswami, V.; Rudra, A., Explicit codes achieving list decoding capacity: error-correction with optimal redundancy, IEEE Trans. Inf. Theory, 54, 1, 135-150 (2008) · Zbl 1205.94125
[25] Guruswami, V.; Sudan, M., Improved decoding of Reed-Solomon and algebraic-geometry codes, IEEE Trans. Inf. Theory, 45, 6, 1757-1767 (1999) · Zbl 0958.94036
[26] Guruswami, V.; Sudan, M., Improved decoding of Reed-Solomon and algebraic-geometric codes, (FOCS’98 (Nov. 1998)), 28-39
[27] Kailath, T., Linear Systems (1980), Prentice Hall · Zbl 0458.93025
[28] Keller-Gehrig, W., Fast algorithms for the characteristic polynomial, Theor. Comput. Sci., 36, 309-317 (1985) · Zbl 0565.68041
[29] Knuth, D. E., The analysis of algorithms, (Congrès Int. Math., Nice, France, vol. 3 (1970)), 269-274 · Zbl 0196.01703
[30] Kötter, R., Fast generalized minimum-distance decoding of algebraic-geometry and Reed-Solomon codes, IEEE Trans. Inf. Theory, 42, 3, 721-737 (1996) · Zbl 0861.94030
[31] Kötter, R.; Vardy, A., Algebraic soft-decision decoding of Reed-Solomon codes, IEEE Trans. Inf. Theory, 49, 11, 2809-2825 (2003) · Zbl 1301.94159
[32] Kötter, R.; Vardy, A., A complexity reducing transformation in algebraic list decoding of Reed-Solomon codes, (ITW2003 (2003), IEEE), 10-13
[33] Le Gall, F., Powers of tensors and fast matrix multiplication, (ISSAC’14 (2014), ACM), 296-303 · Zbl 1325.65061
[35] Lee, K.; O’Sullivan, M., An interpolation algorithm using Gröbner bases for soft-decision decoding of Reed-Solomon codes, (2006 IEEE International Symposium on Information Theory (July 2006)), 2032-2036
[36] Lee, K.; O’Sullivan, M. E., List decoding of Reed-Solomon codes from a Gröbner basis perspective, J. Symb. Comput., 43, 9, 645-658 (2008) · Zbl 1214.94080
[37] Lübbe, W., Über ein allgemeines Interpolationsproblem — lineare Identitäten zwischen benachbarten Lösungssystemen (1983), Department of Applied Mathematics, University of Hannover: Department of Applied Mathematics, University of Hannover Germany, PhD thesis
[38] Mahler, K., Perfect systems, Compos. Math., 19, 2, 95-166 (1968) · Zbl 0168.31303
[39] McEliece, R. J., The Guruswami-Sudan Decoding Algorithm for Reed-Solomon Codes (2003), IPN Progress Report 42-153
[40] Mulders, T.; Storjohann, A., On lattice reduction for polynomial matrices, J. Symb. Comput., 35, 377-401 (2003) · Zbl 1028.65038
[41] Nielsen, J. S.R., Fast Kötter-Nielsen-Høholdt interpolation in the Guruswami-Sudan algorithm, (ACCT’14 (2014))
[42] Nielsen, R. R.; Høholdt, T., Decoding Reed-Solomon codes beyond half the minimum distance, (Coding Theory, Cryptography and Related Areas (2000), Springer), 221-236 · Zbl 1017.94530
[43] Olshevsky, V.; Shokrollahi, M. A., A displacement approach to efficient decoding of algebraic-geometric codes, (STOC’99 (1999), ACM), 235-244 · Zbl 1345.94104
[44] Parvaresh, F.; Vardy, A., Correcting errors beyond the Guruswami-Sudan radius in polynomial time, (FOCS’05 (2005), IEEE), 285-294
[45] Paszkowski, S., Recurrence relations in Padé-Hermite approximation, J. Comput. Appl. Math., 19, 1, 99-107 (Jul. 1987)
[46] Roth, R. M.; Ruckenstein, G., Efficient decoding of Reed-Solomon codes beyond half the minimum distance, IEEE Trans. Inf. Theory, 46, 1, 246-257 (2000) · Zbl 1001.94046
[47] Schönhage, A., Schnelle Berechnung von Kettenbruchentwicklungen, Acta Inform., 1, 139-144 (1971), (in German) · Zbl 0223.68008
[48] Sergeyev, A. V., A recursive algorithm for Padé-Hermite approximations, USSR Comput. Math. Math. Phys., 26, 2, 17-22 (Jul. 1987)
[49] Storjohann, A., Algorithms for Matrix Canonical Forms (2000), Swiss Federal Institute of Technology - ETH, PhD thesis
[50] Storjohann, A., Notes on computing minimal approximant bases, (Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings (2006))
[51] Sudan, M., Decoding of Reed-Solomon codes beyond the error-correction bound, J. Complex., 13, 1, 180-193 (1997) · Zbl 0872.68026
[52] Van Barel, M.; Bultheel, A., The computation of non-perfect Padé-Hermite approximants, Numer. Algorithms, 1, 3, 285-304 (1991) · Zbl 0753.65013
[53] Van Barel, M.; Bultheel, A., A general module theoretic framework for vector M-Padé and matrix rational interpolation, Numer. Algorithms, 3, 451-462 (1992) · Zbl 0780.41014
[54] von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (2013), Cambridge University Press · Zbl 1277.68002
[56] Zeh, A., Algebraic Soft- and Hard-Decision Decoding of Generalized Reed-Solomon and Cyclic Codes (2013), École Polytechnique, PhD thesis · Zbl 1301.94148
[57] Zeh, A.; Gentner, C.; Augot, D., An interpolation procedure for list decoding Reed-Solomon codes based on generalized key equations, IEEE Trans. Inf. Theory, 57, 9, 5946-5959 (2011) · Zbl 1365.94608
[58] Zhou, W., Fast Order Basis and Kernel Basis Computation and Related Problems (2012), University of Waterloo, PhD thesis
[59] Zhou, W.; Labahn, G., Efficient algorithms for order basis computation, J. Symb. Comput., 47, 7, 793-819 (2012) · Zbl 1258.65046
[60] Zhou, W.; Labahn, G.; Storjohann, A., Computing minimal nullspace bases, (ISSAC’12 (2012), ACM), 366-373 · Zbl 1323.68633
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.