The peridynamic (PD) theory is a reformulation of the classical theory of continuum solid mechanics and is particularly suitable for the representation of discontinuities in displacement fields and the description of cracks and their evolution in materials, which the classical partial differential equation (PDE) models tend to fail to apply. However, the PD models yield numerical methods with dense stiffness matrices which requires O(N²) memory and O(N³) computational complexity where N is the number of spatial unknowns. Consequently, the PD models are deemed to be computationally very expensive especially for problems in multiple space dimensions. State-based PD models, which were developed lately, can be treated as a great improvement of the previous bond-based PD models. The state-based PD models have more complicated structures than the bond-based PD models. In this paper we develop a fast collocation method for a state-based linear PD model by exploring the structure of the stiffness matrix of the numerical method. The method has an O(N) memory requirement and computational complexity of O(NlogN) per Krylov subspace iteration. Numerical methods are presented to show the utility of the method.