Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleOutput-sensitive modular algorithms for polynomial matrix normal forms
Author(s) Howard Cheng, George Labahn
TypeArticle in Journal
AbstractWe give modular algorithms to compute row-reduced forms, weak Popov forms, and Popov forms of polynomial matrices, as well as the corresponding unimodular transformation matrices. Our algorithms improve on existing fraction-free algorithms. In each case, we define lucky homomorphisms, determine the appropriate normalization, as well as bound the number of homomorphic images required. The algorithms have the advantage that they are output-sensitive; that is, the number of homomorphic images required depends on the size of the output. Furthermore, there is no need to verify the result by trial division or multiplication. Our algorithms can be used to compute normalized one-sided greatest common divisors and least common multiples of polynomial matrices, along with irreducible matrix-fraction descriptions of matrix rational functions. When our algorithm is used to compute polynomial greatest common divisors, we obtain a new output-sensitive modular algorithm.
KeywordsMatrices, Row-reduced form, Weak Popov form, Popov form, Modular algorithm
URL http://www.sciencedirect.com/science/article/pii/S0747717107000417
JournalJournal of Symbolic Computation
Pages733 - 750
Translation No
Refereed No