Parallel algorithms for certain matrix computations (Q1390874)

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.