Gröbner bases and generalized Padé approximation
Authors:
Jeffrey B. Farr and Shuhong Gao
Journal:
Math. Comp. 75 (2006), 461473
MSC (2000):
Primary 41A21, 13P10, 41A63
Published electronically:
October 12, 2005
MathSciNet review:
2176409
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: It is shown how to find general multivariate Padé approximation using the Gröbner basis technique. This method is more flexible than previous approaches, and several examples are given to illustrate this advantage. When the number of variables is small compared to the degree of approximation, the Gröbner basis technique is more efficient than the linear algebra methods in the literature.
 1.
J.
Abbott, A.
Bigatti, M.
Kreuzer, and L.
Robbiano, Computing ideals of points, J. Symbolic Comput.
30 (2000), no. 4, 341–356. MR 1784266
(2001j:13026), http://dx.doi.org/10.1006/jsco.2000.0411
 2.
William
W. Adams and Philippe
Loustaunau, An introduction to Gröbner bases, Graduate
Studies in Mathematics, vol. 3, American Mathematical Society,
Providence, RI, 1994. MR 1287608
(95g:13025)
 3.
E.R. Berlekamp and L.R. Welch, Error correction for algebraic block codes, U.S. Patent No. 4,633,470, issued December 30, 1986.
 4.
H.
M. Möller and B.
Buchberger, The construction of multivariate polynomials with
preassigned zeros, Computer algebra (Marseille, 1982) Lecture Notes
in Comput. Sci., vol. 144, Springer, BerlinNew York, 1982,
pp. 24–31. MR 680050
(84b:12003)
 5.
David
Cox, John
Little, and Donal
O’Shea, Ideals, varieties, and algorithms, 2nd ed.,
Undergraduate Texts in Mathematics, SpringerVerlag, New York, 1997. An
introduction to computational algebraic geometry and commutative algebra.
MR
1417938 (97h:13024)
 6.
David
Cox, John
Little, and Donal
O’Shea, Using algebraic geometry, Graduate Texts in
Mathematics, vol. 185, SpringerVerlag, New York, 1998. MR 1639811
(99h:13033)
 7.
Annie
Cuyt, How well can the concept of Padé approximant be
generalized to the multivariate case?, J. Comput. Appl. Math.
105 (1999), no. 12, 25–50. Continued fractions
and geometric function theory (CONFUN) (Trondheim, 1997). MR 1690577
(2000e:41029), http://dx.doi.org/10.1016/S03770427(99)00028X
 8.
