Semilinear evolution equations arise in many applications ranging from mathematical biology to chemical reactions (e.g., combustion). The significant difficulty in these equations is the nonlinearity, which combined with the discretized diffusion operator leads to large systems of nonlinear equations. To solve these equations, Newton's method or a variant thereof is often used, and to achieve convergence can require individual fine tuning for each case. This can be especially difficult if nothing is known about the solution behavior. In addition, one observes in many cases that not all frequency components are equally important for the solution; the frequency interaction is determined by the nonlinearity. It is therefore of interest to work in frequency space when analyzing the unknown behavior of such problems numerically. We propose in this paper an algorithm which reduces the dimensionality of the nonlinear problems to be solved to a size chosen by the user. The algorithm performs a decomposition in frequency space into subspaces, and an iteration is used to obtain the solution of the original problem from the solutions on the frequency subspaces. We prove linear convergence of the algorithm on unbounded time intervals, a result which is also valid for the stationary case. On bounded time intervals, we show that the new algorithm converges superlinearly, a rate faster than any linear rate. We obtain this result by relating the algorithm to an algorithm of waveform relaxation type. By using time windows, one can thus achieve any linear contraction rate desired. An additional advantage of this algorithm is its inherent parallelism.