@article{GUPTA2020107385,
title = "Calculating the divided differences of the exponential function by addition and removal of inputs",
journal = "Computer Physics Communications",
volume = "254",
pages = "107385",
year = "2020",
issn = "0010-4655",
doi = "https://doi.org/10.1016/j.cpc.2020.107385",
url = "http://www.sciencedirect.com/science/article/pii/S0010465520301673",
author = "Lalit Gupta and Lev Barash and Itay Hen",
keywords = "Divided differences, Matrix exponential, Scaling and squaring method, Quantum Monte Carlo algorithms, Off-diagonal series expansion",
abstract = "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 Zivcovich (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(sn) floating point operations and O(sn) bytes of memory, where [z0,…,zn] are the inputs and s∝maxi,j|zi−zj|. 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."
}

{"_id":"iLXPWFjgGjQuuh9nh","bibbaseid":"gupta-barash-hen-calculatingthedivideddifferencesoftheexponentialfunctionbyadditionandremovalofinputs-2020","author_short":["Gupta, L.","Barash, L.","Hen, I."],"bibdata":{"bibtype":"article","type":"article","title":"Calculating the divided differences of the exponential function by addition and removal of inputs","journal":"Computer Physics Communications","volume":"254","pages":"107385","year":"2020","issn":"0010-4655","doi":"https://doi.org/10.1016/j.cpc.2020.107385","url":"http://www.sciencedirect.com/science/article/pii/S0010465520301673","author":[{"firstnames":["Lalit"],"propositions":[],"lastnames":["Gupta"],"suffixes":[]},{"firstnames":["Lev"],"propositions":[],"lastnames":["Barash"],"suffixes":[]},{"firstnames":["Itay"],"propositions":[],"lastnames":["Hen"],"suffixes":[]}],"keywords":"Divided differences, Matrix exponential, Scaling and squaring method, Quantum Monte Carlo algorithms, Off-diagonal series expansion","abstract":"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 Zivcovich (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(sn) floating point operations and O(sn) bytes of memory, where [z0,…,zn] are the inputs and s∝maxi,j|zi−zj|. 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.","bibtex":"@article{GUPTA2020107385,\ntitle = \"Calculating the divided differences of the exponential function by addition and removal of inputs\",\njournal = \"Computer Physics Communications\",\nvolume = \"254\",\npages = \"107385\",\nyear = \"2020\",\nissn = \"0010-4655\",\ndoi = \"https://doi.org/10.1016/j.cpc.2020.107385\",\nurl = \"http://www.sciencedirect.com/science/article/pii/S0010465520301673\",\nauthor = \"Lalit Gupta and Lev Barash and Itay Hen\",\nkeywords = \"Divided differences, Matrix exponential, Scaling and squaring method, Quantum Monte Carlo algorithms, Off-diagonal series expansion\",\nabstract = \"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 Zivcovich (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(sn) floating point operations and O(sn) bytes of memory, where [z0,…,zn] are the inputs and s∝maxi,j|zi−zj|. 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.\"\n}\n\n","author_short":["Gupta, L.","Barash, L.","Hen, I."],"bibbaseid":"gupta-barash-hen-calculatingthedivideddifferencesoftheexponentialfunctionbyadditionandremovalofinputs-2020","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/pii/S0010465520301673"},"keyword":["Divided differences","Matrix exponential","Scaling and squaring method","Quantum Monte Carlo algorithms","Off-diagonal series expansion"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://bibbase.org/f/6moQXZADybdshmwar/itayhen.bib","dataSources":["CSYFA7qwQGMgrz3JD"],"keywords":["divided differences","matrix exponential","scaling and squaring method","quantum monte carlo algorithms","off-diagonal series expansion"],"search_terms":["calculating","divided","differences","exponential","function","addition","removal","inputs","gupta","barash","hen"],"title":"Calculating the divided differences of the exponential function by addition and removal of inputs","year":2020}