eigenvector computation depends on the mixing time of the underlying Markov chain on the graph, and is given by, $$T_{max} = O\left(\arccos\left(\cfrac{2+c^2 (e^{-1/\tau}-1)}{2}\right)^{-1} \right) +
    O(N)\,, \label{eq:Waveconvfinal}$$ where $\tau$ is the mixing time of the Markov chain. Thus, the wave equation based algorithm has better scaling with $\tau$ for graphs of any size (given by $N$, see Fig. \[ConvComp\]).

![Comparison of convergence rates between the distributed algorithm in [@Cit:kempe] and our proposed wave equation algorithm for $c^{2}=1.99$. The wave equation based algorithm has better scaling with $\tau$ for graphs of any size (given by $N$). The plots are upper bounds on the convergence speed. For more details see [@Cit:cluster2].\[ConvComp\]](TauComp1.eps "fig:"){width="0.85\hsize"}\

The above work is an example of the construction of a state-of-the-art algorithm using dynamical systems theory. This work has also found application in distributed numerical computations [@Cit:Num_klus] and uncertainty quantification [@Cit:UQ_surana]. We now present another example of constructing novel algorithms for NP-hard problems using the theory of nonlinear dynamics and invariant manifold computations.

Novel algorithm construction: invariant manifolds and the traveling salesman problem {#sec:tsp}
====================================================================================

[Overview]{} Recently, dynamical systems theory was used to construct novel algorithms for another iconic NP-hard problem [@Cit:TSP_sahai]. The traveling salesman problem (TSP) has a 