The complexity of performing matrix computations, such as solving a linear system, inverting a nonsingular matrix or computing its rank, has received a lot of attention by both the theory and the scientific computing communities. In this paper we address some “nonclassical” matrix problems that find extensive applications, notably in control theory. More precisely, we studythe matrix equations AX +XA^T = C and AX - XB = C, the “inverse” of the eigenvalue problem (called pole assignment), and the problem of testing whether the matrix [B AB ... A^nB] has full row rank. For these problems we show two kinds of PRAM algorithms: on one side very fast, i.e. polylog time, algorithms and on the other side almost linear time and processorefficient algorithms. In the latter case, the algorithms rely on basic matrix computations that can be performed efficiently also on realistic machine models.

Parallel Algorithms for Certain Matrix Computations / B., Codenotti; B. N., Datta; K., Datta; Leoncini, Mauro. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 180:(1997), pp. 287-308.

Parallel Algorithms for Certain Matrix Computations

LEONCINI, Mauro
1997

Abstract

The complexity of performing matrix computations, such as solving a linear system, inverting a nonsingular matrix or computing its rank, has received a lot of attention by both the theory and the scientific computing communities. In this paper we address some “nonclassical” matrix problems that find extensive applications, notably in control theory. More precisely, we studythe matrix equations AX +XA^T = C and AX - XB = C, the “inverse” of the eigenvalue problem (called pole assignment), and the problem of testing whether the matrix [B AB ... A^nB] has full row rank. For these problems we show two kinds of PRAM algorithms: on one side very fast, i.e. polylog time, algorithms and on the other side almost linear time and processorefficient algorithms. In the latter case, the algorithms rely on basic matrix computations that can be performed efficiently also on realistic machine models.
180
287
308
Parallel Algorithms for Certain Matrix Computations / B., Codenotti; B. N., Datta; K., Datta; Leoncini, Mauro. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 180:(1997), pp. 287-308.
B., Codenotti; B. N., Datta; K., Datta; Leoncini, Mauro
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11380/454043
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact