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

Ming Yang Kao, Jie Wang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)101-115
Number of pages15
JournalTheoretical Computer Science
Volume262
Issue number1-2
DOIs
StatePublished - 2001

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Minimizing roundoff errors of prefix sums via dynamic construction of Huffman trees'. Together they form a unique fingerprint.

Cite this