Iwona Skalna and Milan Hladík. A new algorithm for Chebyshev minimum-error multiplication of reduced affine forms. Numer. Algorithms, 76(4):1131–1152, 2017.
[PDF] [gzipped postscript] [postscript] [HTML]
Reduced affine arithmetic (RAA) eliminates the main deficiency of the standard affine arithmetic (AA), i.e. a gradual increase of the number of noise symbols, which makes AA inefficient in a long computation chain. To further reduce overestimation in RAA computation, a new algorithm for the Chebyshev minimum-error multiplication of reduced affine forms is proposed. The algorithm yields the minimum Chebyshev-type bounds and works in linear time, which is asymptotically optimal. We also propose a simplified O(n.log(n)) version of the algorithm, which performs better for low dimensional problems. Illustrative examples show that the presented approach significantly improves solutions of many numerical problems, such as the problem of solving parametric interval linear systems or parametric linear programming, and also improves the efficiency of interval global optimisation.
@article{SkaHla2017a,
author = "Iwona Skalna and Milan Hlad\'{\i}k",
title = "A new algorithm for {Chebyshev} minimum-error multiplication of reduced affine forms",
journal = "Numer. Algorithms",
fjournal = "Numerical Algorithms",
volume = "76",
number = "4",
pages = "1131-1152",
year = "2017",
doi = "10.1007/s11075-017-0300-6",
issn = "1572-9265",
url = "https://link.springer.com/article/10.1007/s11075-017-0300-6",
bib2html_dl_html = "https://doi.org/10.1007/s11075-017-0300-6",
bib2html_dl_pdf = "http://rdcu.be/zcFy",
abstract = "Reduced affine arithmetic (RAA) eliminates the main deficiency of the standard affine arithmetic (AA), i.e. a gradual increase of the number of noise symbols, which makes AA inefficient in a long computation chain. To further reduce overestimation in RAA computation, a new algorithm for the Chebyshev minimum-error multiplication of reduced affine forms is proposed. The algorithm yields the minimum Chebyshev-type bounds and works in linear time, which is asymptotically optimal. We also propose a simplified O(n.log(n)) version of the algorithm, which performs better for low dimensional problems. Illustrative examples show that the presented approach significantly improves solutions of many numerical problems, such as the problem of solving parametric interval linear systems or parametric linear programming, and also improves the efficiency of interval global optimisation.",
keywords = "Reduced affine arithmetic; Multiplication; Chebyshev minimum-error approximation",
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Oct 23, 2024 08:16:44