×

A factorization algorithm for \(G\)-algebras and its applications. (English) Zbl 1387.13060

The authors consider the problem of factoring polynomials in \(G\)-algebras, which have rewrite rules \(x_jx_i=c_{ij}x_ix_j+d_{ij}\) where the \(c_{ij}\) are units of a field and the \(d_{ij}\) are polynomials over the same field which, when nonzero, have leading monomial smaller than \(x_ix_j\). (Of note is the discussion on p. 3 of the different meanings of factorization.)
The main result leads to Algorithm 1, which produces all finite factorizations of a polynomial over a \(G\)-algebra, which is a finite factorization domain. It sets up an ansatz \(a\cdot b=g\), then computes a Gröbner basis of the ideal generated by the coefficients of \(a\cdot b-g\). (An “ansatz” is an educated guess.) When the basis indicates a solution, the algorithm saves it and later factors the factors recursively to find irreducible factorizations.
The authors prove the algorithm’s asymptotic complexity. A library that implements the algorithm for Singular (Plural) is provided online.
This algorithm allows them to develop a second algorithm to compute factorized Gröbner bases for \(G\)-algebras, also implemented as a library for Singular (Plural). While complexity is not proved in this case, the authors point out that the algorithm must compute a (left) Gröbner basis, and this is already known to be double exponential in the number of variables.
Throughout the article, the authors refer to applications and work through numerous examples.

MSC:

13P05 Polynomials, factorization in commutative rings
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Apel, J., Gröbnerbasen in nichtkommutativen Algebren und ihre Anwendung (1988), Universität Leipzig, Dissertation · Zbl 0716.16001
[2] Aschenbrenner, M.; Leykin, A., Degree bounds for Gröbner bases in algebras of solvable type, J. Pure Appl. Algebra, 213, 8, 1578-1605 (2009) · Zbl 1166.13032
[3] Bell, J. P.; Heinle, A.; Levandovskyy, V., On noncommutative finite factorization domains, Trans. Am. Math. Soc., 369, 2675-2695 (2017) · Zbl 1392.16033
[4] Buchberger, B., Introduction to Gröbner bases, (Gröbner Bases and Applications (1997), Springer: Springer Berlin), 3-31 · Zbl 0941.13017
[5] Bueso, J.; Gómez-Torrecillas, J.; Lobillo, F., Re-filtering and exactness of the Gelfand-Kirillov dimension, Bull. Sci. Math., 125, 8, 689-715 (2001) · Zbl 1006.16023
[6] Bueso, J.; Gómez-Torrecillas, J.; Verschoren, A., Algorithmic Methods in Non-commutative Algebra. Applications to Quantum Groups (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 1063.16054
[7] Caruso, F., Factorization of non-commutative polynomials (2010), arXiv preprint
[8] Cohn, P., Unique factorization domains, Am. Math. Mon., 80, 1, 1-18 (1973) · Zbl 0256.13011
[9] Cohn, P. M., Free Ideal Rings and Localization in General Rings, vol. 3 (2006), Cambridge University Press · Zbl 1125.16019
[10] Czapor, S. R., Solving algebraic equations: combining Buchberger’s algorithm with multivariate factorization, J. Symb. Comput., 7, 1, 49-53 (1989) · Zbl 0668.68033
[11] Czapor, S. R., Solving algebraic equations via Buchberger’s algorithm, (Eurocal’87 (1989), Springer), 260-269 · Zbl 1209.13002
[12] Davenport, J. H., Looking at a Set of Equations (1987), School of Mathematical Sciences, The University of Bath, Technical report
[13] Decker, W.; Greuel, G.-M.; Pfister, G.; Schönemann, H., Singular 4-0-2 — a computer algebra system for polynomial computations (2015)
[14] Dixmier, J., Enveloping Algebras (1977) · Zbl 0366.17007
[15] Faugere, J.-C.; Gianni, P.; Lazard, D.; Mora, T., Efficient computation of zero-dimensional Gröbner bases by change of ordering, J. Symb. Comput., 16, 4, 329-344 (1993) · Zbl 0805.13007
[16] Giesbrecht, M.; Heinle, A.; Levandovskyy, V., Factoring linear differential operators in \(n\) variables, (Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (2014), ACM), 194-201 · Zbl 1325.68280
[17] Giesbrecht, M.; Heinle, A.; Levandovskyy, V., Factoring linear partial differential operators in \(n\) variables, J. Symb. Comput., 75, 127-148 (2016) · Zbl 1335.68302
[18] Gräbe, H.-G., On factorized Gröbner bases, (Computer Algebra in Science and Engineering (1995), World Scientific), 77-89
[19] Gräbe, H.-G., Triangular Systems and Factorized Gröbner Bases (1995), Springer · Zbl 0908.13018
[20] Greuel, G.-M.; Levandovskyy, V.; Motsak, A.; Schönemann, H., Plural. A Singular 4-1 Subsystem for Computations with Non-commutative Polynomial Algebras (2016), Centre for Computer Algebra, TU Kaiserslautern
[21] Hearn, A. C., Reduce user’s manual, version 3.8 (2004)
[22] Heinle, A.; Levandovskyy, V., Factorization of \(Z\)-homogeneous polynomials in the first (q)-Weyl algebra, (LNM (2017), Springer), In press · Zbl 1400.16001
[23] Jacobson, N., The Theory of Rings (1943), American Mathematical Society
[24] Kandri-Rody, A.; Weispfenning, V., Non-commutative Gröbner bases in algebras of solvable type, J. Symb. Comput., 9, 1, 1-26 (1990) · Zbl 0715.16010
[25] Lakshman, Y. N., On the complexity of computing a Gröbner basis for the radical of a zero dimensional ideal, (Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing (1990), ACM), 555-563
[26] Lakshman, Y. N., A single exponential bound on the complexity of computing Gröbner bases of zero dimensional ideals, (Effective Methods in Algebraic Geometry (1991), Springer), 227-234 · Zbl 0734.13017
[27] Lakshman, Y. N.; Lazard, D., On the complexity of zero-dimensional algebraic systems, (Effective Methods in Algebraic Geometry (1991), Springer), 217-225 · Zbl 0733.13015
[28] Langemyr, L., Algorithms for a multiple algebraic extension, (Effective Methods in Algebraic Geometry (1991), Springer), 235-248 · Zbl 0741.11053
[29] Lazard, D., Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations, (European Conference on Computer Algebra (1983), Springer), 146-156 · Zbl 0539.13002
[30] Lazard, D., Solving zero-dimensional algebraic systems, J. Symb. Comput., 13, 2, 117-131 (1992) · Zbl 0753.13012
[31] Levandovskyy, V., Non-commutative Computer Algebra for Polynomial Algebras: Gröbner Bases, Applications and Implementation (2005), Universität Kaiserslautern, Doctoral Thesis
[32] Li, H., Noncommutative Gröbner Bases and Filtered-Graded Transfer (2002), Springer · Zbl 1050.16022
[33] Mayr, E. W.; Meyer, A. R., The complexity of the word problems for commutative semigroups and polynomial ideals, Adv. Math., 46, 3, 305-329 (1982) · Zbl 0506.03007
[34] Möller, H. M., On decomposing systems of polynomial equations with finitely many solutions, Appl. Algebra Eng. Commun. Comput., 4, 4, 217-230 (1993) · Zbl 0793.13013
[35] Mori, K.; Iida, S., Factorization of noncommutative polynomials, IPSJ J., 34, 11, 2431-2442 (1993)
[36] Seiler, W. M., Involution. The Formal Theory of Differential Equations and Its Applications in Computer Algebra, Algorithms Comput. Math., vol. 24 (2010), Springer: Springer Berlin · Zbl 1205.35003
[37] Tsai, H., Algorithms for Algebraic Analysis (2000), University of California at Berkeley, Ph.D. thesis
[38] Tsai, H., Weyl closure of a linear differential operator, J. Symb. Comput., 29, 747-775 (2000) · Zbl 1008.16026
[39] Zhang, Y., Contraction of Ore ideals with applications, (Proceedings of the 41th International Symposium on Symbolic and Algebraic Computation (2016), ACM), 413-420 · Zbl 1361.13011
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.