Jeffrey B. Farr and Shuhong Gao, Computing Gröbner bases for vanishing ideals of finite sets of points, preprint. (Available at
http://www.math.clemson.edu/~sgao/pub.html )
 9.
Jeffrey B. Farr, Shuhong Gao, and Daniel L. Noneaker, Construction and decoding performance of random linear codes, in preparation.
 10.
Patrick
Fitzpatrick, On the key equation, IEEE Trans. Inform. Theory
41 (1995), no. 5, 1290–1302. MR 1366325
(96i:94033), http://dx.doi.org/10.1109/18.412677
 11.
Patrick
Fitzpatrick and John
Flynn, A Gröbner basis technique for Padé
approximation, J. Symbolic Comput. 13 (1992),
no. 2, 133–138. MR 1153639
(93b:68037), http://dx.doi.org/10.1016/S07477171(08)800879
 12.
Mariano
Gasca and Thomas
Sauer, Polynomial interpolation in several variables, Adv.
Comput. Math. 12 (2000), no. 4, 377–410.
Multivariate polynomial interpolation. MR 1768957
(2001d:41010), http://dx.doi.org/10.1023/A:1018981505752
 13.
Venkatesan
Guruswami and Madhu
Sudan, Improved decoding of ReedSolomon and algebraicgeometry
codes, IEEE Trans. Inform. Theory 45 (1999),
no. 6, 1757–1767. MR 1720630
(2000j:94033), http://dx.doi.org/10.1109/18.782097
 14.
J.
Karlsson and H.
Wallin, Rational approximation by an interpolation procedure in
several variables, Padé and rational approximation (Proc.
Internat. Sympos., Univ. South Florida, Tampa, Fla., 1976) Academic
Press, New York, 1977, pp. 83–100. MR 0481778
(58 #1877)
 15.
Martin
Kreuzer and Lorenzo
Robbiano, Computational commutative algebra. 1,
SpringerVerlag, Berlin, 2000. MR 1790326
(2001j:13027)
 16.
John
B. Little, David
Ortiz, Ricardo
OrtizRosado, Rebecca
Pablo, and Karen
RíosSoto, Some remarks on Fitzpatrick and Flynn’s
Gröbner basis technique for Padé approximation, J.
Symbolic Comput. 35 (2003), no. 4, 451–461. MR 1976578
(2004e:41011), http://dx.doi.org/10.1016/S07477171(03)000415
 17.
C.
H. Lutterodt, A twodimensional analogue of Padé approximant
theory, J. Phys. A 7 (1974), 1027–1037. MR 0408510
(53 #12274)
 18.
M.
G. Marinari, H.
M. Möller, and T.
Mora, Gröbner bases of ideals defined by functionals with an
application to ideals of projective points, Appl. Algebra Engrg. Comm.
Comput. 4 (1993), no. 2, 103–145. MR 1223853
(94g:13019), http://dx.doi.org/10.1007/BF01386834
 19.
Lorenzo
Robbiano, On the theory of graded structures, J. Symbolic
Comput. 2 (1986), no. 2, 139–170. MR 849048
(87j:13010), http://dx.doi.org/10.1016/S07477171(86)800190
 1.
 J. Abbott, A. Bigatti, M. Kreuzer, and L. Robbiano, Computing ideals of points, J. Symbolic Comput. 30 (2000), 341356. MR 1784266 (2001j:13026)
 2.
 William W. Adams and Philippe Loustaunau, An introduction to Gröbner bases, Graduate Studies in Mathematics, 3, American Mathematical Society, Providence, RI, 1994. MR 1287608 (95g:13025)
 3.
 E.R. Berlekamp and L.R. Welch, Error correction for algebraic block codes, U.S. Patent No. 4,633,470, issued December 30, 1986.
 4.
 B. Buchberger and H. M. Möller, The construction of multivariate polynomials with preassigned zeros. Computer algebra, EUROCAM '82, pp. 2431, Lecture Notes in Comput. Sci., vol. 144, Springer, BerlinNew York, 1982. MR 0680050 (84b:12003)
 5.
 David Cox, John Little, and Donal O'Shea, Ideals, varieties, and algorithms, 2nd ed., Undergraduate Texts in Mathematics, SpringerVerlag, New York, 1997. MR 1417938 (97h:13024)
 6.
 David Cox, John Little, and Donal O'Shea, Using algebraic geometry, Graduate Texts in Mathematics, 185, SpringerVerlag, New York, 1998. MR 1639811 (99h:13033)
 7.
 Annie Cuyt, How well can the concept of Padé approximant be generalized to the multivariate case?, Continued fractions and geometric function theory (CONFUN) (Trondheim, 1997), J. Comput. Appl. Math. 105 (1999), no. 12, 2550. MR 1690577 (2000e:41029)
 8.
 Jeffrey B. Farr and Shuhong Gao, Computing Gröbner bases for vanishing ideals of finite sets of points, preprint. (Available at
http://www.math.clemson.edu/~sgao/pub.html )
 9.
 Jeffrey B. Farr, Shuhong Gao, and Daniel L. Noneaker, Construction and decoding performance of random linear codes, in preparation.
 10.
 Patrick Fitzpatrick, On the key equation, IEEE Transactions on Information Theory 41 (1995), no. 5, 12901302. MR 1366325 (96i:94033)
 11.
 Patrick Fitzpatrick and John Flynn, A Gröbner basis technique for Padé approximation, J. Symbolic Comput. 13 (1992), 133138.MR 1153639 (93b:68037)
 12.
 Mariano Gasca and Thomas Sauer, Polynomial interpolation in several variables, in Multivariate polynomial interpolation, Adv. Comput. Math. 12 (2000), no. 4, 377410. MR 1768957 (2001d:41010)
 13.
 Venkatesan Guruswami and Madhu Sudan, Improved decoding of ReedSolomon and algebraicgeometry codes, IEEE Trans. Inform. Theory 45 (1999), no. 6, 17571767. MR 1720630 (2000j:94033)
 14.
 J. Karlsson and H. Wallin, Rational approximation by an interpolation procedure in several variables, Padé and rational approximation (Proc. Internat. Sympos., Univ. South Florida, Tampa, 1976), pp. 83100, Academic Press, New York, 1977. MR 0481778 (58:1877)
 15.
 Martin Kreuzer and Lorenzo Robbiano, Computational Commutative Algebra 1, SpringerVerlag, Berlin, 2000. MR 1790326 (2001j:13027)
 16.
 John B. Little, David Ortiz, Ricardo OrtizRosado, Rebecca Pablo, and Karen RíosSoto, Some remarks on Fitzpatrick and Flynn's Gröbner basis technique for Padé approximation, J. Symbolic Comput. 35 (2003), 451461. MR 1976578 (2004e:41011)
 17.
 C.H. Lutterodt, A twodimensional analogue of Padé approximant theory, J. Phys. A 7 (1974), 10271037. MR 0408510 (53:12274)
 18.
 M. G. Marinari, H.M. Möller, and T. Mora, Gröbner bases of ideals defined by functionals with an application to ideals of projective points, Appl. Algebra Engrg. Comm. Comput. 4 (1993), no. 2, 103145.MR 1223853 (94g:13019)
 19.
 Lorenzo Robbiano, On the theory of graded structures, J. Symbolic Comput. 2 (1986), no. 2, 139170. MR 0849048 (87j:13010)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC (2000):
41A21,
13P10,
41A63
Retrieve articles in all journals
with MSC (2000):
41A21,
13P10,
41A63
Additional Information
Jeffrey B. Farr
Affiliation:
Centre for Experimental and Constructive Mathematics (CECM) and Department of Mathematics, Simon Fraser University, Burnaby, British Columbia, Canada V5A 1S6
Email:
jfarr@cecm.sfu.ca
Shuhong Gao
Affiliation:
Department of Mathematical Sciences, Clemson University, Clemson, South Carolina 296340975
Email:
sgao@ces.clemson.edu
DOI:
http://dx.doi.org/10.1090/S0025571805017904
PII:
S 00255718(05)017904
Received by editor(s):
February 10, 2004
Received by editor(s) in revised form:
December 10, 2004
Published electronically:
October 12, 2005
Additional Notes:
This work was supported in part by the National Science Foundation (NSF) under Grant DMS0302549, the National Security Agency (NSA) under Grant MDA9040210067, and the DoD Multidisciplinary University Research Initiative (MURI) program administered by the Office of Naval Research (ONR) under Grant N000140010565. MITACS also partially supported the first author.
Article copyright:
© Copyright 2005
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
