  We propose an accurate algorithm for a novel sum-of-exponentials (SOE)
approximation of kernel functions, and develop a fast algorithm for convolution
quadrature based on the SOE, which allows an order $N$ calculation for $N$ time
steps of approximating a continuous temporal convolution integral. The SOE
method is constructed by a combination of the de la Vall\'ee-Poussin sums for a
semi-analytical exponential expansion of a general kernel, and a model
reduction technique for the minimization of the number of exponentials under
given error tolerance. We employ the SOE expansion for the finite part of the
splitting convolution kernel such that the convolution integral can be solved
as a system of ordinary differential equations due to the exponential kernels.
The significant features of our algorithm are that the SOE method is efficient
and accurate, and works for general kernels with controllable upperbound of
positive exponents. We provide numerical analysis for both the new SOE method
and the SOE-based convolution quadrature. Numerical results on different
kernels, the convolution integral and integral equations demonstrate attractive
performance of both accuracy and efficiency of the proposed method.
