Solution of algebraic riccati equations on wavefront array processors

Abstract

The need for high performance computers has been felt for some time in application areas such as on-line control, system identification and estimation in real-time, complex control system design, etc. Parallel computers appear to be viable alternative in such applications as indicated by the existing schemes for the solution of some control problems on parallel computers. These schemes, however, make use of some special feature specific to a problem. This thesis deals with the efficient solution of a number of control problems under a unified framework. The approach is to identify basic matrix computations common to a variety of control algorithms and devise parallel schemes to speed them up rather than exploit some special feature of a problem. The main focus is on the solution of Algebraic Riccati Equations using these parallel schemes. The Algebraic Riccati Equation (ARE) plays an important role in the optimal estimation and control of linear systems. Solving •the ARE is computationally demanding either when the system size is large or when the ARE is to be solved in real-time. Under such circumstances, parallel computing techniques could be used with advantage. Schur vector method for the solution of AREs has been chosen for parallelization because of its inherent numerical stability. This method is based on finding the Schur vectors of iii the Hamiltonian matrix associated with the Algebraic Riccati Equation. The speed of solution crucially depends upon the speeds of computations such as ordered Schur decomposition, matrix inversion and matrix multiplication. Wavefront Array Processors are well-suited for matrix computations. Owing to the importance of matrix computations in the solution of many control problems - in particular, the solution of AREs - Wavefront Array Processor has been chosen as the candidate architecture. New and efficient schemes for QR-decomposition and matrix multiplication on Wavefront Array Processor are proposed. Suggestions for handling large matrices on smaller array of processors for these computations are also presented. With these schemes as building blocks, a simple and efficient parallel implementation of the QR-algorithm is proposed for obtaining Schur decomposition of a matrix - an important step in the solution of AREs. In this implementation, special attention is paid to the Hessenberg reduction step which is considered to be a roadblock in implementing the QR-algorithm in parallel. A parallel scheme is also proposed for reordering the eigenvalues of a Schur matrix to obtain orthonormal bases for invariant subspaces associated with the desired set of eigenvalues. The schemes proposed in this work provide an elegant framework for the solution of AREs. Also, they furnish the basic building blocks for the solution of important control problems like system identification, state estimation, solution of Lyapunov equations, controllability and observability computations, etc.