AN INVERSE FREE PARALLEL SPECTRAL DIVIDE-AND-CONQUER ALGORITHM FOR NONSYMMETRIC EIGENPROBLEMS

We discuss an inverse-free, highly parallel, spectral divide and conqu er algorithm. It can compute either an invariant subspace of a nonsymm etric matrix A, or a pair of left and right deflating subspaces of a r egular matrix pencil A - lambda B. This algorithm is based on earlier ones of Bulgakov, Godunov and Malyshev, but improves on them in severa l ways. This algorithm only uses easily parallelizable linear algebra building blocks: matrix multiplication and QR decomposition, but not m atrix inversion. Similar parallel algorithms for the nonsymmetric eige nproblem use the matrix sign function, which requires matrix inversion and is faster but can be less stable than the new algorithm.