Highly parallel recursive/iterative Toeplitz eigenspace decomposition [array processing]

A highly parallel algorithm is presented for the Hermitian Toeplitz eigenproblem. It computes recursively, in increasing order, the complete eigendecompositions of the successive submatrices contained in the original matrix. At each order, a number of independent, structurally identical, nonlinear problems is solved in parallel, facilitating fast implementation. The eigenvalues are found with a constrained iterative Newton scheme, and the eigenvectors are obtained by solving Toeplitz systems. In the multiple minimum eigenvalue case, eigenvector information found at the rank before is used to identify all except one of the eigenvectors associated with the multiple eigenvalue instantaneously. The final eigenvector is found by deflation. The performance of the algorithm is evaluated in terms of eigenpair accuracy