L2WPMA
swMATH ID:  4326 
Software Authors:  Ioannis C. Demetriou 
Description:  Algorithm 863: L2WPMA, a Fortran 77 package for weighted leastsquares piecewise monotonic data approximation. Fortran software is developed that calculates a best piecewise monotonic approximation to n univariate data contaminated by random errors. The underlying method minimizes the weighted sum of the squares of the errors by requiring k − 1 sign changes in the first divided differences of the approximation, where k is a given positive integer. Hence, the piecewise linear interpolant to the fit consists of k monotonic sections, alternately increasing and decreasing. This calculation can have about O(nk) local minima, because the positions of the turning points of the fit are integer variables of the problem. The method, however, by employing a dynamic programming technique divides the data into at most k disjoint sets of adjacent data and solves a k = 1 problem (monotonic fit or isotonic regression) for each set. So it calculates efficiently a global solution in only O(nσ + kσ2) computer operations when k ≥ 3, where σ is the number of local minima of the data, always bounded by n/2. This complexity reduces to only O(n) when k = 1 or k = 2 (unimodal case). At the end of the calculation a spline representation of the solution and the corresponding Lagrange multipliers are provided. The software package has been tested on a variety of data sets showing a performance that does provide in practice shorter computation times than the complexity indicates in theory. An application of the method on identifying turning points and monotonic trends of data from 1947–1996 on the U.K. pound over the U.S. dollar exchange rate is presented. Generally, the method may have useful applications as, for example, in estimating the turning points of a function from some noisy measurements of its values, or in image and signal processing, or in providing a preliminary or complementary smoothing phase to further analyses of the data. 
Homepage:  http://dl.acm.org/citation.cfm?id=1206046 
Programming Languages:  Fortran 
Keywords:  approximation, data smoothing, divided difference, dynamic programming, histogram, image processing, isotonic regression, Lagrange multipliers, piecewise monotonic, pound / dollar exchange rate, signal processing, spline, turning point 
Related Software:  FITPACK; Sheppack; QSHEP5D; CSHEP2D; TSHEP2D; QSHEP3D; QSHEP2D; PVODE; FCVODE; KINSOL; L2MCX; L2CXFT; CXFTV2 
Referenced in:  8 Publications 
Standard Articles
1 Publication describing the Software, including 1 Publication in zbMATH  Year 

Parallel resolution of the twogroup time dependent neutron diffusion equation with public domain ODE codes. Zbl 1118.82300 García, Víctor M.; Vidal, V.; Verdú, G.; Garayoa, J.; Miró, R. 
2005

all
top 5
Referenced by 15 Authors
all
top 5
Referenced in 7 Serials
all
top 5