Parallel algorithms for certain matrix computations
type: Item
instance of: scholarly article
title: Parallel algorithms for certain matrix computations
zbMATH Open document ID: 0901.65029
DOI: 10.1016/S0304-3975(97)83810-8
author: Bruno Codenotti
author: Biswa N. Datta
author: Karabi Datta
author: Mauro Leoncini
published in: Theoretical Computer Science
publication date: 1998-07-22T00:00:00Z
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.
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 65K10
Mathematics Subject Classification ID: 93B05
Mathematics Subject Classification ID: 65Y05
Mathematics Subject Classification ID: 93B55
Mathematics Subject Classification ID: 15A24
zbMATH DE Number: 1177601
zbMATH Keywords: pole assignment problem
zbMATH Keywords: Lyapunov matrix equation
zbMATH Keywords: Sylvester-observer matrix equation
zbMATH Keywords: complexity of parallel algorithms
zbMATH Keywords: rank matrix problem
zbMATH Keywords: matrix powers
zbMATH Keywords: feedback matrix
reviewed by: Neli Dimitrova
describes a project that uses: Algorithm 432
MaRDI profile type: Publication
cites work: Trends in large space structure control theory: Fondest hopes, wildest dreams
cites work: Algorithm 432 [C2]: Solution of the matrix equation AX + XB = C [F4]
cites work: Pole assignment via Sylvester's equation
cites work: Parallel Solution of Certain Toeplitz Linear Systems
cites work: Q4314299
cites work: Parallel algebraic reductions among numerical problems
cites work: A new criterion of controllability
cites work: An algorithm for computing powers of a Hessenberg matrix and its applications
cites work: The matrix equation \(XA=A^ TX\) and an associated algorithm for solving the inertia and stability problems
cites work: Q3139556
cites work: Reduced order observers: A new algorithm and proof
cites work: A Hessenberg-Schur method for the problem AX + XB= C
cites work: Q3359644
cites work: A Survey of Parallel Algorithms in Numerical Linear Algebra
cites work: Computing powers of arbitrary Hessenberg matrices
cites work: Q4385522
cites work: A complexity theory of efficient parallel algorithms
cites work: Complexity of parallel matrix computations
cites work: On Stable Parallel Linear System Solvers
cites work: On pure structure of dynamic systems
cites work: A Schur method for pole assignment
cites work: Q5674306
full work available at URL: s0304-3975(97)83810-8
OpenAlex ID: W2084098088
Recommended article: Q3998906
Recommended article: Q4040698
Recommended article: Parallelism in Matrix Computations
Recommended article: Q3349857
Recommended article: Parallel algorithms and architectures for matrix multiplication
Recommended article: Q3995472
Recommended article: Recursive algorithms of parallel matrix computations
Recommended article: Q4318761
Recommended article: Q4288328
Recommended article: Complexity of parallel matrix computations
description: scientific article; zbMATH DE number 1177601