Computing eigenvalues of normal matrices via complex symmetric matrices

摘要

Computing all eigenvalues of a modest size matrix typically proceeds in two phases. In the first phase, the matrix is transformed to a suitable condensed matrix format, sharing the eigenvalues, and in the second stage the eigenvalues of this condensed matrix are computed. The main purpose of this intermediate matrix is saving valuable computing time. Important subclasses of normal matrices, such as the Hermitian, skew-Hermitian and unitary matrices admit a condensed matrix represented by only O(n) parameters, allowing subsequent low-cost algorithms to compute their eigenvalues. Unfortunately, such a condensed format does not exist for a generic normal matrix.We will show, under modest constraints, that normal matrices also admit a memory cheap intermediate matrix of tridiagonal complex symmetric form. Moreover, we will propose a general approach for computing the eigenvalues of a normal matrix, exploiting thereby the normal complex symmetric structure. An analysis of the computational cost and numerical experiments with respect to the accuracy of the approach are enclosed. In the second part of the manuscript we will investigate the case of nonsimple singular values and propose a theoretical framework for retrieving the eigenvalues. We will, however, also highlight some numerical difficulties inherent to this approach.