research-article

A New Algorithm for General Factorizations of Multivariate Polynomial Matrices

Authors:

Dingkang WangAuthors Info & Claims

ISSAC '17: Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation

Pages 277 - 284

https://doi.org/10.1145/3087604.3087607

Published: 23 July 2017 Publication History

Abstract

We investigate how to factorize a multivariate polynomial matrix into the product of two matrices. There are two major parts. The first is a factorization theorem, which asserts that a multivariate polynomial matrix whose lower order minors satisfy certain conditions admits a matrix factorization. Our theory is a generalization to the previous results given by Lin et.al [16] and Liu et.al [17]. The second is the implementation for factorizing polynomial matrices. According to the proof of factorization theorem, we construct a main algorithm which extends the range of polynomial matrices that can be factorized. In this algorithm, two critical steps are involved in how to compute a zero left prime matrix and a unimodular matrix. Firstly, based on the famous Quillen-Suslin theorem, a new sub-algorithm is presented to obtain a zero left prime matrix by calculating the bases of the syzygies of two low-order polynomial matrices. Experiments show that it is more efficient than the algorithm constructed by Wang and Kwong [31]. Secondly, some auxiliary information provided by the above new sub-algorithm is used to construct a unimodular matrix. As a consequence, the main algorithm extends the application range of the constructive algorithm in [17]. We implement all the algorithms proposed above on the computer algebra system Singular and give a nontrivial example to show the process of the main algorithm.

References

[1]

N. K. Bose. 1995. Multidimensional Systems Theory and Applications. Springer Netherlands.

[2]

C. Charoenlarpnopparut and N. K. Bose. 1999. Multidimensional FIR filter bank design using Grobner bases. IEEE Transactions on Circuits and Systems II Analog and Digital Signal Processing 46, 12 (1999),pages 1475--1486.

[3]

Thomas Cluzeau and Alban Quadrat. 2015. A new insight into Serre's reduction problem. Linear Algebra and Its Applications 483 (2015),pages 40--100.

[4]

Wolfram Decker and Christoph Lossen. 2006. Computing in Algebraic Geometry. Algorithms and Computation in Mathematics, Vol. 16. Springer Berlin Heidelberg.

Digital Library

[5]

David Eisenbud. 1995. Commutative Algebra: With a View Toward Algebraic Geometry. Graduate Texts in Mathematics, Vol. 150. Springer-Verlag.

[6]

Ettore Fornasini and Maria Elena Valcher. 1997. n-D Polynomial Matrices with Applications to Multidimensional Signal Analysis. Multidimensional Systems and Signal Processing 8, 4 (1997),pages 387--408.

Digital Library

[7]

J. Guiver and N. Bose. 1982. Polynomial matrix primitive factorization over arbitrary coefficient field and related results. IEEE Transactions on Circuits and Systems 29, 10 (1982),pages 649--657.

[8]

Thomas Kailath. 1980. Linear systems. Vol. 156. Prentice-Hall Englewood Cliffs, NJ.

[9]

Sigurd Kleon and Ulrich Oberst. 1999. Transfer Operators and State Spaces for Discrete Multidimensional Linear Systems. Acta Applicandae Mathematicae 57, 1 (1999),pages 1--82.

[10]

Martin Kreuzer and Lorenzo Robbiano. 2000. Computational Commutative Algebra 1. Springer Berlin.

Digital Library

[11]

Zhiping Lin. 1988. On matrix fraction descriptions of multivariable linear n-D systems. IEEE Transactions on Circuits and Systems 35, 10 (1988),pages 1317--1322.

[12]

Zhiping Lin. 1999a. Notes on n-D Polynomial Matrix Factorizations. Multidimensional Systems and Signal Processing 10, 4 (1999),pages 379--393.

Digital Library

[13]

Zhiping Lin. 1999b. On syzygy modules for polynomial matrices. Linear Algebra and Its Applications 298, 1--3 (1999),pages 73--86.

