Shirayanagi, Kiyoshi; Sekigawa, Hiroshi A new Gröbner basis conversion method based on stabilization techniques. (English) Zbl 1181.68329 Theor. Comput. Sci. 409, No. 2, 311-317 (2008). Summary: We propose a new method for converting a Gröbner basis with respect to one term order into a Gröbner basis with respect to another term order by using the algorithm stabilization techniques proposed by Shirayanagi and Sweedler. First, we guess the support of the desired Gröbner basis from a floating-point Gröbner basis by exploiting the supportwise convergence property of the stabilized Buchberger’s algorithm. Next, assuming this support to be correct, we use linear algebra, namely, the method of indeterminate coefficients to determine the exact values for the coefficients. Related work includes the FGLM algorithm and its modular version. Our method is new in the sense that it can be thought of as a floating-point approach to the linear algebra method. The results of Maple computing experiments indicate that our method can be very effective in the case of non-rational coefficients, especially the ones including transcendental constants. Cited in 1 Document MSC: 68W30 Symbolic computation and algebraic computation 13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) Keywords:basis conversion; Gröbner basis; algorithm stabilization; floating-point Gröbner basis; symbolic and numeric computation Software:Maple PDFBibTeX XMLCite \textit{K. Shirayanagi} and \textit{H. Sekigawa}, Theor. Comput. Sci. 409, No. 2, 311--317 (2008; Zbl 1181.68329) Full Text: DOI References: [1] Alefeld, G.; Herzberger, J., Introduction to Interval Computations, Computer Science and Applied Mathematics (1983), Academic Press [2] A. Basiri, J.-C. Faugère, Changing the ordering of Gröbner bases with LLL: Case of two variables, in: Proc. the 2003 International Symposium on Symbolic and Algebraic Computation, ISSAC 2003, 2003, pp. 23-28; A. Basiri, J.-C. Faugère, Changing the ordering of Gröbner bases with LLL: Case of two variables, in: Proc. the 2003 International Symposium on Symbolic and Algebraic Computation, ISSAC 2003, 2003, pp. 23-28 [3] Bini, D.; Pan, V. Y., Polynomial and Matrix Computations, Volume 1: Fundamental Algorithms (1994), Birkhäuser: Birkhäuser Boston · Zbl 0809.65012 [4] Buchberger, B., Gröbner bases: An algorithmic method in polynomial ideal theory, (Bose, N. K., Multidimensional Systems Theory (1985), D. Reidel Publishing Company), 184-232, (Chapter 6) · Zbl 0587.13009 [5] Collart, S.; Kalkbrenner, M.; Mall, D., Converting bases with the Gröbner walk, Journal of Symbolic Computation, 24, 3-4, 465-469 (1997) · Zbl 0908.13020 [6] Faugère, J.; Gianni, P.; Lazard, D.; Mora, T., Efficient computation of zero-dimensional Gröbner bases by change of ordering, Journal of Symbolic Computation, 16, 4, 329-344 (1993) · Zbl 0805.13007 [7] P. Khungurn, Stabilizing an algorithm for integrating rational functions, 2005, Preprint. http://web.mit.edu/pramook/www/18.337/report.pdf; P. Khungurn, Stabilizing an algorithm for integrating rational functions, 2005, Preprint. http://web.mit.edu/pramook/www/18.337/report.pdf [8] P. Khungurn, Shirayanagi-Sweedler algebraic algorithm stabilization and polynomial gcd algorithms, Master’s Thesis, MIT School of Engineering, 2007; P. Khungurn, Shirayanagi-Sweedler algebraic algorithm stabilization and polynomial gcd algorithms, Master’s Thesis, MIT School of Engineering, 2007 [9] P. Khungurn, H. Sekigawa, K. Shirayanagi, Minimum converging precision of the QR-factorization algorithm for real polynomial, in: Proc. ISSAC 2007, 2007, pp. 227-234; P. Khungurn, H. Sekigawa, K. Shirayanagi, Minimum converging precision of the QR-factorization algorithm for real polynomial, in: Proc. ISSAC 2007, 2007, pp. 227-234 · Zbl 1190.65068 [10] W. Krandick, Symbolic algebraic techniques for steady state power system analysis. slides, 2005. http://www.drexel.edu/coe/news/articles/rd05/393.pdf; W. Krandick, Symbolic algebraic techniques for steady state power system analysis. slides, 2005. http://www.drexel.edu/coe/news/articles/rd05/393.pdf [11] S. Licciardi, T. Mora, Implicitization of hypersurfaces and curves by the primbasissatz and basis conversion, in: Proc. ISSAC’94, 1994, pp. 191-196; S. Licciardi, T. Mora, Implicitization of hypersurfaces and curves by the primbasissatz and basis conversion, in: Proc. ISSAC’94, 1994, pp. 191-196 · Zbl 0916.14032 [12] H. Minakuchi, H. Kai, M.-T. Noda, Algorithms of generalized inverse and their stabilization, in: Electronic Proc. ATCM’98, 1998. http://www.atcm.mathandtech.org/EP/1998/ATCMP046/paper.pdf; H. Minakuchi, H. Kai, M.-T. Noda, Algorithms of generalized inverse and their stabilization, in: Electronic Proc. ATCM’98, 1998. http://www.atcm.mathandtech.org/EP/1998/ATCMP046/paper.pdf [13] Noda, M.-T.; Sasaki, T., Approximate gcd and its application to ill-conditioned algebraic equations, Journal of Computational and Applied Mathematics, 38, 335-351 (1991) · Zbl 0747.65034 [14] Noro, M.; Yokoyama, K., A modular method to compute the rational univariate representation of zero-dimensional ideals, Journal of Symbolic Computation, 28, 1, 243-263 (1999) · Zbl 0945.13010 [15] Pan, V. Y., Complexity of computations with matrices and polynomials, SIAM Review, 34, 2, 225-262 (1992) · Zbl 0757.65051 [16] (Verschelde, J.; Watt, S., Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation. Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation, SNC 2007, July 2007, London, Ontario, Canada (2007), ACM Press: ACM Press New York) · Zbl 1143.00005 [17] Sasaki, T.; Noda, M.-T., Approximate square-free decomposition and root finding of ill-conditioned algebraic equations, Journal of Information Processing, 12, 2, 159-168 (1989) · Zbl 0755.65046 [18] Shirayanagi, K., Floating point Gröbner bases, Mathematics and Computers in Simulation, 42, 4-6, 509-528 (1996) · Zbl 1037.68547 [19] K. Shirayanagi, M. Sweedler, A theory of stabilizing algebraic algorithms, Technical Report 95-28, Mathematical Sciences Institute, Cornell University, 92 pp., 1995. http://www.ss.u-tokai.ac.jp/ shirayan/msitr95-28.pdf; K. Shirayanagi, M. Sweedler, A theory of stabilizing algebraic algorithms, Technical Report 95-28, Mathematical Sciences Institute, Cornell University, 92 pp., 1995. http://www.ss.u-tokai.ac.jp/ shirayan/msitr95-28.pdf [20] Shirayanagi, K.; Sweedler, M., Automatic algorithm stabilization, (ISSAC’96 Poster Session Abstracts (1996)), 75-78 [21] Shirayanagi, K.; Sweedler, M., Remarks on automatic algorithm stabilization, Journal of Symbolic Computation, 26, 6, 761-766 (1998) · Zbl 0917.65130 [22] Special issue on algebraic and numerical algorithms, Theoretical Computer Science, 315, 2-3, 307-672 (2004) [23] Special issue on symbolic numeric algebra for polynomials, Journal of Symbolic Computation, 26, 6 (1998) · Zbl 0915.00021 [24] Traverso, C., Hilbert function and the Buchberger algorithm, Journal of Symbolic Computation, 22, 355-376 (1996) · Zbl 0922.13019 [25] C. Traverso, A. Zanoni, Numerical stability and stabilization of Groebner basis computation, in: Proc. ISSAC 2002, pp. 262-269; C. Traverso, A. Zanoni, Numerical stability and stabilization of Groebner basis computation, in: Proc. ISSAC 2002, pp. 262-269 · Zbl 1072.68700 [26] Wang, D.; Zhi, L., Symbolic-Numeric Computation (2007), Birkhäuser: Birkhäuser Basel/Boston 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.