TY - GEN
T1 - Efficient minimization of numerical summation errors
AU - Kao, Ming Yang
AU - Wang, Jie
PY - 1998/12/1
Y1 - 1998/12/1
N2 - Given a multiset X = {x1,⋯, xn} of real numbers, the floating-point set summation (FPS) problem asks for Sn = x1 + ··· + xn, and the floating point prefix set summation problem (FPPS) asks for Sk = x1 + ··· + Xk for all k = 1,⋯, n. Let E*k denote the minimum worst-case error over all possible orderings of evaluating Sk-We prove that if X has both positive and negative numbers, it is NP-hard to compute Sn with the worst-case error equal to En. We then give the first known polynomial-time approximation algorithm for computing Sn that has a provably small error for arbitrary X. Our algorithm incurs a worstcase error at most 2([log(n - 1)] + 1)E*n.1 After X is sorted, it runs in O(n) time, yielding an O(n2)-time approximation algorithm for computing Sk for all k = 1,⋯, n such that the worst-case error for each Sk is less than 2[log(k - 1)1 + 1)E*k. For the case where X is either all positive or all negative, we give another approximation algorithm for computing Sn with a worst-case error at most [log log n]E*n. Even for unsorted X, this algorithm runs in 0(n) time. Previously, the best linear-time approximation algorithm had a worst-case error at most flog n] En, while E n was known to be attainable in O(n log n) time using Huffman coding. Consequently, FPPS is solvable in O(n2) time such that the worst-case error for each Sk is the minimum. To improve this quadratic time bound in practice, we design two on-line algorithms that calculate the next Sk by taking advantage of the current S k and thus reduce redundant computation.
AB - Given a multiset X = {x1,⋯, xn} of real numbers, the floating-point set summation (FPS) problem asks for Sn = x1 + ··· + xn, and the floating point prefix set summation problem (FPPS) asks for Sk = x1 + ··· + Xk for all k = 1,⋯, n. Let E*k denote the minimum worst-case error over all possible orderings of evaluating Sk-We prove that if X has both positive and negative numbers, it is NP-hard to compute Sn with the worst-case error equal to En. We then give the first known polynomial-time approximation algorithm for computing Sn that has a provably small error for arbitrary X. Our algorithm incurs a worstcase error at most 2([log(n - 1)] + 1)E*n.1 After X is sorted, it runs in O(n) time, yielding an O(n2)-time approximation algorithm for computing Sk for all k = 1,⋯, n such that the worst-case error for each Sk is less than 2[log(k - 1)1 + 1)E*k. For the case where X is either all positive or all negative, we give another approximation algorithm for computing Sn with a worst-case error at most [log log n]E*n. Even for unsorted X, this algorithm runs in 0(n) time. Previously, the best linear-time approximation algorithm had a worst-case error at most flog n] En, while E n was known to be attainable in O(n log n) time using Huffman coding. Consequently, FPPS is solvable in O(n2) time such that the worst-case error for each Sk is the minimum. To improve this quadratic time bound in practice, we design two on-line algorithms that calculate the next Sk by taking advantage of the current S k and thus reduce redundant computation.
UR - http://www.scopus.com/inward/record.url?scp=0004461454&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0004461454&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0004461454
SN - 3540647813
SN - 9783540647812
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 375
EP - 386
BT - Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings
T2 - 25th International Colloquium on Automata, Languages and Programming, ICALP 1998
Y2 - 13 July 1998 through 17 July 1998
ER -