An evolutionary spectral clustering method using a smoothed Laplacian is presented.The incomplete Cholesky decomposition (ICD) reduces runtime from O(N3) to O(N).The memory requirements are decreased from O(N2) to O(N).A stopping criterion using the convergence of cluster assignments is adopted.An efficient procedure to select the number of clusters is presented. Evolutionary spectral clustering (ESC) represents a state-of-the-art algorithm for grouping objects evolving over time. It typically outperforms traditional static clustering by producing clustering results that can adapt to data drifts while being robust to short-term noise. A major drawback of ESC is given by its cubic complexity, e.g. O(N3), and high memory demand, namely O(N2), that make it unfeasible to handle datasets characterized by a large number N of patterns. In this paper, we propose a solution to this issue by presenting the efficient evolutionary spectral clustering algorithm (E2SC). First we introduce the notion of a smoothed graph Laplacian, then we exploit the incomplete Cholesky decomposition (ICD) to construct an approximation of the this smoothed Laplacian and reduce the size of the related eigenvalue problem from N to m, with mN. Furthermore, in contrast to the standard ICD algorithm, a stopping criterion based on the convergence of the cluster assignments after the selection of each pivot is used, which is effective also when there is not a fast decay of the Laplacian spectrum. Overall, the proposed approach scales linearly with respect to the number of input datapoints N and has low memory requirements because only matrices of size Nm and mm are constructed.