Efficient Computer Algebra Algorithms for Polynomial Matrices in Control Design

Title : Efficient Computer Algebra Algorithms for Polynomial Matrices in Control Design
Authors :
Conference : The 3rd Annual Conference on Aerospace Computational Control Vol. I, , pp. 292-293
Date: August 01 - August 01, 1989

The theory of polynomial matrices plays a key role in the design and analysis of multi-input multi-output control and communications systems using frequency domain methods. Examples include coprime factorizations of transfer functions, canonical realizations from matrix fraction descriptions, and the transfer function design of feedback compensators. Typically, such problems abstract in a natural way to the need to solve systems of Diophantine equations (the so-called generalized Bezout equations) or systems of linear equations over polynomials. These and other problems involving polynomial matrices can in turn be reduced to polynomial matrix triangularization procedures, a result which is not surprising given the importance of matrix triangularization techniques in numerical linear algebra. – There, we deal with matrices with entries from a field and Gaussian elimination plays a fundamental role in understanding the triangularization process. In the case of polynomial matrices we are dealing with matrices with entries from a ring for which Gaussian elimination is not defined and triangularization is accomplished by what is quite properly called Euclidean elimination.

 Unfortunately, the numerical stability and sensitivity issues which accompany floatingpoint approaches to Euclidean elimination are not very well understood at present. In this paper we present new algorithms which circumvent entirely such numerical issues through the use of exact, symbolic methods in computer algebra. The use of such error-free algorithms guarantees that the results are accurate to within the precision of the model data-the best that can be hoped. Care must be taken in the design of such algorithms due to the phenomenon of intermediate epression swell, the price paid for freedom from roundoff error. The 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. Moreover, the triangular Hermite form is defined for any matrix with entries from a principal ideal ring and such matrices arise in many practical problems in communications and control, such as the design of convolutional coders and the analysis of quantization effects in linear systems. Due to their symbolic nature, our algorithms apply equally well to such problems since the particular ring involved in a problem can itself be considered as program input data.

Download Full Paper