The Linear Miminum Mean Square Error (LMMSE) equalizer coefficients of a stationary signal are defined by a Toeplitz system. The Toeplitz structure lends itself to computation in frequency domain, which reduces complexity. In this paper we investigate circulant embedding and circulant approximation methods applied to the preconditioned conjugate gradient (PCG) method and frequency domain equalization. We develop a novel circulant approximation method which improves the performance/complexity tradeoff. All considered algorithms are benchmarked in terms of implementation complexity and capacity achieved by a High Speed Downlink Packet Access (HSDPA) receiver in a multipath fading scenario.