The fast and accurate propagation of general optical fields in free space is still a challenging task. Most of the standard algorithms are either fast or accurate. In the paper we introduce a new algorithm for the fast propagation of non-paraxial vectorial optical fields without further physical approximations. The method is based on decomposing highly divergent (non-paraxial) fields into subfields with small divergence. These subfields can then be propagated by a new semi-analytical spectrum of plane waves (SPW) operator using fast Fourier transformations. In the target plane, all propagated subfields are added coherently. Compared to the standard SPW operator, the numerical effort is reduced drastically due to the analytical handling of linear phase terms arising after the decomposition of the fields. Numerical results are presented for two examples demonstrating the efficiency and the accuracy of the new method.