{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,11]],"date-time":"2025-11-11T12:47:57Z","timestamp":1762865277449,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2007,3,1]],"date-time":"2007-03-01T00:00:00Z","timestamp":1172707200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2007,3]]},"abstract":"<jats:p>Fortran software is developed that calculates a best piecewise monotonic approximation to<jats:italic>n<\/jats:italic>univariate data contaminated by random errors. The underlying method minimizes the weighted sum of the squares of the errors by requiring<jats:italic>k<\/jats:italic>\u2212 1 sign changes in the first divided differences of the approximation, where<jats:italic>k<\/jats:italic>is a given positive integer. Hence, the piecewise linear interpolant to the fit consists of<jats:italic>k<\/jats:italic>monotonic sections, alternately increasing and decreasing. This calculation can have about<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup><jats:italic>k<\/jats:italic><\/jats:sup>) 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<jats:italic>k<\/jats:italic>disjoint sets of adjacent data and solves a<jats:italic>k<\/jats:italic>= 1 problem (monotonic fit or isotonic regression) for each set. So it calculates efficiently a global solution in only<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>\u03c3 +<jats:italic>k<\/jats:italic>\u03c3<jats:sup>2<\/jats:sup>) computer operations when<jats:italic>k<\/jats:italic>\u2265 3, where \u03c3 is the number of local minima of the data, always bounded by<jats:italic>n<\/jats:italic>\/2. This complexity reduces to only<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>) when<jats:italic>k<\/jats:italic>= 1 or<jats:italic>k<\/jats:italic>= 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.<\/jats:p>","DOI":"10.1145\/1206040.1206046","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T19:20:08Z","timestamp":1175800808000},"page":"6","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Algorithm 863"],"prefix":"10.1145","volume":"33","author":[{"given":"Ioannis C.","family":"Demetriou","sequence":"first","affiliation":[{"name":"University of Athens, Athens, Greece"}]}],"member":"320","published-online":{"date-parts":[[2007,3]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Barlow R. E. Bartholomew D. J. Bremner J. M. and Brunk H. D. 1980. Statistical Inference under Order Restrictions. The Theory and Applications of Isotonic Regression. John Wiley &amp; Sons Chichester England. Barlow R. E. Bartholomew D. J. Bremner J. M. and Brunk H. D. 1980. Statistical Inference under Order Restrictions. The Theory and Applications of Isotonic Regression. John Wiley &amp; Sons Chichester England."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1951.tb00067.x"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02868560"},{"volume-title":"Visualizing Data","author":"Cleveland W. S.","key":"e_1_2_2_4_1"},{"volume-title":"A Practical Guide to Splines, rev. ed. Applied Mathematical Sciences","author":"De Boor C.","key":"e_1_2_2_5_1"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.2307\/2153327"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(02)00353-9"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/11.3.411"},{"key":"e_1_2_2_9_1","unstructured":"Demetriou I. C. and Powell M. J. D. 1997. Least squares fitting to univariate data subject to restrictions on the sign of the second differences. In Approximation Theory and Optimization Tributes to M.J.D. Powell M.D. Buhmann and A. Iserles Eds. Cambridge University Press Cambridge England 109--132. Demetriou I. C. and Powell M. J. D. 1997. Least squares fitting to univariate data subject to restrictions on the sign of the second differences. In Approximation Theory and Optimization Tributes to M.J.D. Powell M.D. Buhmann and A. Iserles Eds. Cambridge University Press Cambridge England 109--132."},{"volume-title":"Curve and Surface Fitting with Splines","author":"Dierckx P.","key":"e_1_2_2_10_1","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198534419.001.0001"},{"edition":"2","volume-title":"Practical Methods of Optimization","author":"Fletcher R.","key":"e_1_2_2_11_1"},{"key":"e_1_2_2_12_1","unstructured":"Frisen M. and Goteborg S. 1980. U-shaped regression. In Compstat 1980. Physica Verlag Vienna Austria. Frisen M. and Goteborg S. 1980. U-shaped regression. In Compstat 1980. Physica Verlag Vienna Austria."},{"volume-title":"Requirements of Standards: Optimization Models and Algorithms","author":"Goldengorin B.","key":"e_1_2_2_13_1"},{"volume-title":"Applied Nonparametric Regression","author":"H\u00e4rdle W.","key":"e_1_2_2_14_1","doi-asserted-by":"crossref","DOI":"10.1017\/CCOL0521382483"},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"H\u00e4rdle W. M\u00fcller M. Sperlich S. and Werwatz A. 2004. Nonparametric and Semiparametric Models. Springer-Verlag Heidelberg Germany. H\u00e4rdle W. M\u00fcller M. Sperlich S. and Werwatz A. 2004. Nonparametric and Semiparametric Models. Springer-Verlag Heidelberg Germany.","DOI":"10.1007\/978-3-642-17146-8"},{"key":"e_1_2_2_16_1","unstructured":"Hildenbrand K. and Hildenbrand W. 1986. On the mean income effect: A data analysis of the U.K. family expenditure survey. In Contributions to Mathematical Economics W. Hildenbrand and A. Mas-Collel Eds. North Holland New York NY. Hildenbrand K. and Hildenbrand W. 1986. On the mean income effect: A data analysis of the U.K. family expenditure survey. In Contributions to Mathematical Economics W. Hildenbrand and A. Mas-Collel Eds. North Holland New York NY."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177731784"},{"volume-title":"Categorical and Multivariate Methods","author":"Jobson J. D.","key":"e_1_2_2_18_1"},{"volume-title":"Analysis of Economic Data","author":"Koop G.","key":"e_1_2_2_19_1"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1115\/1.3653121"},{"volume-title":"Englewood","year":"1974","author":"Lawson C. L.","key":"e_1_2_2_21_1"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1117\/12.292795"},{"key":"e_1_2_2_23_1","volume-title":"Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (May, 12--15","volume":"3","author":"Lu J.","year":"1998"},{"volume-title":"Studies in Business-Cycle Theory","author":"Lucas R. E.","key":"e_1_2_2_24_1"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1512686"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0029-554X(67)90058-4"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176350832"},{"volume-title":"Origin Scientific Graphing and Analysis Software. OriginLabtrade","author":"Origin\u00a9","key":"e_1_2_2_28_1"},{"volume-title":"Algorithms for Graphics and Image Processing","author":"Pavlidis T.","key":"e_1_2_2_29_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-93208-3"},{"key":"e_1_2_2_30_1","unstructured":"Peakfit#8482;. 2004. PeakFit 4.11 for Windows User's Manual. Systat Software Richmont CA. Peakfit#8482;. 2004. PeakFit 4.11 for Windows User's Manual. Systat Software Richmont CA."},{"key":"e_1_2_2_31_1","doi-asserted-by":"crossref","unstructured":"Piegl L. and Tiller W. 1997. The NURBS Book 2nd ed. Springer-Verlag Berlin Germany. Piegl L. and Tiller W. 1997. The NURBS Book 2nd ed. Springer-Verlag Berlin Germany.","DOI":"10.1007\/978-3-642-59223-2"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-349-02051-5"},{"volume-title":"Numerical Methods, Software, and Analysis","author":"Rice J. R.","key":"e_1_2_2_33_1","doi-asserted-by":"crossref","DOI":"10.1115\/1.3269330"},{"key":"e_1_2_2_34_1","unstructured":"Robertson T. Wright F. T. and Dykstra R. L. 1988. Order Restricted Statistical Inference. J. Wiley &amp; Sons Chichester England. Robertson T. Wright F. T. and Dykstra R. L. 1988. Order Restricted Statistical Inference. J. Wiley &amp; Sons Chichester England."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511599224"},{"volume-title":"Systat Software Inc","author":"Tablecurve D.","key":"e_1_2_2_36_1"},{"key":"e_1_2_2_37_1","unstructured":"Von Winterfeldt D. and Edwards W. 1986. Decision Analysis and Behavioral Research. Cambridge University Press Cambridge England. Von Winterfeldt D. and Edwards W. 1986. Decision Analysis and Behavioral Research. Cambridge University Press Cambridge England."},{"volume-title":"Spline Models for Observational Data","author":"Wahba G. R.","key":"e_1_2_2_38_1","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970128"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03168258"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-1098(1999)10:2<177::AID-IMA8>3.0.CO;2-8"},{"key":"e_1_2_2_41_1","first-page":"763","volume-title":"Medical Imaging. Proc. SPIE","volume":"2710","author":"Weaver J. B."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177696724"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176345140"},{"volume-title":"Semiparametric Regression for the Applied Econometrician","author":"Yatchew A.","key":"e_1_2_2_44_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511615887"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1206040.1206046","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1206040.1206046","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:31Z","timestamp":1750278151000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1206040.1206046"}},"subtitle":["L2WPMA, a Fortran 77 package for weighted least-squares piecewise monotonic data approximation"],"short-title":[],"issued":{"date-parts":[[2007,3]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,3]]}},"alternative-id":["10.1145\/1206040.1206046"],"URL":"https:\/\/doi.org\/10.1145\/1206040.1206046","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"type":"print","value":"0098-3500"},{"type":"electronic","value":"1557-7295"}],"subject":[],"published":{"date-parts":[[2007,3]]},"assertion":[{"value":"2007-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}