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?

  • 2
    $\begingroup$ @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? $\endgroup$ Aug 2, 2012 at 16:31
  • $\begingroup$ My apologies! I had never seen that notation before. I've changed it back. $\endgroup$ Aug 2, 2012 at 19:36
  • $\begingroup$ 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..."). $\endgroup$ Aug 2, 2012 at 21:50

2 Answers 2


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.

  • $\begingroup$ I think they are saying that $\tilde{O}(n^2)$ is nearly optimal for the entire eigenproblem including eigenvalues. $\endgroup$ Aug 3, 2012 at 17:28
  • $\begingroup$ Sorry, that should be "including eigenvectors." $\endgroup$ Aug 3, 2012 at 17:34
  • 1
    $\begingroup$ Oh no, one more paper I have to read... $\endgroup$ Aug 3, 2012 at 20:20
  • $\begingroup$ @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. $\endgroup$ Aug 3, 2012 at 20:53
  • 1
    $\begingroup$ @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. $\endgroup$ Aug 4, 2012 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.

  • $\begingroup$ 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. $\endgroup$ Aug 3, 2012 at 17:32
  • $\begingroup$ 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. $\endgroup$ Aug 3, 2012 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.