Calculating the divided differences of the exponential function by addition and removal of inputs
share
We introduce a method for calculating the divided differences of the exponential function by means of addition and removal of items from the input list to the function. Our technique exploits a new identity related to divided differences recently derived by F. Zivcovich [Dolomites Research Notes on Approximation 12, 28-42 (2019)]. We show that upon adding an item to or removing an item from the input list of an already evaluated exponential, the re-evaluation of the divided differences can be done with only O(s n) floating point operations and O(s n) bytes of memory, where [z_0,...,z_n] are the inputs and s ∝max_i,j |z_i - z_j|. We demonstrate our algorithm's ability to deal with input lists that are orders-of-magnitude longer than the maximal capacities of the current state-of-the-art. We discuss in detail one practical application of our method: the efficient calculation of weights in the off-diagonal series expansion quantum Monte Carlo algorithm.
READ FULL TEXT