Elsevier Science Home
Computer Physics Communications Program Library
Full text online from Science Direct
Programs in Physics & Physical Chemistry
CPC Home

[Licence| Download | New Version Template] adff_v1_0.gz(33 Kbytes)
Manuscript Title: CXFTV2: a Fortran subroutine for the discrete least squares convex approximation.
Authors: I.C. Demetriou
Program title: CXFTV2
Catalogue identifier: ADFF_v1_0
Distribution format: gz
Journal reference: Comput. Phys. Commun. 100(1997)297
Programming language: Fortran.
Computer: PC Intel Pentium 90MHz.
Operating system: MSDOS 6.1, WINDOWS 95, WINDOWS NT.
Word size: 8
Keywords: General purpose, Fit, Convexity, Data fitting, Smoothing, Least squares, Quadratic programming, Divided difference, B-splines.
Classification: 4.9.

Nature of problem:
Convex smoothing to univariate measurements that contain random errors.

Solution method:
The least squares approximation to n data values subject to non-negative second divided differences (convexity) is calculated. The method employs a dual active set quadratic programming technique that allows several concavities of an iterate to be corrected simultaneously. A B-spline representation of the iterates reduces each active set calculation to an unconstrained minimization with fewer variables. Numerical testing on a variety of data sets indicates that the subroutine is particularly efficient, terminating after a small number of active set changes, where each such change requires O(n) operations.

Number n is not limited in the subroutine but is limited to 2000 in the main driver.

Running time:
12.3 seconds to smooth n=1000 data points (CPU time in T800 INMOS Transputer operating in Macintosh environment).