  In [McDonald, Pestana and Wathen, \textit{SIAM J. Sci. Comput.}, 40 (2018),
pp. A1012--A1033], a block circulant preconditioner is proposed for all-at-once
linear systems arising from evolutionary partial differential equations, in
which the preconditioned matrix is proven to be diagonalizable and to have
identity-plus-low-rank decomposition in the case of the heat equation. In this
paper, we generalize the block circulant preconditioner by introducing a small
parameter $\epsilon>0$ into the top-right block of the block circulant
preconditioner. The implementation of the generalized preconditioner requires
the same computational complexity as that of the block circulant
one.Theoretically, we prove that (i) the generalization preserves the
diagonalizability and the identity-plus-low-rank decomposition; (ii) all
eigenvalues of the new preconditioned matrix are clustered at 1 for
sufficiently small $\epsilon$; (iii) GMRES method for the preconditioned system
has a linear convergence rate independent of size of the linear system when
$\epsilon$ is taken to be smaller than or comparable to square root of
time-step size. Numerical results are reported to confirm the efficiency of the
proposed preconditioner and to show that the generalization improves the
performance of block circulant preconditioner.