[14]

Zhiping Lin. 2001. Further Results on n-D Polynomial Matrix Factorizations. Multidimensional Systems and Signal Processing 12, 2 (2001),pages 199--208.

Digital Library

[15]

Zhiping Lin and N. K. Bose. 2001. A generalization of Serre's conjecture and some related issues. Linear Algebra and Its Applications 338, 1 (2001),pages 125--138.

[16]

Zhiping Lin, Jiang Qian Ying, and Li Xu. 2001. Factorizations for n-D polynomial matrices. Circuits, Systems, and Signal Processing 20, 6 (2001),pages 601--618.

[17]

J. Liu, D. Li, and M. Wang. 2011. On General Factorizations for n-D Polynomial Matrices. Circuits Systems and Signal Processing 30, 3 (2011),pages 553--566.

Digital Library

[18]

J. Liu, D. Li, and L. Zheng. 2014. The Lin-Bose Problem. Circuits and Systems II Express Briefs IEEE Transactions on 61, 1 (2014),pages 41--43.

[19]

J. Liu and M. Wang. 2010. Notes on factor prime factorizations for n-D polynomial matrices. Multidimensional Systems and Signal Processing 21, 1 (2010),pages 87--97.

Digital Library

[20]

Jinwang Liu and Mingsheng Wang. 2015. Further remarks on multivariate polynomial matrix factorizations. Linear Algebra and Its Applications 465, 465 (2015),pages 204--213.

[21]

Alessandro Logar and Bernd Sturmfels. 1992. Algorithms for the Quillen-Suslin theorem. Journal of Algebra 145, 1 (1992),pages 231--239.

[22]

M. Morf, B. C. Levy, and Sun Yuan Kung. 1977. New results in 2-D systems theory, part I: 2-D polynomial matrices, factorization, and coprimeness. Proc. IEEE 65, 6 (1977),pages 861--872.

[23]

HyungJu Park. 1995.bibinfotitleA computational theory of Laurent polynomial rings and multidimensional FIR systems. Ph.D. Dissertation. UNIVERSITY of CALIFORNIA at BERKELEY.

Digital Library

[24]

Hyungju Park and Georg Regensburger. 23--106, 2007. Gröbner Bases in Control Theory and Signal Processing. Radon Series on Computational and Applied Mathematics, Vol. 3. De Gruyter.

[25]

J. F Pommaret. 2001. Solving Bose conjecture on linear multidimensional systems. In Control Conference (ECC), 2001 European. IEEE, Porto, Portugal,pages 1653--1655.

[26]

Daniel Quillen. 1976. Projective modules over polynomial rings. Inventiones mathematicae 36, 1 (1976),pages 167--171.

[27]

Package QuillenSuslin. 2007. A Maple implementation of a constructive version of the Quillen-Suslin Theorem. https://wwwb.math.rwth-aachen.de/QuillenSuslin/. (2007).

[28]

A. A. Suslin. 1976. Projective modules over polynomial rings. Inventiones Mathematicae 36, 1 (1976),pages 167--171.

[29]

M. Wang. 2007. On factor prime factorization for n-D polynomial matrices. IEEE Transactions on Circuits and Systems 54, 6 (2007),pages 1398--1405.

[30]

M. Wang and D. Feng. 2004. On Lin-Bose problem. Linear Algebra and Its Applications 390, 1 (2004),pages 279--285.

[31]

M. Wang and C. P. Kwong. 2005. On multivariate polynomial matrix factorization problems. Mathematics of Control, Signals, and Systems 17, 4 (2005),pages 297--311.

[32]

D. Youla and G. Gnavi. 1979. Notes on n-dimensional System Theory. IEEE Transactions on Circuits and Systems 26, 2 (1979),pages 105--111.

Cited By

