Gröbner bases and generalized Padé approximation

Authors:
Jeffrey B. Farr and Shuhong Gao

Journal:
Math. Comp. **75** (2006), 461-473

MSC (2000):
Primary 41A21, 13P10, 41A63

Published electronically:
October 12, 2005

MathSciNet review:
2176409

Full-text 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**, 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****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, Berlin-New York, 1982, pp. 24–31. MR**680050****5.**David Cox, John Little, and Donal O’Shea,*Ideals, varieties, and algorithms*, 2nd ed., Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1997. An introduction to computational algebraic geometry and commutative algebra. MR**1417938****6.**David Cox, John Little, and Donal O’Shea,*Using algebraic geometry*, Graduate Texts in Mathematics, vol. 185, Springer-Verlag, New York, 1998. MR**1639811****7.**Annie Cuyt,*How well can the concept of Padé approximant be generalized to the multivariate case?*, J. Comput. Appl. Math.**105**(1999), no. 1-2, 25–50. Continued fractions and geometric function theory (CONFUN) (Trondheim, 1997). MR**1690577**, 10.1016/S0377-0427(99)00028-X**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**, 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**, 10.1016/S0747-7171(08)80087-9**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**, 10.1023/A:1018981505752**13.**Venkatesan Guruswami and Madhu Sudan,*Improved decoding of Reed-Solomon and algebraic-geometry codes*, IEEE Trans. Inform. Theory**45**(1999), no. 6, 1757–1767. MR**1720630**, 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****15.**Martin Kreuzer and Lorenzo Robbiano,*Computational commutative algebra. 1*, Springer-Verlag, Berlin, 2000. MR**1790326****16.**John B. Little, David Ortiz, Ricardo Ortiz-Rosado, Rebecca Pablo, and Karen Ríos-Soto,*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**, 10.1016/S0747-7171(03)00041-5**17.**C. H. Lutterodt,*A two-dimensional analogue of Padé approximant theory*, J. Phys. A**7**(1974), 1027–1037. MR**0408510****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**, 10.1007/BF01386834**19.**Lorenzo Robbiano,*On the theory of graded structures*, J. Symbolic Comput.**2**(1986), no. 2, 139–170. MR**849048**, 10.1016/S0747-7171(86)80019-0

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 29634-0975

Email:
sgao@ces.clemson.edu

DOI:
https://doi.org/10.1090/S0025-5718-05-01790-4

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 MDA904-02-1-0067, and the DoD Multidisciplinary University Research Initiative (MURI) program administered by the Office of Naval Research (ONR) under Grant N00014-00-1-0565. 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.