Can all eigenvalues of a Hermitian Toeplitz matrix be computed in $\tilde{O}(n)$ time?

I know there are "superfast" $O(n \log^p n)$ algorithms for solving Toeplitz linear systems. Is it possible to compute all eigenvalues of such a matrix with the same complexity?

• @David: You changed $\tilde{O}$ to $\mathcal{O}$, but $\tilde{O}(n)$ is standard notation for linear times a polylog factor. I haven't seen the mathcal usage before; is it also supposed to indicate the polylog? Aug 2 '12 at 16:31
• My apologies! I had never seen that notation before. I've changed it back. Aug 2 '12 at 19:36
• No worries. I often feel guilty using $\tilde{O}$ anyways, since it feels like lazy marketing ("Look at my nearly linear time algorithm, not the small print..."). Aug 2 '12 at 21:50

The results in The Complexity of the Matrix Eigenproblem (STOC '99, Proceedings of the thirty-first annual ACM symposium on theory of computing, p. 507-516) indicate that the best known algorithms for the Hermitian Toeplitz case are $$\tilde{O}(n^{2})$$, based on Section 1.2. In this section, the eigenproblem is divided into three stages (Section 1.2, pages 3 and 4 of the article):

a) the reduction of the eigenproblem for a given matrix to the one for a matrix in a canonical form (that is, for a Frobenius matrix, for a block triangular or block diagonal matrix with Frobenius diagonal blocks or for a tridiagonal matrix); as a by-product of this stage, the coefficients of the characteristic polynomial $$c_A(x)$$ of the original input matrix $$A$$ are output or become available readily, in $$O(n)$$ additional ops

b) the approximation of the eigenvalues of $$A$$ as the zeros of $$c_A(x)$$, and

c) the computational of the eigenspaces of the approximated eigenvalues, by exploiting the available reduction of $$A$$ to the canonical form.

The lower bound on the arithmetic complexity of stage (a) stated in the article fror general matrices is $$\Omega(M(n))$$, where $$M(n)$$ is the arithmetic complexity of matrix-matrix multiplication. I know that the arithmetic complexity of LU decomposition is equivalent to the arithmetic complexity of matrix-matrix multiplication, but I don't know if it is true for individual linear solves. I don't believe it's true. Since $$M(n)$$ is $$\Omega(n^{2})$$ (even for Toeplitz matrices, from what I can tell), calculating the eigenvalues (stages (a) and (b)) must be $$\Omega(n^{2})$$, based on the results of the article.

In order to obtain a $$\tilde{O}(n)$$ algorithm, the limiting step is calculating the characteristic polynomial in $$\tilde{O}(n)$$ time. How one does that, I'm not sure, but the output of stage (a) can't be the limiting step because Frobenius, block Frobenius, and tridiagonal matrices can all be specified with $$O(n)$$ data. I don't have access to the source cited along with the $$\Omega(n^{2})$$ bound, so I can only speculate that the limiting step there is a sequence of matrix-matrix multiplies associated with elementary matrix operations to reduce the given matrix to one of the listed canonical forms, in which case the "output-limiting step" is in intermediate calculations.

The fastest known algorithm is one by Ng and Trench (1997 technical report), which calculates the eigenvalues in $$\tilde{O}(n^{2})$$ time in serial and $$\tilde{O}(n)$$ time in parallel.

• I think they are saying that $\tilde{O}(n^2)$ is nearly optimal for the entire eigenproblem including eigenvalues. Aug 3 '12 at 17:28
• Sorry, that should be "including eigenvectors." Aug 3 '12 at 17:34
• Oh no, one more paper I have to read... Aug 3 '12 at 20:20
• @GeoffreyIrving: Look at Section 1.2 of the paper, where they separate the problem into three stages, (a) through (c). Calculating the eigenvalues is equivalent to solving stages (a) and (b); Section 1.2 gives the computational complexity of each stage, which is what I used to write my answer. Aug 3 '12 at 20:53
• @Geoffrey: Frobenius, block Frobenius, and tridiagonal matrices can all be specified using $O(n)$ data, so output data (at least at the end of that stage) is not an issue; rather, you need a fast way (i.e., $\tilde{O}(n)$ algorithm) to calculate the coefficients of the characteristic polynomial. Without the source, it's not immediately clear to me that the $\Omega(M(n))$ bound excludes that possibility, but the "fast algorithms" I've seen from searching around are all $\tilde{O}(n^{2})$. It's not a proof, but the evidence suggests that a $\tilde{O}(n)$ algorithm is unlikely. Aug 4 '12 at 4:49

My first idea for computing the eigenvalues of a Hermitian Toeplitz matrix would be to use the fast $O(n \log n)$ matrix multiplication for Toeplitz matrices together with the Lanczos algorithm to get a tridiagonal matrix. The complexity of this procedure is $O(n^2 \log n)$, and it isn't even numerically robust. I vaguely remember that Marlis Hochbruck has written a paper on look-ahead algorithms related to Toeplitz matrices, but I think these were intended to ensure robustness for non-Hermitian Toeplitz systems, not to reduce the complexity.

My conclusion is that already a proof that there exists a numerically robust $\tilde{O}(n^2)$ algorithm for computing all eigenvalues (and eigenvectors) of a Hermitian Toeplitz matrix would be a nice thing to have. I also wonder how useful it would be to able to compute the eigenvalues in $\tilde{O}(n)$ time, if computing the corresponding eigenvectors takes $O(n^2)$ time.

• A more useful version would be an $\tilde{O}(n)$ algorithm that constructs both eigenvalues and a $\tilde{O}(n)$ eigenvector action operator. This is the case for circulant matrices, for example. Aug 3 '12 at 17:32
• Well, the eigenvectors of a circulant matrix are known beforehand, so you don't really need to compute them. I guess the mentioned "superfast" algorithms will take $\tilde{O}(n)$ time for solving a Toeplitz linear system for a single right hand side vector, which is "superfast", but still not really unexpected. Perhaps there exists a way to compute the characteristic polynomial of a Toeplitz matrix in $\tilde{O}(n)$ time, but I wouldn't consider this to be very useful. On the other hand, computing the complete eigenvalue decomposition in $\tilde{O}(n)$ time would be really unexpected. Aug 3 '12 at 20:16