Efficient minimization of numerical summation errors

Ming Yang Kao, Jie Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings
Pages375-386
Number of pages12
StatePublished - Dec 1 1998
Event25th International Colloquium on Automata, Languages and Programming, ICALP 1998 - Aalborg, Denmark
Duration: Jul 13 1998Jul 17 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1443 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other25th International Colloquium on Automata, Languages and Programming, ICALP 1998
CountryDenmark
CityAalborg
Period7/13/987/17/98

Fingerprint

Worst Case Error
Summation
Approximation Algorithms
Floating point
Approximation algorithms
Prefix
Computing
Huffman Coding
Multiset
Linear-time Algorithm
Point Sets
Polynomial-time Algorithm
NP-complete problem
Denote
Calculate
Polynomials
Arbitrary

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Kao, M. Y., & Wang, J. (1998). Efficient minimization of numerical summation errors. In Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings (pp. 375-386). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1443 LNCS).
Kao, Ming Yang ; Wang, Jie. / Efficient minimization of numerical summation errors. Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings. 1998. pp. 375-386 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{bb82fc180026439ba39553f07f964192,
title = "Efficient minimization of numerical summation errors",
abstract = "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.",
author = "Kao, {Ming Yang} and Jie Wang",
year = "1998",
month = "12",
day = "1",
language = "English (US)",
isbn = "3540647813",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "375--386",
booktitle = "Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings",

}

Kao, MY & Wang, J 1998, Efficient minimization of numerical summation errors. in Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1443 LNCS, pp. 375-386, 25th International Colloquium on Automata, Languages and Programming, ICALP 1998, Aalborg, Denmark, 7/13/98.

Efficient minimization of numerical summation errors. / Kao, Ming Yang; Wang, Jie.

Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings. 1998. p. 375-386 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1443 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

ER -

Kao MY, Wang J. Efficient minimization of numerical summation errors. In Automata, Languages and Programming - 25th International Colloquium, ICALP 1998, Proceedings. 1998. p. 375-386. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).