Computer Science – Computational Engineering – Finance – and Science
Scientific paper
2006-09-14
Recurrence relations and fast algorithms, Applied and Computational Harmonic Analysis, 28 (1): 121-128, 2010
Computer Science
Computational Engineering, Finance, and Science
24 pages
Scientific paper
We construct fast algorithms for evaluating transforms associated with families of functions which satisfy recurrence relations. These include algorithms both for computing the coefficients in linear combinations of the functions, given the values of these linear combinations at certain points, and, vice versa, for evaluating such linear combinations at those points, given the coefficients in the linear combinations; such procedures are also known as analysis and synthesis of series of certain special functions. The algorithms of the present paper are efficient in the sense that their computational costs are proportional to n (ln n) (ln(1/epsilon))^3, where n is the amount of input and output data, and epsilon is the precision of computations. Stated somewhat more precisely, we find a positive real number C such that, for any positive integer n > 10, the algorithms require at most C n (ln n) (ln(1/epsilon))^3 floating-point operations and words of memory to evaluate at n appropriately chosen points any linear combination of n special functions, given the coefficients in the linear combination, where epsilon is the precision of computations.
No associations
LandOfFree
Recurrence relations and fast algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Recurrence relations and fast algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Recurrence relations and fast algorithms will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-537420