TY - JOUR

T1 - Minimizing roundoff errors of prefix sums via dynamic construction of Huffman trees

AU - Kao, Ming Yang

AU - Wang, Jie

N1 - Funding Information:
Some of the results in this paper appeared in the Proceedings of the 25th International Colloquium on Automata, Languages, and Programming, 1998, pp. 376–386. ∗Corresponding author. E-mail address: wang@uncg.edu (J. Wang). 1Supported in part by NSF under Grant CCR-9531028. 2Supported in part by NSF under Grants CCR-9424164 and by the University of North Carolina at Greensboro through a research grant.

PY - 2001

Y1 - 2001

N2 - The prefix-sum operation, which returns all prefix sums on a sequence of numbers, plays an important role in many applications. We study how to efficiently evaluate prefix sums on positive floating-point numbers such that the worst-case roundoff error of each sum is minimized. A direct approach to this problem builds a Huffman tree for each prefix subsequence from scratch, requiring exactly quadratic time for every input X. We can do better by taking advantage of the current Huffman tree to build the next Huffman tree, using dynamic insertions and deletions on Huffman trees. Consequently, subquadratic time suffices for various input patterns. We also provide experimental comparisons of all the algorithms studied in this paper on inputs that are randomly and uniformly generated.

AB - The prefix-sum operation, which returns all prefix sums on a sequence of numbers, plays an important role in many applications. We study how to efficiently evaluate prefix sums on positive floating-point numbers such that the worst-case roundoff error of each sum is minimized. A direct approach to this problem builds a Huffman tree for each prefix subsequence from scratch, requiring exactly quadratic time for every input X. We can do better by taking advantage of the current Huffman tree to build the next Huffman tree, using dynamic insertions and deletions on Huffman trees. Consequently, subquadratic time suffices for various input patterns. We also provide experimental comparisons of all the algorithms studied in this paper on inputs that are randomly and uniformly generated.

UR - http://www.scopus.com/inward/record.url?scp=0034921973&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0034921973&partnerID=8YFLogxK

U2 - 10.1016/S0304-3975(00)00183-3

DO - 10.1016/S0304-3975(00)00183-3

M3 - Article

AN - SCOPUS:0034921973

SN - 0304-3975

VL - 262

SP - 101

EP - 115

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -