An extended GCD algorithm for parametric univariate polynomials and application to parametric Smith normal form. (English) Zbl 07300103
Mantzaflaris, Angelos (ed.), Proceedings of the 45th international symposium on symbolic and algebraic computation, ISSAC ’20, Kalamata, Greece, July 20–23, 2020. New York, NY: Association for Computing Machinery (ACM). 442-449 (2020).
MSC:
| 13P10 | Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) |
| 68W30 | Symbolic computation and algebraic computation |
Keywords:
comprehensive Gröbner system; extended greatest common divisor; parametric univariate polynomial; Smith normal formSoftware:
PGBReferences:
| [1] | S.A. Abramov and K.Y. Kvashenko. 1993. On the Greatest Common Divisor of Polynomials which Depend on a Parameter. In Proceedings of the 1993 ACM International Symposium on Symbolic and Algebraic Computation. 152-156. · Zbl 0925.13009 |
| [2] | A. Ayad. 2010. Complexity of algorithms for computing greatest common divisors of parametric univariate polynomials. International Journal of Algebra 4 (2010), 173-188. · Zbl 1205.11133 |
| [3] | T. Bächler, V. Gerdt, M. Lange-Hegermann, and D. Robertz. 2012. Algorithmic Thomas decomposition of algebraic and differential systems. Journal of Symbolic Computation 47, 10 (2012), 1233-1266. · Zbl 1315.35013 |
| [4] | S. Bamett. 1971. Matrices in control theory. Van Norstrand Reinhold (1971). · Zbl 0245.93002 |
| [5] | B. Beckermann, G. Labahn, and G. Villard. 1999. Shifted normal forms of polynomial matrices. In Proceedings of ISSAC’ 1999. 189-196. |
| [6] | G. Bradley. 1971. Algorithms for Hermite and Smith normal matrices and linear diophantine equations. Math. Comp. 25, 116 (1971), 897-907. · Zbl 0233.65023 |
| [7] | R. P. Brent and H. T. Kung. 1984. Systolic VLSI Arrays for Polynomial GCD Computation. IEEE Trans. Comput. 100, 8 (1984), 731-736. · Zbl 0542.94043 |
| [8] | W.S. Brown. 1971. On Euclid’s Algorithm And The Computation Of Polynomial Greatest Common Divisors. J. ACM 18, 4 (1971), 478-504. · Zbl 0226.65040 |
| [9] | C. Chen and M. Maza. 2012. Algorithms for computing triangular decomposition of polynomial systems. Journal of Symbolic Computation 47, 6 (2012), 610-642. · Zbl 1264.12011 |
| [10] | S.C. Chou. 1988. Mechanical geometry theorem proving. Vol. 41. Springer Science and Business Media. · Zbl 0661.14037 |
| [11] | R.M. Corless, M.M. Maza, and S.E. Thornton. 2017. Jordan Canonical Form with Parameters from Frobenius Form with Parameters. In International Conference on Mathematical Aspects of Computer and Information Sciences. 179-194. · Zbl 1504.65109 |
| [12] | D. Cox, J. Little, and D. O’shea. 2006. Using algebraic geometry. Vol. 185. Springer Science & Business Media. · Zbl 1079.13017 |
| [13] | D. Cox, T. Sederberg, and F.L. Chen. 1998. The moving line ideal basis of planar rational curves. Computer Aided Geometric Design 15, 8 (1998), 803-827. · Zbl 0908.68174 |
| [14] | F. R. Gantmakher. 1959. The theory of matrices. American Mathematical Soc. · Zbl 0085.01001 |
| [15] | K. Geddes, S. Czapor, and G. Labahn. 1992. Algorithms for computer algebra. Springer Science and Business Media. · Zbl 0805.68072 |
| [16] | P. Gianni and B. Trager. 1985. Gcd’s and factoring multivariate polynomials using Grobner bases. In European Conference on Computer Algebra. Springer, 409-410. |
| [17] | H. Kai and M.-T. Noda. 2000. Hybrid rational approximation and its applications. Reliable Computing 6 (2000), 429-438. · Zbl 0970.65010 |
| [18] | M. Kalkbrener. 1997. On the Stability of Gröbner Bases Under Specializations. Journal of Symbolic Computation 24, 1 (1997), 51-58. · Zbl 1054.13502 |
| [19] | D. Kapur, D. Lu, M. Monagan, Y. Sun, and D.K. Wang. 2018. An Efficient Algorithm for Computing Parametric Multivariate Polynomial GCD. In Proceedings of the 2018 International Symposium on Symbolic and Algebraic Computation. 239-246. · Zbl 1467.13047 |
| [20] | D. Kapur, Y. Sun, and D.K. Wang. 2010. A new algorithm for computing comprehensive Gröbner systems. In Proceedings of ISSAC’ 2010. 29-36. · Zbl 1321.68533 |
| [21] | D. Kapur, Y. Sun, and D.K. Wang. 2013. An efficient algorithm for computing a comprehensive Gröbner system of a parametric polynomial system. Journal of Symbolic Computation 49 (2013), 27-44. · Zbl 1255.13018 |
| [22] | A. Montes. 2002. A new algorithm for discussing Gröbner bases with parameters. Journal of Symbolic Computation 33, 2 (2002), 183-208. · Zbl 1068.13016 |
| [23] | J. Moses and D. Yun. 1973. The ez gcd algorithm. In Proceedings of the ACM annual conference. ACM, 159-166. |
| [24] | K. Nabeshima. 2007. PGB: a package for computing parametric Gröbner and related objects. ACM Communications in Computer Algebra 41, 3 (2007), 104-105. |
| [25] | K. Nabeshima. 2007. A speed-up of the algorithm for computing comprehensive Gröbner systems. In Proceedings of ISSAC’ 2007. 299-306. · Zbl 1190.13025 |
| [26] | K. Nabeshima. 2010. On the computation of parametric gröbner bases for modules and syzygies. Japan Journal of Industrial and Applied Mathematics 27, 2 (2010), 217-238. · Zbl 1204.13019 |
| [27] | K. Nagasaka. 2017. Parametric Greatest Common Divisors using Comprehensive Gröbner Systems. In Proceedings of ISSAC’ 2017. 341-348. · Zbl 1458.13037 |
| [28] | C. Norman. 2012. Finitely Generated Abelian Groups and Similarity of Matrices over a Field. Springer Undergraduate Mathematics (2012). · Zbl 1242.20002 |
| [29] | I.S. Pace and S. Barnett. 1974. Efficient algorithms for linear system calculations. I: Smith form and common divisor of polynomial matrices. Internat.j.systems Sci (1974), 403-411. · Zbl 0287.93005 |
| [30] | H.H. Rosenbrock. 1970. State-space and multivariable theory. (1970). · Zbl 0246.93010 |
| [31] | T. Sasaki and M. Suzuki. 1992. Three new algorithms for multivariate polynomial GCD. Journal of Symbolic Computation 13, 4 (1992), 395-411. · Zbl 0761.12005 |
| [32] | J. Sendra and J. Llovet. 1992. An extended polynomial GCD algorithm using Hankel matrices. Journal of symbolic computation 13, 1 (1992), 25-39. · Zbl 0771.15005 |
| [33] | A. Storjohann. 1997. A solution to the extended GCD problem with applications. In Proceedings of the 1997 international symposium on Symbolic and algebraic computation. 109-116. · Zbl 0923.11004 |
| [34] | A. Suzuki and Y. Sato. 2002. An alternative approach to comprehensive Gröbner bases. Journal of Symbolic Computation 36, 3 (2002), 649-667. · Zbl 1053.13013 |
| [35] | A. Suzuki and Y. Sato. 2006. A simple algorithm to compute comprehensive Gröbner bases using Gröbner bases. In Proceedings of the 2006 ACM International Symposium on Symbolic and Algebraic Computation. 326-331. · Zbl 1356.13040 |
| [36] | V. Weispfenning. 1992. Comprehensive Gröbner bases. Journal of Symbolic Computation 14, 1 (1992), 1-29. · Zbl 0784.13013 |
| [37] | R. Zippel. 1979. Probabilistic algorithms for sparse polynomials. In Proceedings of the EUROSAM’79. Springer-Verlag, 216-226. · Zbl 0418.68040 |
| [38] | R. Zippel. 1993. Effective Polynomial Computation. Vol. 241. Springer Science and Business Media. · Zbl 0794.11048 |
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.
