We study the stability of spatially periodic, nonlinear Vlasov-Poisson equilibria as an eigenproblem in a Fourier-Hermite basis (in the space and velocity variables, respectively) of finite dimension, $N$. When the advection term in Vlasov equation is dominant, the convergence with $N$ of the eigenvalues is rather slow, limiting the applicability of the method. We use the method of spectral deformation introduced in [J. D. Crawford and P. D. Hislop, Ann. Phys. 189, 265 (1989)] to selectively damp the continuum of neutral modes associated with the advection term, thus accelerating convergence. We validate and benchmark the performance of our method by reproducing the kinetic dispersion relation results for linear (spatially homogeneous) equilibria. Finally, we study the stability of a periodic Bernstein-Greene-Kruskal mode with multiple phase space vortices, compare our results with numerical simulations of the Vlasov-Poisson system and show that the initial unstable equilibrium may evolve to different asymptotic states depending on the way it was perturbed.