×

An extended GCRD algorithm for parametric univariate polynomial matrices and application to parametric Smith form. (English) Zbl 1502.13068

This paper (extension of [T. Kailath, Linear systems. Englewood Cliffs, N.J.: Prentice-Hall, Inc. (1980; Zbl 0454.93001)]) introduces an algorithm for computing the extended GCRD of parametric univariate matrices.This entails a discussion of parameters such that for each different value, there is a GCRD. Sections 2 and 3 introduce the problem for univariate polynomial matrices. As one can expect, the computation of GCRD implies the computing a minimal Gröbner basis for the submodule generated by the rows of the given matrices (see Theorems 9 and 10); furthermore, the computation of such a minimal basis allows to develop another algorithm for computed the extended GCRD (see Theorem 12). Section 4 introduce the new contributions. The authors extend the ideas introduced in Section 3, in order to compute the extended GCRD of parametric univariate matrices. Logically, usual Gröbner bases must be replaced by comprehensive Gröbner systems which provide the discussion of parameters. Finally, Section 5 introduced the computation of Smith normal form.

MSC:

13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
15A54 Matrices over function rings in one or more variables
68W30 Symbolic computation and algebraic computation

Citations:

Zbl 0454.93001
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abramov, S.; Kvashenko, K., On the greatest common divisor of polynomials which depend on a parameter, (Proceedings of the 1993 ACM International Symposium on Symbolic and Algebraic Computation (1993)), 152-156 · Zbl 0925.13009
[2] Ayad, A., Complexity of algorithms for computing greatest common divisors of parametric univariate polynomials, Int. J. Algebra, 4, 4, 173-188 (2010) · Zbl 1205.11133
[3] Bächler, T.; Gerdt, V.; Lange-Hegermann, M.; Robertz, D., Algorithmic Thomas decomposition of algebraic and differential systems, J. Symb. Comput., 47, 10, 1233-1266 (2012) · Zbl 1315.35013
[4] Barnett, S., Matrices in Control Theory: with Applications to Linear Programming (1971), Van Nostrand Reinhold · Zbl 0245.93002
[5] Beckermann, B.; Labahn, G., Fraction-free computation of matrix rational interpolants and matrix GCDs, SIAM J. Matrix Anal. Appl., 22, 1, 114-144 (2000) · Zbl 0973.65007
[6] Beckermann, B.; Labahn, G.; Villard, G., Shifted normal forms of polynomial matrices, (Proceedings of the 1999 ACM International Symposium on Symbolic and Algebraic Computation (1999)), 189-196
[7] Bradley, G., Algorithms for Hermite and Smith normal matrices and linear Diophantine equations, Math. Comput., 25, 116, 897-907 (1971) · Zbl 0233.65023
[8] Brent, R. P.; Kung, H. T., Systolic VLSI arrays for polynomial GCD computation, IEEE Trans. Comput., 100, 8, 731-736 (1984) · Zbl 0542.94043
[9] Brown, W., On Euclid’s algorithm and the computation of polynomial greatest common divisors, J. ACM, 18, 4, 478-504 (1971) · Zbl 0226.65040
[10] Chen, C.; Maza, M., Algorithms for computing triangular decomposition of polynomial systems, J. Symb. Comput., 47, 6, 610-642 (2012) · Zbl 1264.12011
[11] Chou, S., Mechanical Geometry Theorem Proving, Vol. 41 (1988), Springer Science and Business Media · Zbl 0661.14037
[12] Corless, R.; Maza, M.; Thornton, S., Jordan canonical form with parameters from Frobenius form with parameters, (International Conference on Mathematical Aspects of Computer and Information Sciences (2017)), 179-194 · Zbl 1504.65109
[13] Emre, E.; Silverman, L., New criteria and system theoretic interpretations for relatively prime polynomial matrices, IEEE Trans. Autom. Control, 22, 2, 239-242 (1976) · Zbl 0396.93019
[14] Gantmacher, F. R., The Theory of Matrices, Vol. 1 (1959), American Mathematical Society · Zbl 0085.01001
[15] Geddes, K. O.; Czapor, S. R.; Labahn, G., Algorithms for Computer Algebra (1992), Springer Science & Business Media · Zbl 0805.68072
[16] Gianni, P.; Trager, B., GCDs and factoring multivariate polynomials using Gröbner bases, (European Conference on Computer Algebra (1985), Springer), 409-410
[17] Hippe, P.; Deutscher, J., Polynomial Matrix Fraction Descriptions (2009), Springer: Springer London
[18] Insua, M., Varias perspectives sobre las bases de Gröbner: Forma normal de Smith, Algoritme de Berlekamp y álgebras de Leibniz (2005), Universidade de Santiago de Compostela: Universidade de Santiago de Compostela Spain, Ph.D. thesis
[19] Kai, H.; Noda, M.-T., Hybrid rational approximation and its applications, Reliab. Comput., 6, 429-438 (2000) · Zbl 0970.65010
[20] Kailath, T., Linear Systems, Vol. 156 (1980), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0454.93001
[21] Kalkbrener, M., On the stability of Gröbner bases under specializations, J. Symb. Comput., 24, 1, 51-58 (1997) · Zbl 1054.13502
[22] Kapur, D.; Lu, D.; Monagan, M.; Sun, Y.; Wang, D., An efficient algorithm for computing parametric multivariate polynomial GCD, (Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation (2018)), 239-246 · Zbl 1467.13047
[23] Kapur, D.; Sun, Y.; Wang, D., A new algorithm for computing comprehensive Gröbner systems, (Proceedings of the 2010 ACM International Symposium on Symbolic and Algebraic Computation (2010)), 29-36 · Zbl 1321.68533
[24] Kapur, D.; Sun, Y.; Wang, D., An efficient algorithm for computing a comprehensive Gröbner system of a parametric polynomial system, J. Symb. Comput., 49, 27-44 (2013) · Zbl 1255.13018
[25] Kung, S.; Kailath, T.; Morf, M., A generalized resultant matrix for polynomial matrices, (IEEE Conference on Decision and Control Including the 15th Symposium on Adaptive Processes (1976)), 892-895
[26] Montes, A., A new algorithm for discussing Gröbner bases with parameters, J. Symb. Comput., 33, 2, 183-208 (2002) · Zbl 1068.13016
[27] Moses, J.; Yun, D., The EZ GCD algorithm, (Proceedings of the ACM Annual Conference (1973), ACM), 159-166
[28] Nabeshima, K., PGB: a package for computing parametric Gröbner and related objects, ACM Commun. Comput. Algebra, 41, 3, 104-105 (2007)
[29] Nabeshima, K., A speed-up of the algorithm for computing comprehensive Gröbner systems, (Proceedings of the 2007 ACM International Symposium on Symbolic and Algebraic Computation (2007)), 299-306 · Zbl 1190.13025
[30] Nabeshima, K., On the computation of parametric Gröbner bases for modules and syzygies, Jpn. J. Ind. Appl. Math., 27, 2, 217-238 (2010) · Zbl 1204.13019
[31] Nagasaka, K., Parametric greatest common divisors using comprehensive Gröbner systems, (Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation (2017)), 341-348 · Zbl 1458.13037
[32] Norman, C., Finitely Generated Abelian Groups and Similarity of Matrices over a Field (2012), Springer Science & Business Media · Zbl 1242.20002
[33] Pace, I.; Barnett, S., Efficient algorithms for linear system calculations. I: Smith form and common divisor of polynomial matrices, Int. J. Syst. Sci., 403-411 (1974) · Zbl 0287.93005
[34] Rosenbrock, H., State-Space and Multivariable Theory (1970), Nelson · Zbl 0246.93010
[35] Sasaki, T.; Suzuki, M., Three new algorithms for multivariate polynomial GCD, J. Symb. Comput., 13, 4, 395-411 (1992) · Zbl 0761.12005
[36] Suzuki, A.; Sato, Y., An alternative approach to comprehensive Gröbner bases, J. Symb. Comput., 36, 3, 649-667 (2002) · Zbl 1053.13013
[37] Suzuki, A.; Sato, Y., A simple algorithm to compute comprehensive Gröbner bases using Gröbner bases, (Proceedings of the 2006 ACM International Symposium on Symbolic and Algebraic Computation (2006)), 326-331 · Zbl 1356.13040
[38] Wang, D.; Wang, H.; Xiao, F., An extended GCD algorithm for parametric univariate polynomials and application to parametric Smith normal form, (Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation (2020)), 442-449 · Zbl 07300103
[39] Weispfenning, V., Comprehensive Gröbner bases, J. Symb. Comput., 14, 1, 1-29 (1992) · Zbl 0784.13013
[40] Wolovich, W. A., Equivalence and invariants in linear multivariable systems, (Joint Automatic Control Conference, vol. 12 (1974)), 177-185
[41] Zippel, R., Probabilistic algorithms for sparse polynomials, (Proceedings of the EUROSAM’79 (1979), Springer-Verlag), 216-226 · Zbl 0418.68040
[42] Zippel, R., Effective Polynomial Computation, Vol. 241 (1993), 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.