A graph-theoretic model of symmetric givens operations and its implications

D.E Stewart

doi:10.1016/S0024-3795(96)00157-7

Back

A graph-theoretic model of symmetric givens operations and its implications

Journal article

Open access

Peer reviewed

A graph-theoretic model of symmetric givens operations and its implications

D.E Stewart

Linear algebra and its applications, Vol.257(1-3), pp.311-320

1997

DOI: 10.1016/S0024-3795(96)00157-7

Files and links (1)

url

https://doi.org/10.1016/S0024-3795(96)00157-7View

Published (Version of record) Open Access

Abstract

Symmetric Givens operations ( A′ ← GAG T , G a Givens rotation matrix) are a basic tool in many matrix computations, especially for eigenvalue-eigenvector computations. A graph-theoretic model of these operations is given for symmetric matrices, analogous to the graph-theoretic model of Cholesky factorization. Using this model, it is shown that unless there is “accidental cancellation,” it is impossible to reduce a range of different matrix classes to tridiagonal form in o( n 2) Givens operations; these classes include arrowhead matrices, pentadiagonal matrices, and cyclic tridiagonal matrices.

Details

Title: Subtitle: A graph-theoretic model of symmetric givens operations and its implications
Creators: D.E Stewart - Texas A&M University
Resource Type: Journal article
Publication Details: Linear algebra and its applications, Vol.257(1-3), pp.311-320
DOI: 10.1016/S0024-3795(96)00157-7
ISSN: 0024-3795
eISSN: 1873-1856
Publisher: Elsevier Inc
Language: English
Date published: 1997
Academic Unit: Mathematics
Record Identifier: 9984240768002771

Metrics

31 Record Views

2 Times Cited - Web of Science