zbMATH — the first resource for mathematics

Fraction-free algorithm for the computation of diagonal forms matrices over Ore domains using Gröbner bases. (English) Zbl 1245.65051
The authors present a new fraction-free algorithm for the computation of a diagonal form of a matrix over a certain non-commutative Euclidean domain over a computable field with the help of Gröbner bases. They investigate Ore localizations of common operator algebras over \(K[x]\) and use them in the unimodularity analysis of transformation matrices \(U\) and \(V\). Their algorithm, which is implemented in the computer algebra system SINGULAR:PLURAL following the fraction-free strategy, shows impressive performance compared with methods which directly use fractions.
65F30 Other matrix algorithms (MSC2010)
68W30 Symbolic computation and algebraic computation
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
Full Text: DOI arXiv
[1] Apel, J., 1998. Gröbnerbasen in nichtkommutativen Algebren und ihre Anwendung. Dissertation, Universität Leipzig.
[2] Beckermann, B.; Cheng, H.; Labahn, G., Fraction-free row reduction of matrices of ore polynomials, J. symbolic comput., 41, 5, 513-543, (2006) · Zbl 1151.16025
[3] Blinkov, Y.A., Cid, C.F., Gerdt, V.P., Plesken, W., Robertz, D., 2003. The MAPLE package “janet”: II. Linear Partial Differential Equations. In: Proceedings of the 6th International Workshop on Computer Algebra in Scientific Computing. pp. 41-54. http://wwwb.math.rwth-aachen.de/Janet.
[4] Bueso, J.; Gómez-Torrecillas, J.; Verschoren, A., Algorithmic methods in non-commutative algebra, () · Zbl 1063.16054
[5] Cheng, H.; Labahn, G., Modular computation for matrices of ore polynomials, (), 43-66
[6] Chyzak, F.; Quadrat, A.; Robertz, D., \scoremodules: a symbolic package for the study of multidimensional linear systems, (), 233-264 · Zbl 1248.93006
[7] Chyzak, F.; Salvy, B., Non – commutative elimination in ore algebras proves multivariate identities, J. symbolic comput., 26, 2, 187-227, (1998) · Zbl 0944.05006
[8] Cluzeau, T.; Quadrat, A., Factoring and decomposing a class of linear functional systems, Linear algebra appl., 428, 1, 324-381, (2008) · Zbl 1131.15011
[9] Cluzeau, T., Quadrat, A., 2010. Serre’s reduction of linear partial differential systems with holonomic adjoints. Tech. Rep. 7486, INRIA. · Zbl 1252.35016
[10] Cohn, C., Free rings and their relations, (1971), Academic Press · Zbl 0232.16003
[11] Culianez, G., Quadrat, A., 2005. Formes de Hermite et de Jacobson: implementations et applications. Tech. rep., INRIA Sophia Antipolis.
[12] Davies, P., Cheng, H., Labahn, G., 2008. Computing Popov form of general Ore polynomial matrices. In: Proceedings of the Milestones in Computer Algebra (MICA) Conference. pp. 149-156.
[13] Decker, W., Greuel, G.-M., Pfister, G., Schönemann, H., 2011. \scSingular 3-1-3 — A computer algebra system for polynomial computations. http://www.singular.uni-kl.de.
[14] García García, J.I.; García Miranda, J.; Lobillo, F.J., Elimination orderings and localization in PBW algebras, Linear algebra appl., 430, 8-9, 2133-2148, (2009) · Zbl 1213.16039
[15] Gianni, P.; Trager, B.; Zacharias, G., Gröbner bases and primary decomposition of polynomial ideals, J. symbolic comput., 6, 2-3, 149-167, (1988) · Zbl 0667.13008
[16] Greuel, G.-M., Levandovskyy, V., Motsak, O., Schönemann, H., 2010. \scPlural. A \scSingular 3-1 subsystem for computations with non-commutative polynomial algebras. http://www.singular.uni-kl.de.
[17] Grigor’ev, D., Complexity of factoring and calculating the GCD of linear ordinary differential operators, J. symbolic comput., 10, 1, 7-37, (1990) · Zbl 0728.68067
[18] Ilchmann, A.; Mehrmann, V., A behavioral approach to time-varying linear systems. I: general theory, SIAM J. control optim., 44, 5, 1725-1747, (2006) · Zbl 1139.93007
[19] Ilchmann, A.; Nürnberger, I.; Schmale, W., Time-varying polynomial matrix systems, Internat. J. control, 40, 329-362, (1984) · Zbl 0545.93045
[20] Insua, M.A., 2005. Varias perspectives sobre las bases de Gröbner: Forma normal de Smith, Algoritme de Berlekamp y álgebras de Leibniz. Ph.D. Thesis, Universidade de Santiago de Compostela, Spain.
[21] Jacobson, N., The theory of rings, (1943), American Mathematical Society
[22] Kaltofen, E.; Krishnamoorthy, M.S.; Saunders, B.D., Mr. Smith goes to Las Vegas: randomized parallel computation of the Smith normal form of polynomial matrices, (), 317-322 · Zbl 1209.15003
[23] Kredel, H., 1993. Solvable polynomial rings. Shaker. http://krum.rz.uni-mannheim.de/publicatons.html. · Zbl 0790.16027
[24] Levandovskyy, V., 2005. Non-commutative computer algebra for polynomial algebras: Gröbner bases, applications and implementation. Ph.D. Thesis, Universität Kaiserslautern. http://kluedo.ub.uni-kl.de/volltexte/2005/1883/.
[25] Levandovskyy, V.; Schindelar, K., Computing diagonal form and Jacobson normal form of a matrix using Gröbner bases, J. symbolic comput., 46, 5, 595-608, (2011) · Zbl 1210.13029
[26] Levandovskyy, V.; Schönemann, H., Plural — a computer algebra system for noncommutative polynomial algebras, (), 176-183 · Zbl 1072.68681
[27] Leykin, A., 2003. Algorithms in computational algebraic analysis. Ph.D. Dissertation, University of Minnesota. http://scholar.lib.vt.edu/theses/available/etd-03262004-082608/.
[28] Lübeck, F., On the computation of elementary divisors of integer matrices, J. symbolic comput., 33, 1, 57-65, (2002) · Zbl 1017.65037
[29] Middeke, J., 2008. A polynomial-time algorithm for the Jacobson form for matrices of differential operators. Tech. Rep. 2008-13, RISC, J. Kepler University Linz.
[30] Storjohann, A.; Labahn, G., A fast Las Vegas algorithm for computing the Smith normal form of a polynomial matrix, Linear algebra appl., 253, 155-173, (1997) · Zbl 0890.65038
[31] Zariski, O.; Samuel, P., ()
[32] Zerz, E., An algebraic analysis approach to linear time-varying systems, IMA J. math. control inf., 23, 1, 113-126, (2006) · Zbl 1106.93019
[33] Zerz, E., State representations of time-varying linear systems, (), 235-251 · Zbl 1206.93048
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.