Fast Algorithms for the Triangularization of Polynomial Matrices

The theory of polynomial matrices plays a key role in the design and analysis of multi-input-multi-output control systems. More generally, matrices with entries from various principal ideal rings arise in many practical problems in communications and control, such as the design of convolutional coders and the analysis of computational aspects which accompany such matrices are not widely appreciated at present. Indeed, one popularly held belief is that polynomial matrix problems are merely "big" linear algebra problems, but are otherwise essentially straightforward from a numerical standpoint. However, time and again, when confronted by real-world data, the best algorithms of linear algebra fail miserably despite meticulous program design and use of multiple precision floating-point arithmetic. We will describe the nature of this unexpectedly bad behavior and present new algorithms which circumvent it entirely through the use of exact, symbolic methods in computer algebra. Emphasis will be placed on efficient algorithms to compute exact Hermite forms for polynomial matrices because this triangularization procedure is central to a large variety of algorithms important in the design of control and communication systems