1
$\begingroup$

Kahan summation applies to summation problems, but not to three-term recurrence relations. However, a three-term recurrence shares many of the features of a summation-albeit with a rescaling step at each iteration. Hence there seems to be hope for a Kahan summation for three-term recurrences. Has this idea been worked out in the literature or is the idea flawed in some way?

$\endgroup$
  • 1
    $\begingroup$ Kahan summation is like emulating double-double arithmetic with only double numbers. So if you want to use double-double arithmetic for a three-term recurrence, it's probably easier to just find a double-double (or a quad-double) library, if it's not already part of the language you're using, and use that. $\endgroup$ – Kirill Apr 14 '17 at 19:16
  • $\begingroup$ True. However, if the user wants the speed, they can just use the -ffast-math flag and have the optimizer kill off the Kahan summation. Shipping a dependency is more painful. $\endgroup$ – user14717 Apr 14 '17 at 19:24
  • 3
    $\begingroup$ @user14717 There are plenty of examples in the literature how to implement a double-native precision addition yourself, e.g. this paper. Kahan summation uses native precision for the source data and double-native precision for the result, but in a three-term recurrence (e.g. to compute Bessel functions) the source data is double-native precision as well after the first step, so you need double-native precision operations throughout. $\endgroup$ – njuffa Apr 14 '17 at 22:12
  • $\begingroup$ "...a three-term recurrence shares many of the features of a three-term recurrence..." - what? $\endgroup$ – J. M. Apr 16 '17 at 1:19
  • $\begingroup$ If you're computing the dominant solution of a three-term recurrence (e.g. $Y_n(x)$ for the Bessel recurrence), I don't see how something like Kahan could be shoehorned. If you're computing the (usually more interesting) minimal solution (e.g. $J_n(x)$ for the Bessel recurrence), you could maybe use Kahan along with Miller's algorithm. $\endgroup$ – J. M. Apr 16 '17 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.