Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Inverse Free Parallel Spectral Divide and Conquer Algorithms for Nonsymmetric Eigenproblems

Zhaojun Bai, James W. Demmel and Ming Gu

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-94-793
February 1994

http://www.eecs.berkeley.edu/Pubs/TechRpts/1994/CSD-94-793.pdf

We discuss two inverse free, highly parallel, spectral divide and conquer algorithms: one for computing an invariant subspace of a nonsymmetric matrix and another one for computing left and right deflating subspaces of a regular matrix pencil A - lambda B. These two closely related algorithms are based on earlier ones of Bulgakov, Godunov and Malyshev, but improve on them in several ways. These algorithms only use easily parallelizable linear algebra building blocks: matrix multiplication and QR decomposition. The existing parallel algorithms for the nonsymmetric eigenproblem use the matrix sign function, which is faster but can be less stable than the new algorithm.


BibTeX citation:

@techreport{Bai:CSD-94-793,
    Author = {Bai, Zhaojun and Demmel, James W. and Gu, Ming},
    Title = {Inverse Free Parallel Spectral Divide and Conquer Algorithms for Nonsymmetric Eigenproblems},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1994},
    Month = {Feb},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1994/5383.html},
    Number = {UCB/CSD-94-793},
    Abstract = {We discuss two inverse free, highly parallel, spectral divide and conquer algorithms: one for computing an invariant subspace of a nonsymmetric matrix and another one for computing left and right deflating subspaces of a regular matrix pencil <i>A</i> - lambda <i>B</i>. These two closely related algorithms are based on earlier ones of Bulgakov, Godunov and Malyshev, but improve on them in several ways. These algorithms only use easily parallelizable linear algebra building blocks: matrix multiplication and QR decomposition. The existing parallel algorithms for the nonsymmetric eigenproblem use the matrix sign function, which is faster but can be less stable than the new algorithm.}
}

EndNote citation:

%0 Report
%A Bai, Zhaojun
%A Demmel, James W.
%A Gu, Ming
%T Inverse Free Parallel Spectral Divide and Conquer Algorithms for Nonsymmetric Eigenproblems
%I EECS Department, University of California, Berkeley
%D 1994
%@ UCB/CSD-94-793
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/1994/5383.html
%F Bai:CSD-94-793