Liu JWu TLi D(2022)Smith Form of Triangular Multivariate Polynomial MatrixJournal of Systems Science and Complexity10.1007/s11424-022-1289-z36:1(151-164)Online publication date: 13-Sep-2022
https://doi.org/10.1007/s11424-022-1289-z
Xiao FLu DWang D(2021)Solving Multivariate Polynomial Matrix Diophantine Equations with Gröbner Basis MethodJournal of Systems Science and Complexity10.1007/s11424-021-0072-x35:1(413-426)Online publication date: 4-Feb-2021
https://doi.org/10.1007/s11424-021-0072-x
Lu DWang DXiao F(2020)Factorizations for a class of multivariate polynomial matricesMultidimensional Systems and Signal Processing10.1007/s11045-019-00694-z31:3(989-1004)Online publication date: 1-Jul-2020
https://dl.acm.org/doi/10.1007/s11045-019-00694-z
Show More Cited By

Index Terms

A New Algorithm for General Factorizations of Multivariate Polynomial Matrices
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms

Recommendations

A Property of Modules Over a Polynomial Ring With an Application in Multivariate Polynomial Matrix Factorizations
ISSAC '22: Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation

This paper is concerned with a property of modules over a polynomial ring and its application in multivariate polynomial matrix factorizations. We construct a specific polynomial such that the product of the polynomial and a nonzero vector in a module ...
Further results on the factorization and equivalence for multivariate polynomial matrices
ISSAC '20: Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation

This paper is concerned with the factorization and equivalence problems of multivariate polynomial matrices. We present a new criterion for the existence of matrix factorizations for a class of multivariate polynomial matrices, and prove that these ...
Factorizations for a class of multivariate polynomial matrices
Abstract
This paper investigates how to factorize a class of multivariate polynomial matrices. We prove that an $l \times m$ multivariate polynomial matrix admits a matrix factorization with respect to a given polynomial if the polynomial and all the $(l - 1) \times (l - 1)$ ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '17: Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation

July 2017

466 pages

ISBN:9781450350648

DOI:10.1145/3087604

Editor:
Michael Burr
Clemson University, USA
,
General Chair:
Chee K. Yap
New York University, USA
,
Program Chair:
Mohab Safey El Din
University Pierre et Marie Curie, France

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Natural Science Foundation of China
Chinese Universities Scientific Fund

Conference

ISSAC '17

ISSAC '17: International Symposium on Symbolic and Algebraic Computation

July 23 - 28, 2017

Kaiserslautern, Germany

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
87
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Liu JWu TLi D(2022)Smith Form of Triangular Multivariate Polynomial MatrixJournal of Systems Science and Complexity10.1007/s11424-022-1289-z36:1(151-164)Online publication date: 13-Sep-2022
https://doi.org/10.1007/s11424-022-1289-z
Xiao FLu DWang D(2021)Solving Multivariate Polynomial Matrix Diophantine Equations with Gröbner Basis MethodJournal of Systems Science and Complexity10.1007/s11424-021-0072-x35:1(413-426)Online publication date: 4-Feb-2021
https://doi.org/10.1007/s11424-021-0072-x
Lu DWang DXiao F(2020)Factorizations for a class of multivariate polynomial matricesMultidimensional Systems and Signal Processing10.1007/s11045-019-00694-z31:3(989-1004)Online publication date: 1-Jul-2020
https://dl.acm.org/doi/10.1007/s11045-019-00694-z
Liu JLi DZheng L(2019)Factorization for n-D Polynomial Matrices over Arbitrary Coefficient FieldJournal of Systems Science and Complexity10.1007/s11424-019-8016-433:1(215-229)Online publication date: 26-Dec-2019
https://doi.org/10.1007/s11424-019-8016-4
Kayal NNair VSaha C(2019)Average-case linear matrix factorization and reconstruction of low width algebraic branching programsComputational Complexity10.1007/s00037-019-00189-028:4(749-828)Online publication date: 1-Dec-2019
https://dl.acm.org/doi/10.1007/s00037-019-00189-0

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten