Parallel algorithms for certain matrix computations

complexity of parallel algorithms feedback matrix Lyapunov matrix equation matrix powers pole assignment problem rank matrix problem Sylvester-observer matrix equation

Mathematics Subject Classification ID

Matrix equations and identities (15A24) Numerical optimization and variational techniques (65K10) Parallel numerical computation (65Y05) Controllability (93B05) Pole and zero placement problems (93B55)

Review text

The authors study some nonclassical matrix problems arising in control theory. More precisely they consider the matrix equations \(AX+XA^{T}=C\), \(AX-XB=C\), the pole assignment problem and the problem of testing if the matrix \(W=[B AB \ldots A^{n}B]\) has full row rank. For all these problems parallel algorithms are proposed under the assumption of unbounded and bounded parallelism. The rank matrix problem is studied when \(A\) is a lower Hessenberg matrix. The first algorithm proposed, which is of linear time, avoids computation of matrix powers but needs computing of the determinant of a matrix with no special structure. A second parallel algorithm is also given which takes time \(O(\log^2n)\) on an \(O(nM(n))\) processors PRAM. Given a pair of matrices \((A,B)\), the pole assignment problem is to find a feedback matrix \(F\) such that \(A+BF\) has a desired spectrum. In the single input case, i.e. when \(B=b\) is a vector, a processor efficient parallel algorithm is proposed. The latter does not require that the matrix \(A\) be transformed into Hessenberg form. This allows the authors to demonstrate that the parallel time complexity of the problem is much smaller than linear. The matrix equation \(AX+XA^{T} =-C\), where \(A\) and \(C\) are matrices of \(n\)-th order, is known as the Lyapunov equation. For the solution of this equation in case \(C\) is rank-one symmetric positive semidefinite, two different algorithms are developed. They are characterized by running time \(O(n \log n)\) and are processor efficient. The Sylvester-observer equation is considered in a restricted form \(HX-XL=C\), where \(H\) is an \(n \times n\) Hessenberg matrix, \(C=[O F]\), \(F\) is \(n \times r\) and \(L\) is any matrix satisfying the following two conditions: (i) \(L\) is stable; (ii) \(L\) and \(H\) have no eigenvalues in common. The method proposed here is well suited to fast parallel implementation.

Recommendations

Cites work

Cited in

(24)

Describes a project that uses

Uses Software

Algorithm 432

This page was built for publication: Parallel algorithms for certain matrix computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1390874)