A fast segmentation algorithm for piecewise polynomial numeric function generators

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:235

Article

Butler, Jon T.¹  Frenzen, C. L.²  Sasao, Tsutomu³ 

[1] USN, Postgrad Sch, Dept Elect & Comp Engn, Code EC Bu, Monterey, CA 93943 USA

[2] USN, Postgrad Sch, Dept Appl Math, Monterey, CA 93943 USA

[3] Kyushu Inst Technol, Dept Comp Sci & Elect, Iizuka, Fukuoka 8208502, Japan

关键词: Numerical approximation;    Piecewise polynomial approximation;    Numeric function generators;    Segmentation algorithm;    Piecewise linear approximation;   

DOI  :  10.1016/j.cam.2011.02.033

来源: Elsevier

【 摘 要 】

We give an efficient algorithm for partitioning the domain of a numeric function f into segments. The function f is realized as a polynomial in each segment, and a lookup table stores the coefficients of the polynomial. Such an algorithm is an essential part of the design of lookup table methods Ercepovac et al. (2000)[5], Lee et al. (2003)[7], Nagayama et al. (2007) [12], Paul et al. (2007) [6] and Sasao et al. (2004)[8] for realizing numeric functions, such as sin(pi x), In(x), and root-In(x). Our algorithm requires many fewer steps than a previous algorithm given in Frenzen et al. (2010)[10] and makes tractable the design of numeric function generators based on table lookup for high-accuracy applications. We show that an estimate of segment width based on local derivatives greatly reduces the search needed to determine the exact segment width. We apply the new algorithm to a suite of 15 numeric functions and show that the estimates are sufficiently accurate to produce a minimum or near-minimum number of computational steps. Published by Elsevier B.V.

【 授权许可】

Free