In the vibration analysis of high speed trains arises such a palindromic quadratic eigenvalue problem (PQEP) (λ2AT + λQ + A)z = 0, where A; Q ϵ Cn×n have special structures: both Q and A are m × m block matrices with each block being k × k (thus n = m × k), and Q is complex symmetric and tridiagonal block-Toeplitz, and A has only one nonzero block in the (1;m)th block position which is the same as the subdiagonal block of Q. This PQEP has eigenvalues 0 and 1 each of multiplicity (m-1)k just by examining A, but it is its remaining 2k eigenvalues, usually nonzero and finite but with an extreme wide range in magnitude, that are of interest. The problem is notoriously diffcult numerically. Earlier methods that seek to de ate eigenvalues 0 and 1 first often produce eigenvalues that are too inaccurate to be useful due to the large errors introduced in the de ation process. The solvent approach proposed by Guo and Lin in 2010 changed the situation because it can deliver sufficiently accurate eigenvalues. In this paper, we propose a fast algorithm along the line of the solvent approach. The theoretical foundation of our algorithm is the connection we establish here between this fast train PQEP and a k×k PQEP defined by the subblocks of A and Q without any computational work. This connection lends itself to a fast algorithm: solve the k ×k PQEP and then use its eigenpairs to recover the eigenpairs for the original fast train PQEP. The so-called α-structured backward error analysis that preserves all possible structures in the fast train PQEP to the extreme is studied. Finally numerical examples are presented to show the effectiveness of the new fast algorithm.