We investigate the computational requirements for all-sky, all-frequen
cy searches for gravitational waves from spinning neutron stars, using
archived data from interferometric gravitational wave detectors such
as LIGO. These sources are expected to be weak, so the optimal strateg
y involves coherent accumulation of signal-to-noise using Fourier tran
sforms of long stretches of data (months to years). Earth-motion-induc
ed Doppler shifts, and intrinsic pulsar spindown, will reduce the narr
ow-band signal-to-noise by spreading power across many frequency bins;
therefore, it is necessary to correct for these effects before perfor
ming the Fourier transform. The corrections can be implemented by a pa
rametrized model, in which one does a search over a discrete set of pa
rameter values (points in the parameter space of corrections). We defi
ne a metric on this parameter space, which can be used to determine th
e optimal spacing between points in a search; the metric is used to co
mpute the number of independent parameter-space points N-p, that must
be searched, as a function of observation time T. This method accounts
automatically for correlations between the spindown and Doppler corre
ctions. The number N-p(T) depends on the maximum gravitational wave fr
equency and the minimum spindown age tau=f/f that the search can detec
t. The signal-to-noise ratio required, in order to have 99% confidence
of a detection, also depends on N-p,(T). We find that for an all-sky,
all-frequency search lasting T=10(7) s, this detection threshold is h
(c),approximate to(4-5)h,(3/yr),,, where h(3/yr) is the corresponding
99% confidence threshold if one knows in advance the pulsar position a
nd spin period. We define a coherent search, over some data stream of
length T, to be one where we apply a correction, followed by a fast Fo
urier transform of the data, for every independent point in the parame
ter space. Given realistic limits on computing power, and assuming tha
t data analysis proceeds at the same rate as data acquisition (e.g., 1
0 days of data gets analyzed in similar to 10 days), we can place limi
tations on how much data can be searched coherently. In an all-sky sea
rch for pulsars having gravity-wave frequencies f less than or equal t
o 200 Hz and spindown ages tau greater than or equal to 1000 yr, one c
an coherently search similar to 18 days of data on a teraflops compute
r. In contrast, a teraflops computer can only perform a similar to 0.8
-day coherent search for pulsars with frequencies f less than or equal
to 1 kHz and spindown ages as low as 40 yr. In addition to all-sky se
arches we consider coherent directed searches, where one knows in adva
nce the source position but not the period. (Nearby supernova remnants
and the galactic center are obvious places to look.) We show that for
such a search, one gains a factor of similar to 10 in observation tim
e over the case of an all-sky search, given a 1 Tflops computer. The e
normous computational burden involved in coherent searches indicates t
he need for alternative data analysis strategies. As an example we bri
efly discuss the implementation of a simple hierarchical search in the
last section of the paper. Further work is required to determine the
optimal approach. [S0556-2821(98)02902-6].