  Fast, reliable orbital evolutions of compact objects around massive black
holes will be needed as input for gravitational wave search algorithms in the
data stream generated by the planned Laser Interferometer Space Antenna (LISA).
Currently, the state of the art is a time-domain code by [Phys. Rev. D{\bf 81},
084021, (2010)] that computes the gravitational self-force on a point-particle
in an eccentric orbit around a Schwarzschild black hole. Currently, time-domain
codes take up to a few days to compute just one point in parameter space. In a
series of articles, we advocate the use of a frequency-domain approach to the
problem of gravitational self-force (GSF) with the ultimate goal of orbital
evolution in mind. Here, we compute the GSF for a particle in a circular orbit
in Schwarzschild spacetime. We solve the linearized Einstein equations for the
metric perturbation in Lorenz gauge. Our frequency-domain code reproduces the
time-domain results for the GSF up to $\sim 1000$ times faster for small
orbital radii. In forthcoming companion papers, we will generalize our
frequency-domain methods to include bound (eccentric) orbits in Schwarzschild
and (eventually) Kerr spacetimes for computing the GSF, where we will employ
the method of extended homogeneous solutions [Phys. Rev. D {\bf 78}, 084021
(2008)].
