c*** l2cxft.txt
         ============================================================
                 DESCRIPTION AND USE OF THE FORTRAN CODES FOR

         "L2CXFT: A FORTRAN SUBROUTINE FOR LEAST SQUARES DATA FITTING
                 WITH NON-NEGATIVE SECOND DIVIDED DIFFERENCES"

                                I.C. DEMETRIOU

              An algorithm of ACM TOMS, Vol.21, No.1, March 1995
         ============================================================

                             University of Athens
                            Department of Economics
                      Unit of Mathematics and Informatics
                  8 Pesmazoglou Street, 105 59 Athens, Greece
                       E-mail: demetri@aueb.ariadne-t.gr


This file provides information about:

      DOCUMENTATION, LISTINGS, DRIVER PROGRAMS, INSTALLATION, TESTING AND
                 MAINTENANCE OF THE FORTRAN SUBROUTINE L2CXFT

SUMMARY
This file is complementary to the ACM  TOMS  submission  entitled  "L2CXFT:  A
Fortran subroutine for least squares data  fitting  with  non-negative  second
divided differences" by I.C. Demetriou [1]. It consists of three sections  and
four appendices organized as follows. Section 1 states the problem, Section  2
presents the purpose of each  subroutine  and  Section  3  outlines  the  user
interface. Appendix A keeps the Fortran listings of the  subroutines  together
with symbol explanations. Appendix B presents driver programs  and  output  of
test examples in order to help the usage of L2CXFT. Appendix C gives technical
details about installation, compilation, linking and running  of  the  Fortran
codes. Appendix D considers some coding details of each subroutine.
The entire set code occupies 1469 Fortran 77 lines including comments.  Single
and double precision versions have  been  developed  for  practical  use.  All
subroutines begin with comments that explain the input and  output  arguments,
the working space and the method followed.
Details about the method of calculation, the user interface and the subroutine
purpose  are  presented  in  [1].  The  underlying  method  is  mathematically
established by [2].
APPLICATIONS
Since the underlying method may be attended as a convex regression  technique,
it may be particularly useful to  statistical  analysis  and  economics  where
marginal utility, productivity, supply and demand functions are assumed to  be
convex or concave. The concave smoothing can be treated  as  convex  after  an
overall change of sign.
REFERENCES
[1] Demetriou, I.C., L2CXFT: A  Fortran  subroutine  for  least  squares  data
    fitting with nonnegative second divided differences. ACM  Transactions  on
    Mathematical Software, Vol.21, No.1, March 1995.
[2] Demetriou, I.C. and M.J.D.Powell, The minimum sum  of  squares  change  to
    univariate data that  gives  convexity.  IMA  J.  of  Numerical  Analysis,
    11(1991), pp. 433-448.
[3] Powell, M.J.D., "Approximation theory and methods".  Cambridge  University
    Press, Cambridge, 1981.

                              THIS FILE CONTAINS:
                              -------------------
1. Problem definition
2. Directory of subroutines
3. The user interface

Appendix A  Subroutine listings .............................................
Appendix B  Driver programs for L2CXFT and a test example with output  ......
Appendix C  Installation and testing of subroutine L2CXFT  ..................
            1. Overview and diskette contents  ..............................
            2. Installing the source codes  .................................
            3. Generating data sets  ........................................
            4. Applying subroutine L2CXFT to a data set  ....................
            5. Multiple testing of subroutine L2CXFT on substantially
               different data sets  .........................................
Appendix D  Remarks on the Fortran listings  ................................

                  THE ACCOMPANYING MS-DOS DISKETTE CONTAINS:
                  ------------------------------------------
Disk 1 of 1: Source codes
     README            Explains the diskette contents
     L2CXFT.TXT        This file

     \SGL subdirectory: Single precision codes
     L2CXFT.FOR
     L2ILS.FOR
     CFLGRF.FOR
     COEFF.FOR
     LAGRANG.FOR
     SXATXI.FOR
     ADDKNT.FOR
     PLUS.FOR
     DELKNT.FOR
     MINUS1.FOR
     MESSGE.FOR
     PROG1.FOR
     PROG2.FOR
     PROGMULT.FOR
     RND.FOR
          (15 files)

     \DBL subdirectory: Double precision codes
     L2CXFT.FOR
     L2ILS.FOR
     CFLGRF.FOR
     COEFF.FOR
     LAGRANG.FOR
     SXATXI.FOR
     ADDKNT.FOR
     PLUS.FOR
     DELKNT.FOR
     MINUS1.FOR
     MESSGE.FOR
     PROG1.FOR
     PROG2.FOR
     PROGMULT.FOR
     RND.FOR
          (15 files)

1. PROBLEM DEFINITION
---------------------
Fortran 77 software is presented for best least squares  convex  data  fitting
that is stated by Demetriou and Powell [2] as follows. A convex function  f(x)
is measured at  the  abscissae  X(I1)<X(I1+1)<...<X(N)  but  the  measurements
(data) {F(i):i=I1,I1+1,...,N} have lost convexity due to random errors of the
measuring process. We regard the measurements as a vector F(.) and calculate a
vector SX(.) that minimizes the function

                       N
                      SUM (F(i)-SX(i))*(F(i)-SX(i))                      (1.1)
                      i=I1

subject to the convexity constraints

            SX[X(i),X(i+1),X(i+2)] >= 0 ,   i=I1,i1+1,...,N-2,           (1.2)

where SX[X(i),X(i+1),X(i+2)] is the i-th second divided  difference  of  SX(.)
(see, for example, Powell [3:p.46]). Here SX(X(j)) denotes SX(j)  which  is  a
component of SX(.). Due to the  structure  of  the  divided  differences,  the
constraints (1.2) are consistent and their gradients are linearly independent.
Hence and in view of (1.1),  this  problem  is  a  strictly  convex  quadratic
programming calculation. There exists a unique solution  SX(.)  which  can  be
calculated efficiently by the following special method of Demetriou and Powell
[2] that takes account of the structure of the constraints. First an algorithm
gives an approximation close to the optimum in  O(N-I1)  operations  and  then
this approximation is used as the starting vector of a dual feasible quadratic
programming algorithm that completes the calculation of the optimum.  A  great
advantage of this method is that, due to B-splines, it uses the constraints to
reduce the number of variables and  at  the  same  time  the  constraints  are
satisfied automatically. The remark implies that the knots of the splines  are
determined automatically from the non-zero divided differences.

On termination, SX(.) is the vector  that  minimizes  the  objective  function
(1.1) subject to the equality (or active) constraints

               SX[X(i),X(i+1),X(i+2)] = 0 ,   i in IACT(.)               (1.3)

where IACT(.) is a subset of the constraint indices {I1,I1+1,...,N-2}.  Unique
Lagrange multipliers {PAR(i): i in IACT(.)} are defined  by  the  first  order
optimality condition

    2*(SX(.)-F(.)) = SUM  PAR(i)*grad(i),  PAR(i) >= 0  i in IACT(.),    (1.4)
                   i in IACT

where grad(i) is the gradient of the i-th divided difference with  respect  to
SX(.).

The calculation of  the  best  convex  approximation  SX(.)  is  performed  by
software that consists of eleven subroutines, the main  one  being  subroutine
L2CXFT. The underlying methods of the quadratic programming algorithm and  its
initialization procedure are shortly described by [1] and in  detail  by  [2].
Section2 presents the purpose of each subroutine and Section 3 specifies  the
interface of this software with the calling program.  Since  the  solution  is
expressed by a linear spline approximation, suitable updating algorithms  have
been developed for the cases when  the  spline  basis  changes.  The  software
includes a test whose purpose is to safeguard the termination of the quadratic
programming algorithm in degenerate or near  degenerate  situations.  Further,
iterative refinement is applied automatically when the  accumulated  round-off
errors disturb the solution so much that basic theorems are violated.

The entire set code occupies 1469 Fortran 77 lines including comments.  Single
and double precision versions have been developed for practical use. In  order
to make the code readable and reasonably self described, all subroutines begin
with comments that explain the input and output arguments, the  working  space
and the method  followed.  The  software  has  being  tested  successfully  on
randomly generated data sets of large size and on thin  grids  showing  robust
performance and excessively small time demands (see Demetriou and Powell [2]).

Since our method may be attended as a convex regression technique, it  may  be
particularly useful to  statistical  analysis  and  economics  where  marginal
utility, productivity, supply and demand functions are assumed to be convex or
concave. The concave smoothing can be  treated  as  convex  after  an  overall
change of sign.

2. DIRECTORY OF SUBROUTINES
---------------------------
Eleven subroutines whose purposes are  shown  in  Table1  below  compose  the
software for the calculation described in [1]. Common blocks and private array
storage are completely avoided. The working  space  is  directed  through  the
argument list of the subroutines. All variables but the temporary ones  retain
their meaning. The arguments that appear in the  subroutine  declarations  are
explained by comments in the beginning of each subroutine.

The number of lines of code of  each  subroutine  including  comments  are  as
follows:

ADDKNT   122        L2CXFT   502        MINUS    34
DELKNT    92        L2ILS    183        PLUS    119
CFLGRF   154        LAGRNG    85        SXATXI   36
COEFF     51        MESSGE    91

                   TABLE 1   DIRECTORY OF SUBROUTINES
==============================================================================
    Name of
   subroutine    Purpose of subroutine
------------------------------------------------------------------------------
    L2CXFT       Interface to the user.
                 Minimizes  the  objective  function  (1.1)  subject  to   the
                 constraints (1.2) by implementing  Algorithm3  of  Demetriou
                 and Powell [2].  Calls  subroutines  L2ILS,  CFLGRF,  DELKNT,
                 ADDKNT and MESSGE.

    L2ILS        Provides a  starting  point  for  the  quadratic  programming
                 calculation  in  L2CXFT  by   implementing   Algorithm1   of
                 Demetriou and Powell [2]. It sets  for  the  first  time  the
                 normal equations associated to the B-spline representation of
                 the solution estimates.

    CFLGRF       Provides the least squares approximation by a  linear  spline
                 on given knots and the associated Lagrange multipliers. Also,
                 in certain cases, it initiates iterative improvement for  the
                 coefficients  of  the  normal  equations  and  the   Lagrange
                 multipliers. The normal equations are input to CFLGRF.  Calls
                 subroutines COEFF, SXATXI and LAGRNG.

    COEFF        Calculates the coefficients associated with the least squares
                 linear  spline  approximation.

    LAGRNG       Calculates the Lagrange multipliers by equation (1.4).

    SXATXI       Calculates the components of the linear spline approximation.

    ADDKNT       Adds a prescribed knot into the linear spline that occurs  in
                 CFLGRF. Calls subroutine PLUS.

    PLUS         Revises the normal equations of the linear spline  in  ADDKNT
                 when a knot is added.

    DELKNT       Deletes a prescribed knot from the linear spline that  occurs
                 in CFLGRF. Calls subroutine MINUS1.

    MINUS1       Revises the normal equations of the linear spline  in  DELKNT
                 when a knot is deleted.

    MESSGE       Contains certain messages associated with  the  operation  of
                 subroutine L2CXFT.
==============================================================================

3. THE USER INTERFACE
---------------------
The main subroutine that provides interface to the user is declared by

     SUBROUTINE L2CXFT(X,F,SX,I1,N,AKN,IAKN,COEF,NK,IACT,NACT,PAR,
    1  ITER,SXOLD,E,B,D,Z,U,DC,EC,PAROLD,RES,IPRINT,MODE)

Subroutine L2CXFT implements the quadratic programming method described in [1]
and [2]. It is is designed to handle sequences of data with variable lower and
upper array indices, I1 and N respectively. The user  need  only  provide  the
data pairs {(X(i),F(i)): i=I1,I1+1,...,N}.

On successful return from  L2CXFT,  SX(.)  satisfies  the  constraints  (1.2),
PAR(IACT(.)) is non-negative and MODE is set to one.

Since the objective function increases strictly monotonically at the estimates
SX(.) of the optimum that are generated when PAR(.) has  the  accepted  signs,
the subroutine terminates the calculation if two consecutive estimates fail to
give an increase. In this case all violations  of  the  constraints  are  very
small. The subroutine sets MODE=2 and returns with the message

     L2CXFT RETURNS BECAUSE THE ACCURACY IS INSUFFICIENT
     TO MAINTAIN INCREASING THE FUNCTION VALUES.

Thus L2CXFT guarantees termination because of  the  finite  precision  of  the
computer arithmetic. Evenmore  machine  dependence  is  avoided  by  employing
termination safeguards described in [1].

Subroutine MESSGE holds messages associated with the operation of  L2CXFT.  An
error  return  (MODE=4)  is  caused  if  N<I1,  as   well   as   (MODE=3)   if
ITER(1)>3*(N-I1+1). So far the numerical results  reported  by  Demetriou  and
Powell [2] indicate termination with ITER(1) much  less  than  the  number  of
data. Messages may be avoided by letting IPRINT=0 in the call of L2CXFT.



\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
APPENDIX A

SUBROUTINE LISTINGS
===================

In Appendix A we are given the source listings of the subroutines and lists of
internal variables. The Fortran implicit naming  of  the  variables  is  used.
Double precision versions of these procedures are received by simply  omitting
the comment star (*) in each source file where the line
*     IMPLICIT DOUBLE PRECISION (A-H,O-Z)
occurs. However, a  double  precision  version  of  our  subroutines  is  also
included in machine readable form.
     The source listings contain  the  numbered  source  code  lines  of  each
subroutine referred to in Section 3. The listings are followed  by  tables  of
local  symbols,  global  symbols  and  parameters  for  each  procedure.   The
subroutine arguments appear in the tables but they are not  explained  because
references are made in the beginning of each listing.
     The NAME column lists each global  symbol,  external  symbol  and  variable
     declared in the source file.
     The PARAMETER column lists each symbolic constant defined  in  a  PARAMETER
     statement.
     The CLASS column contains either subroutine, function, global and  external
     or argument and local symbols.
     The TYPE column shows a simplified version of the symbol's type as declared
     in the source file. We leave the column empty when an argument occurs.
     The EXPLANATION column gives a simplified explanation to the symbol used in
     the source file.
     The VALUE field appears only for parameter symbols.


Subroutine L2CXFT
-----------------

 Line#  Source Line

     1  C......................................................................
     2  C     L2CXFT: A FORTRAN SUBROUTINE FOR LEAST SQUARES DATA FITTING
     3  C             WITH NON-NEGATIVE SECOND DIVIDED DIFFERENCES.
     4  C     BY I.C. DEMETRIOU, DEPARTMENT OF ECONOMICS, UNIVERSITY OF ATHENS,
     5  C             8 PESMAZOGLOU STREET, ATHENS 105 59, GREECE.
     6  C             TEL   : (GR) 01-3242438, 8017732
     7  C             E-MAIL: DEMETRI@AUEB.ARIADNE-T.GR
     8  C......................................................................
     9  C     THE USER GIVES THE NOISY FUNCTION MEASUREMENTS F(I): I=1,2,...N
    10  C      AT THE ABSCISSAE X(1)<X(2)<...<X(N),
    11  C     AND THIS SUBROUTINE CALCULATES THE N-TH COMPONENT VECTOR SX(.)
    12  C
    13  C           THAT MINIMIZES THE SUM OF THE SQUARES OF THE ERRORS
    14  C            SX(I)-F(I): I=1,2,...,N
    15  C           SUBJECT TO NON-NEGATIVITY OF SECOND DIVIDED DIFFERENCES
    16  C            OF THE SMOOTHED VALUES SX(.).
    17  C
    18  C     IN THIS SENSE, SX(.) IS
    19  C                   THE BEST CONVEX FIT TO F(.)
    20  C                 OR THE CONVEX REGRESSION ON F(.)
    21  C
    22  C     THERE ARE EXACTLY N-2 CONSTRAINTS THAT GIVE A HIGHLY STRUCTURED
    23  C      CALCULATION WHICH IS SOLVED BY A SPECIAL DUAL FEASIBLE QUADRATIC
    24  C      PROGRAMMING ALGORITHM INITIALIZED BY A O(N) STARTING PROCEDURE.
    25  C
    26  C     THE CONCAVE FITTING CAN BE TREATED AS CONVEX AFTER AN OVERALL
    27  C      CHANGE OF SIGN.
    28  C
    29  C     REF:  I.C.DEMETRIOU AND M.J.D. POWELL, "THE MINIMUM SUM OF
    30  C           SQUARES CHANGE TO UNIVARIATE DATA THAT GIVES CONVEXITY",
    31  C           IMA J. OF NUMERICAL ANALYSIS, 11(1991), PP. 433-448.
    32  C
    33  C     APPLICATIONS: DATA SMOOTHING, STATISTICAL ANALYSIS, ECONOMICS.
    34  C
    35  C     CALLS SUBROUTINES ADDKNT, CFLGRF, DELKNT, L2ILS AND MESSGE.
    36  C......................................................................
    37        SUBROUTINE L2CXFT(X,F,SX,I1,N,AKN,IAKN,COEF,NK,IACT,NACT,PAR,
    38       1  ITER,SXOLD,E,B,D,Z,U,DC,EC,PAROLD,RES,IPRINT,MODE)
    39  *     IMPLICIT DOUBLE PRECISION (A-H,O-Z)
    40        DIMENSION X(I1:N),F(I1:N),SX(I1:N),COEF(I1-1:N),AKN(I1-2:N),
    41       1  IAKN(I1-1:N),IACT(I1:N),PAR(I1:N),DC(I1:N),EC(I1:N),
    42       2  E(I1-1:N),B(I1-1:N),D(I1-1:N),Z(I1-1:N),U(I1-1:N),
    43       3  SXOLD(I1:N),PAROLD(I1:N),RES(I1-1:N),ITER(*)
    44  C
    45  C..... I N P U T .....
    46  C      I1      INTEGER VARIABLE, LOWER DATA INDEX.
    47  C      N       INTEGER VARIABLE, UPPER DATA INDEX.
    48  C      X(I1:N) REAL ARRAY OF ABSCISSAE.
    49  C      F(I1:N) REAL ARRAY OF FUNCTION MEASUREMENTS.
    50  C      IPRINT  INTEGER VARIABLE. IF IPRINT=1 THEN SUBROUTINE MESSGE
    51  C               PRODUCES OUTPUT.
    52  C
    53  C .....O U T P U T .....
    54  C      SX(I1:N) REAL ARRAY CONTAINING THE SPLINE COMPONENTS AT X(I),
    55  C                I=I1,I1+1,...,N IE THE BEST CONVEX FIT TO F(.).
    56  C      NK      INTEGER VARIABLE, UPPER INDEX OF SPLINE KNOTS SEQUENCE.
    57  C      NACT    INTEGER VARIABLE, SUCH THAT EITHER NACT=I1-1 OR
    58  C               (NACT-I1+1) IS EQUAL TO THE NUMBER OF ACTIVE CONSTRAINT
    59  C               IN THE SOLUTION.
    60  C      AKN(I1-2:NK)  REAL ARRAY CONTAINING THE SPLINE KNOTS AND THE
    61  C               DUMMY COMPONENT AKN(I1-2)=X(I1).
    62  C      IAKN(I1-1:NK)  INTEGER ARRAY CONTAINING THE DATA POINT INDICES
    63  C               OF THE ASSOCIATED KNOTS.
    64  C      COEF(I1-1:NK)  REAL ARRAY CONTAINING THE SPLINE COEFFICIENTS
    65  C               AT AKN(I), I=I1-1,I1,...,NK.
    66  C      IACT(I1:NACT)  INTEGER ARRAY CONTAINING THE INDICES OF THE
    67  C              ACTIVE CONSTRAINTS AT THE SOLUTION.
    68  C      PAR(I1:N-2)  INTEGER ARRAY CONTAINING IN PAR(IACT(.))
    69  C               THE LAGRANGE MULTIPLIERS OF THE ACTIVE CONSTRAINTS.
    70  C      ITER(*) INTEGER ARRAY WHOSE ELEMENTS ARE AS FOLLOWS:
    71  C              ITER(1)  KEEPS THE NUMBER OF ITERATIONS AT THE END
    72  C                        OF THE CALCULATION. IF ITER(1) EXCEEDS
    73  C                        THE NUMBER 3*(N-I1+1) THEN TERMINATION OCCURS
    74  C                        WITH THE MESSAGE
    75  C                         'L2CXFT QUITS ON ITERATION COUNT'
    76  C              ITER(2)  KEEPS THE NUMBER OF ACTIVE CONSTRAINTS AT THE
    77  C                        END OF THE CALL OF SUBROUTINE L2ILS.
    78  C              ITER(3)  KEEPS THE NUMBER OF CALLS OF SUBROUTINE
    79  C                        CFLGRF.
    80  C              ITER(4)  KEEPS THE NUMBER OF ACTIVE CONSTRAINTS WHEN
    81  C                        FIRST FEASIBLE LAGRANGIAN VECTOR IS FOUND
    82  C                        JUST AFTER THE CALL OF SUBROUTINE L2ILS.
    83  C              ITER(5)  KEEPS THE NUMBER OF CONSTRAINT DELETIONS FROM
    84  C                        THE ACTIVE SET.
    85  C              ITER(6)  KEEPS THE NUMBER OF CONSTRAINT ADDITIONS TO
    86  C                        THE ACTIVE SET AFTER FIRST FEASIBLE PAR(.).
    87  C      MODE    INTEGER VARIABLE THAT IS SET AUTOMATICALLY BY THE
    88  C               SUBROUTINE TO INDICATE THE TERMINATION STATUS.
    89  C              1 = SUCCESSFUL TERMINATION
    90  C              2 = TERMINATION DUE TO NON-INCREASE OF OBJECTIVE FUNCTIO
    91  C              3 = NUMBER OF 3*(N-I1+1) ITERATIONS HAS EXCEEDED
    92  C              4 = ERROR RETURN BECAUSE (N .LT. I1).
    93  C
    94  C.... M E S S A G E S ....
    95  C     INCLUDED IN SUBROUTINE MESSGE AND ACTIVATED WHEN INPUT PARAMETER
    96  C      IPRINT IS SET BY THE USER TO ONE.
    97  C
    98  C.... W O R K I N G   S P A C E .....
    99  C      E(I1-1:NK)  REAL ARRAY THAT HOLDS THE DIAGONAL OF THE NORMAL
   100  C              EQUATIONS ASSOCIATED WITH SPLINE SX(.).
   101  C      D(I1-1:NK)  REAL ARRAY THAT HOLDS THE SUBDIAGONAL OF THE
   102  C              NORMAL EQUATIONS ASSOCIATED WITH SX(.).
   103  C      B(I1-1:NK)  REAL ARRAY THAT HOLDS THE RIGHT HAND SIDE OF
   104  C              THE NORMAL EQUATIONS.
   105  C      EC(I1:N-2)  REAL ARRAY SUCH THAT EC(I)=(SECOND COMPONENT OF
   106  C              THE I-TH DIVIDED DIFFERENCE AFTER SCALING).
   107  C      DC(I1:N-2)  REAL ARRAY SUCH THAT DC(I+1)=(THIRD COMPONENT OF
   108  C              THE I-TH DIVIDED DIFFERENCE AFTER SCALING).
   109  C      PAROLD(I1:N-2)  REAL ARRAY THAT HOLDS THE LAGRANGE MULTIPLIERS
   110  C              THAT OCCURED AT THE FORMER ITERATION. IT IS
   111  C              PAROLD(IACT(.)).GT.0. .
   112  C      SXOLD(I1:N) REAL ARRAY THAT HOLDS THE SPLINE COMPONENTS
   113  C              THAT OCCURED AT THE FORMER ITERATION.
   114  C      RES(I1-1:NK)  REAL ARRAY THAT IS USED TO KEEP THE RESIDUALS OF
   115  C              THE NORMAL EQUATIONS AT COEF(.) AND THE CORRECTIONS OF
   116  C              COEF(.). IT IS ALSO USED TO KEEP THE RESIDUALS OF THE
   117  C              LANGRANGIAN EQUATIONS AT PAR(.) AND THE CORRECTIONS TO
   118  C              PAR(.).
   119  C      U(I1-1,N) REAL ARRAY PROVIDING SPACE FOR FACTORIZATIONS.
   120  C      Z(I1-1,N) REAL ARRAY PROVIDING SPACE FOR FACTORIZATIONS.
   121  C      ITREF   INTEGER VARIABLE. IF ITREF=1 THEN ITERATIVE REFINEMENT
   122  C               IS INITIATED.
   123  C      ITEST   INTEGER VARIABLE. IF ITEST=1 THEN A RETURN IS CAUSED DUE
   124  C               TO NOT INCREASING OF THE FUNCTION VALUES.
   125  C
   126  C .....M E T H O D (DUAL-FEASIBLE ALGORITHM 3 IN QUOTED REFERENCE).
   127  C      VECTOR SX(.) IS CALCULATED BY THIS SUBROUTINE AS FOLLOWS:
   128  C        STEP 0   CALL SUBROUTINE L2ILS TO DERIVE AN INITIAL
   129  C                  APPROXIMATION TO SX(.).
   130  C        STEP 1   USE THIS APPROXIMATION AS STARTING POINT OF A
   131  C                  SPECIAL QUADRATIC PROGRAMMING (QP) METHOD THAT
   132  C                  COMPLETES THE CALCULATION OF SX(.).
   133  C
   134  C      FEATURES OF THE QP METHOD:
   135  C              A) IT GENERATES INFEASIBLE ESTIMATES OF THE OPTIMUM,
   136  C              B) IT KEEPS A SET OF ACTIVE CONSTRAINTS THAT ARE
   137  C                  ASSOCIATED WITH NON-NEGATIVE LAGRANGE MULTIPLIERS,
   138  C              C) THE OBJECTIVE FUNCTION ACHIEVES A STRICTLY LARGER
   139  C                  VALUE ANY TIME A NEW ITERATION BEGINS.
   140  C              D) POWELL'S SAFEGUARD TERMINATION TEST IS APPLIED
   141  C                  WHEN ACCURACY IS INSUFFICIENT TO MAINTAIN INCREASING
   142  C                  FUNCTION VALUES.
   143  C              E) ITERATIVE REFINEMENT IS CALLED AUTOMATICALLY IN
   144  C                  CONJUNCTION WITH D) IN ORDER TO IMPROVE ACCURACY.
   145  C
   146  C      IMPLEMENTATION OF THE QP METHOD:
   147  C      A) CALCULATION OF AN ESTIMATE SX(.) OF THE OPTIMUM:
   148  C          EXPRESS SPLINE SX(.) AS A LINEAR COMBINATION OF LINEAR
   149  C          B-SPLINES
   150  C              SX(I)=SIGMA(COEF(J)*N(J,I), J=I1-1,I1,...,NK)
   151  C                                           FOR I=I1,I1+1,...,N ,
   152  C          WHERE N(J,I)=THE I-TH COMPONENT OF THE J-TH LINEAR B-SPLINE.
   153  C          DENOTE BY <.,.> THE INNER PRODUCT OF TWO VECTORS AND,
   154  C          THE COEFFICIENTS OF SX(.) ARE DETERMINED BY SOLVING THE
   155  C          THE POSITIVE DEFINITE SYSTEM OF THE NORMAL EQUATIONS
   156  C          EFFICIENTLY AND STABLY BY CHOLESKY FACTORIZATION
   157  C              D(J)*COEF(J-1)+E(J)*COEF(J)+D(J+1)*COEF(J+1)=B(J)
   158  C                                           FOR J=I1-1,I1,...,NK
   159  C          WHERE BY <.,.> IS DENOTED THE SCALAR PRODUCT OF TWO VECTORS
   160  C          AND
   161  C              D(J)=<N(J,.),N(J-1,.)>, J=I1,I1+1,...,NK
   162  C              E(J)=<N(J,.),N(J,.)>, J=I1-1,I1,...,NK
   163  C              B(J)=<N(J,.),F(.)>, J=I1-1,I1,...,NK.
   164  C          (SUBROUTINE CFLGRF).
   165  C
   166  C      B) CALCULATION OF THE LAGRANGE MULTIPLIERS
   167  C          THE LAGRANGE EQUATIONS AT AN ESTIMATE SX(.) ARE
   168  C              2*(SX(II+1)-F(II+1))=SIGMA(PAR(II)*A(II,.))
   169  C                                    FOR II=IACT(I), I=I1,I1+1,...,NACT
   170  C          WHERE A(II,J) IS THE J-TH COMPONENT OF THE NORMAL
   171  C          OF THE II-TH CONSTRAINT AND
   172  C              A(II,J)<>0 ONLY FOR (II.LE.J.LE.II+2).
   173  C          (ARRAY A(.,.) IS NOT ACTUALLY USED IN THIS SUBROUTINE;
   174  C          INSTEAD ARRAYS EC(.) AND DC(.) ARE EMPLOYED.). BECAUSE
   175  C          THIS SYSTEM IS OVERDETERMINED PAR(IACT(.)) IS DERIVED
   176  C          BY CHOOSING FROM THE LAGRANGE EQUATIONS THOSE EQUATIONS THAT
   177  C          CORRESPOND TO THE SECOND NON-ZERO COMPONENT OF A(IACT(.),.);
   178  C          SO A BLOCK DIAGONAL POSITIVE DEFINITE SYSTEM IS OBTAINED THA
   179  C          IS SOLVED EFFICIENTLY AND STABLY BY CHOLESKY FACTORIZATION.
   180  C          (SUBROUTINE CFLGRF).
   181  C
   182  C      C) PARTICULAR METHODS ARE DEVELOPED FOR INSERTING INTO AND
   183  C          DELETING FROM THE SPLINE APPROXIMATION ONE KNOT ECONOMICALLY
   184  C          (SUBROUTINES ADDKNT AND DELKNT).
   185  C......................................................................
   186  C     SET CERTAIN INITIAL VALUES.
   187  C
   188        MODE=1
   189        I0=I1-1
   190        ITREF=0
   191        ITEST=0
   192        ZERO=0.
   193        DO 10 I=1,10
   194  10       ITER(I)=0
   195  C
   196        IF (N.LT.I1) THEN
   197            MODE=4
   198            CALL MESSGE(ZERO,0,0,ITER,10)
   199            GO TO 1000
   200        END IF
   201  C
   202  C     IF N=I1 OR N=I1+1 THEN THE DATA ITSELF IS THE REQUIRED FIT.
   203  C
   204        IF (N.EQ.I1) THEN
   205            SX(I1)=F(I1)
   206            AKN(I1-1)=X(I1)
   207            IAKN(I1-1)=I1
   208            COEF(I1-1)=F(I1)
   209            CALL MESSGE(ZERO,0,0,ITER,20)
   210            GO TO 1000
   211        END IF
   212  C
   213        IF (N.EQ.I1+1) THEN
   214            SX(I1)=F(I1)
   215            SX(N)=F(N)
   216            AKN(I1-1)=X(I1)
   217            AKN(I1)=X(N)
   218            IAKN(I1-1)=I1
   219            IAKN(I1)=N
   220            COEF(I1-1)=F(I1)
   221            COEF(I1)=F(N)
   222            CALL MESSGE(ZERO,0,0,ITER,20)
   223            GO TO 1000
   224        END IF
   225  C
   226  C.... I N I T I A L I Z E .............................................
   227  C
   228  C     THERE ARE N-2 CONSTRAINTS DEFINED BY THE DIVIDED DIFFERENCES.
   229  C      WE ASSOCIATE THE I-TH CONSTRAINT WITH THE I-TH DIVIDED DIFFER-
   230  C      ENCE. SET COEFFICIENTS OF FULL SYSTEM OF EQUATIONS OF LAGRANGE
   231  C      MULTIPLIERS. SINCE GRAD(F)=2*(SX-F), THE COEFFICIENTS ARE
   232  C      SCALED BY 2.
   233  C
   234        DO 50 I=I1,N-3
   235           CX2=X(I+2)-X(I+1)
   236           CX1=X(I+1)-X(I)
   237           CX3=X(I+2)-X(I)
   238           CX2=1/CX2
   239           CX1=1/CX1
   240           EC(I)=-(CX1+CX2)/2
   241  50       DC(I+1)=CX2/2
   242        CX2=X(N)-X(N-1)
   243        CX1=X(N-1)-X(N-2)
   244        CX3=X(N)-X(N-2)
   245        CX2=1/CX2
   246        CX1=1/CX1
   247        EC(N-2)=-(CX1+CX2)/2
   248  C
   249        DO 60 I=I1,N-2
   250  60       PAR(I)=0.0
   251  C
   252  C.... CALCULATE STARTING POINT BY L2ILS ...............................
   253  C
   254        CALL L2ILS(COEF,AKN,IAKN,D,E,B,Z,U,NK,F,X,I1,N)
   255  C
   256  C     INITIALIZE INDICES OF ACTIVE CONSTRAINTS IN IACT(.).
   257  C
   258        J=I0
   259        I=I1+1
   260        IAKN(I0)=I1
   261        KL=I0
   262  80    IF (IAKN(J).LT.I .AND. I.LT.IAKN(J+1)) THEN
   263            KL=KL+1
   264            IACT(KL)=I-1
   265            I=I+1
   266            GO TO 80
   267        END IF
   268        J=J+1
   269        I=I+1
   270        IF (J.LT.NK) GO TO 80
   271        NACT=KL
   272        ITER(2)=NACT-I0
   273  C
   274  C.... ITERATE BY ONE, UNTIL FIRST FEASIBLE LAGRANGIAN VECTOR IS FOUND.
   275  C
   276  C     CALCULATE COEF OVER KNOTS, SPLINE OVER ABSCISSAE AND
   277  C      LAGRANGE MULTIPLIERS.
   278  C
   279  90    CALL CFLGRF(SX,PAR,COEF,IACT,E,B,D,X,AKN,IAKN,F,DC,EC,U,
   280       1  RES,NK,NACT,I1,N,ITREF,ITER(3))
   281        ITER(3)=ITER(3)+1
   282  C
   283  C     FIND MINIMUM LAGRANGE MULTIPLIER.
   284  C
   285        IF (NACT .LE. I0) GO TO 150
   286        AMINLA=PAR(IACT(I1))
   287        IPAR=IACT(I1)
   288        IF (I1 .EQ. NACT) GO TO 110
   289        DO 100 I=I1+1,NACT
   290           IF (PAR(IACT(I)) .LT. AMINLA) THEN
   291               AMINLA=PAR(IACT(I))
   292               IPAR=IACT(I)
   293           END IF
   294  100   CONTINUE
   295  110   ITER(4)=NACT-I0
   296        IF (AMINLA .GE. 0.0) GO TO 150
   297  C
   298  C     INSERT A KNOT WHERE THE LEAST NEGATIVE LAGRANGE MULTIPLIER.
   299  C
   300        INKNOT=IPAR+1
   301        PAR(IPAR)=0.0
   302        CALL ADDKNT(INKNOT,E,B,D,X,F,AKN,IAKN,IACT,NK,NACT,I1,N)
   303        GO TO 90
   304  C
   305  C.... M A I N  I T E R A T I O N ......................................
   306  C
   307  150   CONTINUE
   308  C
   309  C     EXAMINE CONVEXITES AT ALL KNOTS OF SPLINE APPROXIMATION.
   310  C      SPECIAL CASE: IF NK-I0=1 THEN SX(.) IS A STRAIGHT LINE.
   311  C
   312        IF (NK-I0 .EQ. 1) GO TO 1000
   313  C
   314  C     FIND THE KNOT OF THE MOST VIOLATED CONSTRAINT.
   315  C
   316        CVMAX=0.
   317        KL=I0
   318        K=0
   319        DO 160 J=I1,NK-1
   320           JJ=IAKN(J)
   321           CKNOT=(SX(JJ+1)-SX(JJ))/(X(JJ+1)-X(JJ))-
   322       1         (SX(JJ)-SX(JJ-1))/(X(JJ)-X(JJ-1))
   323           SUM2=1/(X(JJ+1)-X(JJ))**2+
   324       1   ((X(JJ+1)-X(JJ-1))/((X(JJ+1)-X(JJ))*(X(JJ)-X(JJ-1))))**2+
   325       2   1/(X(JJ)-X(JJ-1))**2
   326           SUM2=SQRT(SUM2)
   327           CKNOT=CKNOT/SUM2
   328           IF (CKNOT .LT. 0.) K=K+1
   329           IF (CKNOT .LT. CVMAX) THEN
   330               CVMAX=CKNOT
   331               KNTOUT=J
   332               IAKNJ=IAKN(J)
   333               KL=KL+1
   334           END IF
   335  160   CONTINUE
   336  C
   337  C     IF KL=I0 THEN SX(.) IS CONVEX. SINCE AT THIS LEVEL PAR(.) ARE
   338  C      ALL NON-NEGATIVE THE KUHN-TUCKER CONDITIONS ARE SATISFIED.
   339  C
   340  C.... T E R M I N A T I O N ...........................................
   341  C
   342        IF (KL .EQ. I0) GO TO 1000
   343  C
   344  C     MSG: PRINT CVMAX,IAKNJ,K.
   345  C
   346        IF (IPRINT.NE.0) CALL MESSGE(CVMAX,K,IAKNJ,ITER,160)
   347  C
   348  C     POWELL'S SAFEGUARD TERMINATION TEST:
   349  C      RETURN, IF DUE TO ROUNDING ERRORS, THE CHANGE IN SX(.) MAY
   350  C      NOT INCREASE THE OBJECTIVE FUNCTION.
   351  C
   352        IF (ITER(1).EQ.0) GO TO 190
   353            R=0.0
   354            T=0.0
   355            DO 170 I=I1,N
   356               R=R+(SX(I)-SXOLD(I))*(SX(I)+SXOLD(I)-2*F(I))
   357  170          T=T+ABS(SX(I)-SXOLD(I))*(ABS(SX(I)+SXOLD(I))+2*ABS(F(I)))
   358            IF (T+R.LE.T .OR. T+1.5*R.LE.T+R) THEN
   359                IF (ITEST.EQ.1) THEN
   360                    MODE=2
   361                    IF (IPRINT.NE.0) CALL MESSGE(ZERO,0,0,ITER,170)
   362  C
   363  C                     MSG: L2CXFT RETURNS BECAUSE THE ACCURACY IS
   364  C                          INSUFFICIENT TO MAINTAIN INCREASING
   365  C                          THE FUNCTION VALUES.
   366  C
   367                    GO TO 1000
   368                END IF
   369  C
   370                IF (IPRINT.EQ.0) GO TO 180
   371                IF (ITREF.EQ.0) CALL MESSGE (ZERO,0,0,ITER,180)
   372  C
   373  C                 MSG: ITERATIVE REFINEMENT IS INITIATED.
   374  C
   375  180           ITREF=1
   376                ITEST=1
   377            ELSE
   378                ITEST=0
   379            END IF
   380  190   CONTINUE
   381  C
   382  C     KEEP OLD LAGRANGE MULTIPLIERS AND OLD SPLINE APPROXIMATION.
   383  C
   384        DO 200 I=I1,N-2
   385  200      PAROLD(I)=PAR(I)
   386        DO 210 I=I1,N
   387  210      SXOLD(I)=SX(I)
   388  C
   389  C     TERMINATION ON ITERATION COUNT.
   390  C
   391        ITER(1)=ITER(1)+1
   392        IF (ITER(1).GT.3*(N-I0)) THEN
   393            MODE=3
   394            CALL MESSGE(ZERO,0,0,ITER,210)
   395  C
   396  C         MSG: L2CXFT QUITS ON ITERATION COUNT.
   397  C
   398            GO TO 1000
   399        END IF
   400  C
   401  C     CALCULATE A SEARCH DIRECTION (DELETE THE KNOT KNTOUT).
   402  C
   403        CALL DELKNT(E,B,D,AKN,IAKN,IACT,NK,NACT,I1,N,KNTOUT)
   404        ITER(6)=ITER(6)+1
   405  C
   406  C     SOLVE FOR SX(.) OVER AKN(.).
   407  C
   408  220   CALL CFLGRF(SX,PAR,COEF,IACT,E,B,D,X,AKN,IAKN,F,DC,EC,U,
   409       1  RES,NK,NACT,I1,N,ITREF,ITER(3))
   410        ITER(3)=ITER(3)+1
   411  C
   412        IPAR=IAKNJ-1
   413        IF (IPRINT.NE.0) CALL MESSGE(PAR(IPAR),0,0,ITER,220)
   414  C
   415  C     MSG: PRINT MULTIPLIER OF INSERTED CONSTRAINT.
   416  C
   417  C     APPLY POWELL'S TECHNIQUE IN ORDER THAT THE INDEX IPAR
   418  C      REMAIN IN ACTIVE SET. SET PAR(IPAR)=MAX(PAR(IPAR),0.0)
   419  C      BECAUSE IN THEORY HOLDS THAT PAR(IPAR)>0.
   420  C
   421        IF (PAR(IPAR).LT.0.0) PAR(IPAR)=0.0
   422  C
   423  C     EXAMINE SIGN OF LAGRANGE MULTIPLIERS
   424  C
   425  300   IF (NACT .EQ. I0) GO TO 150
   426        KL=I0
   427        THETA=2.0
   428        DO 320 I=I1,NACT
   429           K=IACT(I)
   430           IF (PAR(K)) 310,320,320
   431  310      RATIO=PAROLD(K)/(PAROLD(K)-PAR(K))
   432           IF (THETA .LE. RATIO) GO TO 320
   433               THETA=RATIO
   434               IPAR=K
   435               KL=I1
   436  320      CONTINUE
   437  C
   438  C.... ITERATE IN THE PRIMAL SPACE .....................................
   439  C     IF KL=I0 THEN PAR(.) ARE NON-NEGATIVE. BRANCH WHERE TEST
   440  C      PRIMAL FEASIBILITY.
   441  C
   442        IF (KL .EQ. I0) GO TO 150
   443  C
   444  C.... RECOVER NON-NEGATIVITY OF LAGRANGE MULTIPLIERS ..................
   445  C
   446        DO 340 I=I1,NACT
   447           K=IACT(I)
   448  340      PAROLD(K)=(1-THETA)*PAROLD(K)+THETA*PAR(K)
   449  C
   450  C     INSERT KNOT IPAR+1 INTO THE SPLINE AND SOLVE FOR SX(.).
   451  C
   452        I1NEW=I1
   453  350   INKNOT=IPAR+1
   454        PAR(IPAR)=0.
   455        CALL ADDKNT(INKNOT,E,B,D,X,F,AKN,IAKN,IACT,NK,NACT,I1,N)
   456        ITER(5)=ITER(5)+1
   457  C
   458  C     TEST THE FEASIBILITY OF PAROLD(.). ALL PAROLD(.) MUST BE
   459  C      NON-NEGATIVE BECAUSE OF THE WAY THETA WAS DETERMINED. OTHERWISE,
   460  C      THIS IS DUE TO ROUND-OFF ERROR. HENCE, ANY NEGATIVITY
   461  C      IS TREATED AS BEING ZERO. SEE LAWSON & HANSON (SOLVING
   462  C      LEAST SQUARES PROBLEMS, PRENTICE-HALL, 1974, p.307).
   463  C
   464        IF (NACT .EQ. I0) GO TO 370
   465        IF (I1NEW .GT. NACT) GO TO 370
   466        DO 360 I=I1NEW,NACT
   467           IPAR=IACT(I)
   468           IF (PAROLD(IPAR) .LT. 0.0) THEN
   469               IF (IPRINT.NE.0) CALL MESSGE(PAROLD(IPAR),IPAR,0,ITER,350)
   470  C
   471  C                MSG: ITERATION IN THE DUAL SPACE DUE TO ROUND OFF.
   472  C                PRINT ACTIVE CONSTRAINT AND LAGRANGE MULTIPLIER.
   473  C
   474               I1NEW=I
   475               GO TO 350
   476           END IF
   477  360   CONTINUE
   478  C
   479  370   CONTINUE
   480  C
   481        CALL CFLGRF(SX,PAR,COEF,IACT,E,B,D,X,AKN,IAKN,F,DC,EC,U,
   482       1  RES,NK,NACT,I1,N,ITREF,ITER(3))
   483        ITER(3)=ITER(3)+1
   484  C
   485  C.... ITERATE IN THE DUAL SPACE .......................................
   486  C
   487        GO TO 300
   488  1000  CONTINUE
   489  C
   490        CALL MESSGE(ZERO,NACT-I0,MODE,ITER,1000)
   491  C
   492  C     MSG: PRINT MODE AND
   493  C          INITIAL ACTIVE SET
   494  C          STARTING ACTIVE SET
   495  C          FINAL ACTIVE SET
   496  C          ADDITIONS OF CONSTRAINTS
   497  C          DELETIONS OF CONSTRAINTS
   498  C
   499  C.... END OF SUBROUTINE L2CXFT ........................................
   500  C
   501        RETURN
   502        END

L2CXFT  Local Symbols

NAME                      CLASS       TYPE         EXPLANATION

MODE. . . . . . . . . . . argument
IPRINT. . . . . . . . . . argument
RES . . . . . . . . . . . argument
PAROLD. . . . . . . . . . argument
EC. . . . . . . . . . . . argument
DC. . . . . . . . . . . . argument
U . . . . . . . . . . . . argument
Z . . . . . . . . . . . . argument
D . . . . . . . . . . . . argument
B . . . . . . . . . . . . argument
E . . . . . . . . . . . . argument
SXOLD . . . . . . . . . . argument
ITER. . . . . . . . . . . argument
PAR . . . . . . . . . . . argument
NACT. . . . . . . . . . . argument
IACT. . . . . . . . . . . argument
NK. . . . . . . . . . . . argument
COEF. . . . . . . . . . . argument
IAKN. . . . . . . . . . . argument
AKN . . . . . . . . . . . argument
N . . . . . . . . . . . . argument
I1. . . . . . . . . . . . argument
SX. . . . . . . . . . . . argument
F . . . . . . . . . . . . argument
X . . . . . . . . . . . . argument

AMINLA. . . . . . . . . . local       REAL         min Lagrange multiplier
CKNOT . . . . . . . . . . local       REAL         temporary
CVMAX . . . . . . . . . . local       REAL         max constraint violation
CX1 . . . . . . . . . . . local       REAL         temporary
CX2 . . . . . . . . . . . local       REAL         temporary
CX3 . . . . . . . . . . . local       REAL         temporary
I . . . . . . . . . . . . local       INTEGER      temporary
I0. . . . . . . . . . . . local       INTEGER      I0=I1-1
ITREF . . . . . . . . . . local       INTEGER      see comments on working space
ITEST . . . . . . . . . . local       INTEGER      see comments on working space
INKNOT. . . . . . . . . . local       INTEGER      data index of inserted knot
IPAR. . . . . . . . . . . local       INTEGER      temporary
IAKNJ . . . . . . . . . . local       INTEGER      data index of KNOUT
J . . . . . . . . . . . . local       INTEGER      temporary
JJ. . . . . . . . . . . . local       INTEGER      temporary
K . . . . . . . . . . . . local       INTEGER      temporary
KL. . . . . . . . . . . . local       INTEGER      temporary
KNTOUT. . . . . . . . . . local       INTEGER      index of deleted knot
R . . . . . . . . . . . . local       REAL         residual of obj function
RATIO . . . . . . . . . . local       REAL         temporary
SUM2. . . . . . . . . . . local       REAL         temporary
T . . . . . . . . . . . . local       REAL         abs residual of obj function
THETA . . . . . . . . . . local       REAL         0  THETA < 1
ZERO. . . . . . . . . . . local       REAL         ZERO=0.

L2CXFT  Global Symbols

NAME                      CLASS         NUMBER of lines of code
                                        including comments
ADDKNT. . . . . . . . . . external
CFLGRF. . . . . . . . . . external
DELKNT. . . . . . . . . . external
L2CXFT. . . . . . . . . . SUBROUTINE    502
L2ILS . . . . . . . . . . external
MESSGE. . . . . . . . . . external



Subroutine L2ILS
----------------

 Line#  Source Line

     1  C......................................................................
     2  C     GIVEN N NOISY FUNCTION MEASUREMENTS F(I): I=1,2,...N
     3  C      AT THE ABSCISSAE X(1)<X(2)<...<X(N),
     4  C     THIS SUBROUTINE CALCULATES IN ONLY O(N) COMPUTER OPERATIONS AN
     5  C      EXCELLENT STARTING POINT FOR THE FOLLOWING DATA FIT CALCULATION:
     6  C
     7  C      FIND SX(.) THAT MINIMIZES THE SUM OF THE SQUARES OF THE ERRORS
     8  C            SX(I)-F(I): I=1,2,...,N
     9  C      SUBJECT TO NON-NEGATIVITY OF SECOND DIVIDED DIFFERENCES
    10  C            OF THE SMOOTHED VALUES SX(.).
    11  C
    12  C     SX(.) APPEARS DUE A B-SPLINE REPRESENTATION (SEE METHOD BELOW).
    13  C......................................................................
    14  C     THE ALGORITHM OF THIS CODE CAN BE FOUND IN REF 1.
    15  C     REF 1: "THE MINIMUM SUM OF SQUARES CHANGE TO UNIVARIATE DATA
    16  C             THAT GIVES CONVEXITY"
    17  C             BY I.C. DEMETRIOU AND M.J.D. POWELL, TO APPEAR IN
    18  C             IMA JOURNAL OF NUMERICAL ANALYSIS, 1991.
    19  C     A REPORT ON THIS CODE CAN BE FOUND IN REF 2.
    20  C     REF 2: "REPORT ON THE RERFORMANCE OF THE O(N) ALGORITHM THAT
    21  C             INITIATES THE QUADRATIC PROGRAMMING CALCULATION OF
    22  C             SUBROUTINE L2CXFT", BY I.C.DEMETRIOU, HELLENIC AIR FORCE
    23  C             ACADEMY, DEPT. OF MATHEMATICS 1990/NA2 (ATHENS, GREECE).
    24  C.......................................................................
    25          SUBROUTINE L2ILS(COEF,AKN,IAKN,D,E,B,Z,U,NK,F,X,I1,N)
    26  *       IMPLICIT DOUBLE PRECISION (A-H,O-Z)
    27          DIMENSION X(I1:N),F(I1:N),COEF(I1-1:N),AKN(I1-2:N),
    28       1    IAKN(I1-1:N),D(I1-1:N),E(I1-1:N),B(I1-1:N),Z(I1-1:N),U(I1-1:N)
    29  C
    30  C ..... I N P U T .....
    31  C       I1      INTEGER VARIABLE, LOWER DATA INDEX.
    32  C       N       INTEGER VARIABLE, UPPER DATA INDEX.
    33  C       X(I1:N) REAL ARRAY OF ABSCISSAE.
    34  C       F(I1:N) REAL ARRAY OF MEASUREMENTS.
    35  C
    36  C ..... O U T P U T .....
    37  C       NK      INTEGER VARIABLE, UPPER INDEX OF SPLINE KNOTS SEQUENCE.
    38  C       AKN(I1-2:NK)  REAL ARRAY CONTAINING THE SPLINE KNOTS, WHERE
    39  C               AKN(I1-2)=AKN(I1-1).
    40  C       IAKN(I1-1:NK)  INTEGER ARRAY CONTAINING THE DATA POINT INDICES
    41  C               OF THE ASSOCIATED KNOTS.
    42  C       COEF(I1-1:NK)  REAL ARRAY CONTAINING THE SPLINE COEFFICIENTS
    43  C               AT AKN(I), I=I1-1,I1,...,NK.
    44  C
    45  C ..... W O R K I N G   S P A C E .....
    46  C       E(I1-1:N)  REAL ARRAY THAT HOLDS THE DIAGONAL OF THE NORMAL
    47  C               EQUATIONS ASSOCIATED WITH SPLINE SX(.).
    48  C       D(I1-1:N)  REAL ARRAY THAT HOLDS THE SUBDIAGONAL OF THE
    49  C               NORMAL EQUATIONS ASSOCIATED WITH SX(.).
    50  C       U(I1-1:N)  REAL ARRAY THAT HOLDS THE DIAGONAL OF CHOLESKY
    51  C               FACTORIZATION OF THE NORMAL EQUATIONS.
    52  C       B(I1-1:N)  REAL ARRAY THAT HOLDS THE RIGHT HAND SIDE OF
    53  C               THE NORMAL EQUATIONS.
    54  C       Z(I1-1:N)  REAL ARRAY THAT HOLDS THE RIGHT HAND SIDE OF
    55  C               THE CHOLESKY FACTORIZATION.
    56  C
    57  C ..... M E T H O D (ALGORITHM 1 IN QUOTED REFERENCE) .....
    58  C       EXPRESS SPLINE SX(.) AS A LINEAR COMBINATION OF B-SPLINES
    59  C               SX(T)=SUM(COEF(J)*N(I,T), I=I1-1,I1,...,J)
    60  C                                            FOR T=I1,I1+1,...,N
    61  C       WHERE N(I,T)=THE T-TH COMPONENT OF THE I-TH LINEAR B-SPLINE.
    62  C       DENOTE BY <.,.> THE INNER PRODUCT OF TWO VECTORS AND,
    63  C       THE COEFFICIENTS OF SX(.) ARE DETERMINED BY SOLVING THE
    64  C       NORMAL EQUATIONS
    65  C               D(I)*COEF(I-1)+E(I)*COEF(I)+D(I+1)*COEF(I+1)=B(I)
    66  C                                            FOR I=I1-1,I1,...,J
    67  C       WHERE
    68  C               D(I)=<N(I,.),N(I-1,.)>, I=I1-1,I1,...,J
    69  C               E(I)=<N(I,.),N(I,.)>, I=I1-1,I1,...,J
    70  C               B(I)=<N(I,.),F(.)>, I=I1-1,I1,...,J.
    71  C
    72  C       THEN PROCEED AS IN REFERENCE QUOTED.
    73  C......................................................................
    74  C       NO TEST ON THE CONDITIONS N<I1, N=I1 AND N=I1+1 IS MADE
    75  C        HERE BECAUSE THEY ARE CONSIDERED BY SUBROUTINE L2CXFT.
    76  C
    77  C       SET INITIAL VALUES.
    78  C
    79          I0=I1-1
    80  100     K=I0
    81          J=I1
    82          AKN(I0)=X(I1)
    83          AKN(I0-1)=AKN(I0)
    84          AKN(I1)=X(I1+1)
    85          AKN(I1+1)=AKN(I1)
    86          IAKN(I0)=I1
    87          IAKN(I1)=I1+1
    88  C
    89  C       SET NORMAL EQUATIONS.
    90  C
    91          E(I0)=1.
    92          E(I1)=1.
    93          D(I1)=0.
    94          B(I0)=F(I1)
    95          B(I1)=F(I1+1)
    96  C
    97  C       SET CHOLESKY FACTORIZATION AND COEFFICIENTS.
    98  C
    99          U(I0)=1.
   100          U(I1)=1.
   101          Z(I0)=B(I0)
   102          Z(I1)=B(I1)
   103          COEF(I0)=Z(I0)
   104          COEF(I1)=Z(I1)
   105  110     IF (K.EQ.N-2) GOTO 170
   106  C
   107  C       INSERT A KNOT AT X(K+2).
   108  C
   109          J=J+1
   110          AKN(J)=X(K+3)
   111          IAKN(J)=K+3
   112          AKN(J+1)=AKN(J)
   113  C
   114  C       UPDATE NORMAL EQUATIONS AND CHOLESKY FACTORIZATION.
   115  C
   116          E(J)=1.
   117          D(J)=0.
   118          B(J)=F(K+3)
   119          U(J)=1.
   120          Z(J)=B(J)
   121  C
   122  C       EXAMINE RIGHTMOST KNOT CONVEXITY.
   123  C
   124  120     IF (J.EQ.I1) THEN
   125              K=K+1
   126              GO TO 110
   127          END IF
   128  C
   129  C       CALCULATE RIGHTMOST THREE COEFFICIENTS.
   130  C
   131          COEF(J)=Z(J)/U(J)
   132          DO 130 I=J-1,J-2,-1
   133  130        COEF(I)=(Z(I)-D(I+1)*COEF(I+1))/U(I)
   134  C
   135  C       DETERMINE SIGN OF RIGHTMOST SECOND DIVIDED DIFFERENCE.
   136  C
   137  140     CAKNOT=(COEF(J)-COEF(J-1))/(AKN(J)-AKN(J-1))-
   138       1  (COEF(J-1)-COEF(J-2))/(AKN(J-1)-AKN(J-2))
   139          IF (CAKNOT.GT.0.0) THEN
   140              K=K+1
   141              GOTO 110
   142          END IF
   143  C
   144  C       DELETE KNOT AKN(J-1)
   145  C       UPDATE NORMAL EQUATIONS AND CHOLESKY FACTORIZATION.
   146  C
   147          C1=(AKN(J-1)-AKN(J-2))/(AKN(J)-AKN(J-2))
   148          C2=(AKN(J)-AKN(J-1))/(AKN(J)-AKN(J-2))
   149          E(J-2)=E(J-2)+C2*C2*E(J-1)+2*C2*D(J-1)
   150          D(J-1)=C1*D(J-1)+C2*D(J)+C1*C2*E(J-1)
   151          E(J-1)=C1*C1*E(J-1)+E(J)+2*C1*D(J)
   152          B(J-2)=B(J-2)+C2*B(J-1)
   153          B(J-1)=C1*B(J-1)+B(J)
   154  C
   155          IF (J.EQ.I0+2) THEN
   156              U(J-2)=E(J-2)
   157              Z(J-2)=B(J-2)
   158          ELSE
   159              U(J-2)=E(J-2)-D(J-2)*D(J-2)/U(J-3)
   160              Z(J-2)=B(J-2)-D(J-2)*Z(J-3)/U(J-3)
   161          END IF
   162          U(J-1)=E(J-1)-D(J-1)*D(J-1)/U(J-2)
   163          Z(J-1)=B(J-1)-D(J-1)*Z(J-2)/U(J-2)
   164          U(J)=0.
   165          Z(J)=0.
   166          E(J)=0.
   167          D(J)=0.
   168          B(J)=0.
   169          J=J-1
   170          AKN(J)=X(K+3)
   171          IAKN(J)=K+3
   172          AKN(J+1)=AKN(J)
   173          GOTO 120
   174  C
   175  C       DERIVE COEFFICIENTS BY BACK SUBSTITUTION.
   176  C
   177  170     NK=J
   178          COEF(NK)=Z(NK)/U(NK)
   179          DO 180 I=NK-1,I0,-1
   180  180        COEF(I)=(Z(I)-D(I+1)*COEF(I+1))/U(I)
   181  C
   182          RETURN
   183          END


L2ILS  Local Symbols

NAME                      CLASS       TYPE         EXPLANATION

N . . . . . . . . . . . . argument
I1. . . . . . . . . . . . argument
X . . . . . . . . . . . . argument
F . . . . . . . . . . . . argument
NK. . . . . . . . . . . . argument
U . . . . . . . . . . . . argument
Z . . . . . . . . . . . . argument
B . . . . . . . . . . . . argument
E . . . . . . . . . . . . argument
D . . . . . . . . . . . . argument
IAKN. . . . . . . . . . . argument
AKN . . . . . . . . . . . argument
COEF. . . . . . . . . . . argument

CAKNOT. . . . . . . . . . local       REAL         temporary
I . . . . . . . . . . . . local       INTEGER      temporary
J . . . . . . . . . . . . local       INTEGER      knot counter, I1JN-1
K . . . . . . . . . . . . local       INTEGER      data point counter, I0KN-2
C1. . . . . . . . . . . . local       REAL         temporary
C2. . . . . . . . . . . . local       REAL         temporary
I0. . . . . . . . . . . . local       INTEGER      I0=I1-1


L2ILS  Global Symbols

NAME                      CLASS         NUMBER of lines of code
                                        including comments
L2ILS . . . . . . . . . . SUBROUTINE    183



Subroutine CFLGRF
-----------------

 Line#  Source Line

     1  C......................................................................
     2  C     THIS SUBROUTINE CALCULATES
     3  C      1) THE COEFFICIENTS COEF(.) OF A LINEAR SPLINE SX(.) OVER
     4  C         KNOTS AKN(.), FROM THE NORMAL EQUATIONS.
     5  C      2) THE SPLINE COMPONENTS SX(.) FROM COEF(.) AND
     6  C      3) THE ASSOCIATED LAGRANGE MULTIPLIERS PAR(.).
     7  C     ALSO THIS SUBROUTINE PROVIDES ITERATIVE REFINEMENT OF
     8  C      1) THE COEFFICIENTS COEF(.) AND
     9  C      2) THE LAGRANGE MULTIPLIERS PAR(.).
    10  C
    11  C     CALLS SUBROUTINES COEFF, SXATXI AND LAGRNG.
    12  C......................................................................
    13        SUBROUTINE CFLGRF(SX,PAR,COEF,IACT,E,B,D,X,AKN,IAKN,F,DC,EC,
    14       1  UE,RES,NK,NACT,I1,N,ITREF,ITERTN)
    15  *     IMPLICIT DOUBLE PRECISION (A-H,O-Z)
    16        DIMENSION SX(I1:N),COEF(I1-1:N),E(I1-1:N),B(I1-1:N),D(I1-1:N),
    17       1  AKN(I1-2:N),IAKN(I1-1:N),X(I1:N),F(I1:N),DC(I1:N),EC(I1:N),
    18       2  IACT(I1:N),UE(I1-1:N),PAR(I1:N),RES(I1-1:N)
    19  C
    20  C.... I N P U T ....
    21  C     E,B,D,X,F,AKN,IAKN,IACT,DC,EC,I1,N,NK AND NACT AS THEY ARE
    22  C              DEFINED IN SUBROUTINE L2CXFT.
    23  C     ITERTN  INTEGER VARIABLE THAT IS USED TO CHECK THE FIRST CALL
    24  C              OF THIS SUBROUTINE BY SUBROUTINE L2CXFT.
    25  C     ITREF   INTEGER VARIABLE, IF ITREF=1 THEN ITERATIVE REFINEMENT
    26  C              IS INITIATED.
    27  C
    28  C.... O U T P U T ....
    29  C     COEF(I1-1:NK) REAL ARRAY CONTAINING THE SPLINE COEFFICIENTS
    30  C             AT AKN(I), I=I1-1,I1,...,NK.
    31  C     SX(I1:N) REAL ARRAY CONTAINING THE SPLINE COMPONENTS AT X(I),
    32  C             I=I1,I1+1,...,N.
    33  C     PAR(I1:N-2) REAL ARRAY CONTAINING THE LAGRANGE MULTIPLIERS SO
    34  C             THAT PAR(IACT(I)), I=I1,I1+1,...,NACT ARE THE ACTIVE
    35  C             CONSTRAINT MULTIPLIERS WHILE THE REMAINING MULTIPLIERS
    36  C             EQUAL TO ZERO.
    37  C
    38  C.... W O R K I N G  S P A C E ....
    39  C     UE(I1-1:NK+1) REAL ARRAY THAT PROVIDES WORKING SPACE FOR THE
    40  C             FACTORIZATIONS THAT GIVE COEF(.) AND PAR(.).
    41  C     RES(I1-1:N) REAL ARRAY THAT PROVIDES WORKING SPACE FOR THE
    42  C             RESIDUALS OF THE NORMAL EQUATIONS AT COEF(.) AND FOR
    43  C             THE CORRECTIONS OF COEF(.). IT ALSO PROVIDES WORKING
    44  C             SPACE FOR THE RESIDUALS OF THE LAGRANGE EQUATIONS AT
    45  C             PAR(.) AND FOR THE CORRECTIONS OF PAR(.).
    46  C
    47  C.... M E T H O D ....
    48  C     FOLLOWS THE STEPS DESCRIBED IN THE HEADING COMMENT.
    49  C......................................................................
    50        I0=I1-1
    51  C
    52  C     IF ITERTN=0 THEN AVOID CALCULATION OF COEF(.), SINCE COEF(.)
    53  C      ARE SUPPLIED BY SUBROUTINE L2ILS.
    54  C
    55        IF (ITERTN.EQ.0) GO TO 50
    56  C
    57  C.... DERIVE THE SPLINE COEF(.) ....
    58  C
    59        CALL COEFF(COEF,E,B,D,UE,NK,I1,N)
    60  C
    61  C.... INITIATE ITERATIVE REFINEMENT IF ITREF=1 ....
    62  C
    63        IF (ITREF.NE.1) GO TO 50
    64  C
    65  C         REFINE COEF(.).
    66  C         SET RESIDUALS OF NORMAL EQUATIONS IN RES(.).
    67  C
    68            RES(I0)=B(I0)-(E(I0)*COEF(I0)+D(I1)*COEF(I1))
    69            IF (I1 .EQ. NK) GO TO 30
    70            DO 20 I=I1,NK-1
    71  20           RES(I)=B(I)-(D(I)*COEF(I-1)+E(I)*COEF(I)+D(I+1)*COEF(I+1))
    72  30        RES(NK)=B(NK)-(D(NK)*COEF(NK-1)+E(NK)*COEF(NK))
    73  C
    74  C         SOLVE FOR RES(.).
    75  C
    76            CALL COEFF(RES,E,RES,D,UE,NK,I1,N)
    77  C
    78  C         CORRECT COEF(.).
    79  C
    80            DO 40 I=I0,NK
    81  40           COEF(I)=COEF(I)+RES(I)
    82  C
    83  C.... GENERATE SPLINE SX(.) AT X(.) FROM COEF(.) OVER AKN(.) ....
    84  C
    85  50    CALL SXATXI(SX,X,COEF,AKN,IAKN,I1,N,NK)
    86  C
    87  C.... CALCULATE THE LAGRANGE MULTIPLIERS PAR(.) ....
    88  C
    89        IF (NACT.LE.I0) GO TO 270
    90        CALL LAGRNG(PAR,SX,F,IACT,NACT,EC,DC,UE,I1,N)
    91  C
    92  C.... INITIATE ITERATIVE REFINEMENT IF ITREF=1 ....
    93  C
    94        IF (ITREF.NE.1) GO TO 270
    95  C
    96  C         REFINE PAR(.).
    97  C         SET RESIDUALS OF LAGRANGIAN EQUATIONS IN RES(.).
    98  C
    99            IF (I1 .EQ. NACT) THEN
   100                II=IACT(I1)
   101                RES(II)=SX(II+1)-F(II+1) - EC(II)*PAR(II)
   102                GO TO 200
   103            END IF
   104  C
   105            II=IACT(I1)
   106            RES(II)=SX(II+1)-F(II+1)-(EC(II)*PAR(II)+DC(II+1)*PAR(II+1))
   107            IF (I1+1 .EQ. NACT) GO TO 190
   108            DO 180 I=I1+1,NACT-1
   109               II=IACT(I)
   110  180          RES(II)=SX(II+1)-F(II+1) -
   111       1          (DC(II)*PAR(II-1)+EC(II)*PAR(II)+DC(II+1)*PAR(II+1))
   112  190       II=IACT(NACT)
   113            RES(II)=SX(II+1)-F(II+1)-(DC(II)*PAR(II-1)+EC(II)*PAR(II))
   114  200       CONTINUE
   115  C
   116  C         SOLVE FOR RES(.) AND CORRECT PAR(.).
   117  C          THE FOLLOWING CODE DUPLICATES WITH THAT IN SUBROUTINE LAGRNG.
   118  C
   119            I=I1
   120  210       K=1
   121  220       IF (I.LT.NACT .AND. IACT(I).EQ.IACT(I+1)-1) THEN
   122                I=I+1
   123                K=K+1
   124                GO TO 220
   125            END IF
   126  C
   127  230       IF (K.EQ.1) THEN
   128                II=IACT(I)
   129                PAR(II)=PAR(II)+RES(II)
   130            ELSE
   131                UE(I-K+1)=EC(IACT(I-K+1))
   132                DO 240 L=I-K+2,I
   133                   DI=DC(IACT(L))
   134  240              UE(L)=EC(IACT(L))-DI/UE(L-1)*DI
   135  C
   136                II=IACT(I-K+1)
   137                RES(II)=RES(II)
   138                DO 250 L=I-K+2,I
   139                   II=IACT(L)
   140  250              RES(II)=RES(II)-DC(II)*RES(IACT(L-1))/UE(L-1)
   141  C
   142                RES(IACT(I))=RES(IACT(I))/UE(I)
   143                PAR(IACT(I))=PAR(IACT(I))+RES(IACT(I))
   144                DO 260 L=I-1,I-K+1,-1
   145                   RES(IACT(L))=RES(IACT(L))/UE(L)-DC(IACT(L+1))*
   146       1                     RES(IACT(L+1))/UE(L)
   147  260              PAR(IACT(L))=PAR(IACT(L))+RES(IACT(L))
   148
   149            END IF
   150            I=I+1
   151            IF (I-NACT) 210,210,270
   152  C
   153  270   RETURN
   154        END


CFLGRF  Local Symbols

NAME                      CLASS       TYPE         EXPLANATION

ITERTN. . . . . . . . . . argument
ITREF . . . . . . . . . . argument
N . . . . . . . . . . . . argument
I1. . . . . . . . . . . . argument
NACT. . . . . . . . . . . argument
NK. . . . . . . . . . . . argument
RES . . . . . . . . . . . argument
UE. . . . . . . . . . . . argument
EC. . . . . . . . . . . . argument
DC. . . . . . . . . . . . argument
F . . . . . . . . . . . . argument
IAKN. . . . . . . . . . . argument
AKN . . . . . . . . . . . argument
X . . . . . . . . . . . . argument
D . . . . . . . . . . . . argument
B . . . . . . . . . . . . argument
E . . . . . . . . . . . . argument
IACT. . . . . . . . . . . argument
COEF. . . . . . . . . . . argument
PAR . . . . . . . . . . . argument
SX. . . . . . . . . . . . argument

I . . . . . . . . . . . . local       INTEGER      I1  I  NACT
K . . . . . . . . . . . . local       INTEGER      1  K  NACT-I0
L . . . . . . . . . . . . local       INTEGER      temporary
DI. . . . . . . . . . . . local       REAL         temporary
II. . . . . . . . . . . . local       INTEGER      temporary
I0. . . . . . . . . . . . local       INTEGER      I0=I1-1

CFLGRF  Global Symbols

NAME                      CLASS         NUMBER of lines of code
                                        including comments
CFLGRF. . . . . . . . . . SUBROUTINE    154
COEFF . . . . . . . . . . external
LAGRNG. . . . . . . . . . external
SXATXI. . . . . . . . . . external



Subroutine COEFF
----------------

 Line#  Source Line

     1  C......................................................................
     2  C     THIS SUBROUTINE CALCULATES THE COEFFICIENTS COEF(.) OF
     3  C      A LEAST SQUARES LINEAR SPLINE FROM THE NORMAL EQUATIONS.
     4  C......................................................................
     5        SUBROUTINE COEFF(COEF,E,B,D,UE,NK,I1,N)
     6  *     IMPLICIT DOUBLE PRECISION (A-H,O-Z)
     7        DIMENSION COEF(I1-1:N),E(I1-1:N),B(I1-1:N),D(I1-1:N),UE(I1-1:N)
     8  C
     9  C.... I N P U T ....
    10  C     E,B,D,I1,N,NK   AS THEY ARE DEFINED IN SUBROUTINE L2CXFT.
    11  C
    12  C.... O U T P U T ....
    13  C     COEF(I1-1:NK) REAL ARRAY CONTAINING THE SPLINE COEFFICIENTS
    14  C             AT AKN(I), I=I1-1,I1,...,NK.
    15  C
    16  C.... W O R K I N G  S P A C E ....
    17  C     UE(I1-1:NK+1) REAL ARRAY THAT PROVIDES WORKING SPACE FOR THE
    18  C             FACTORIZATION THAT GIVES COEF(.). IT KEEPS THE
    19  C             THE DIAGONAL ELEMENTS OF THE FORWARD SWEEP OF
    20  C             THE FACTORIZATION.
    21  C
    22  C.... M E T H O D (CALCULATE COEFFICIENTS) ....
    23  C     EXPRESS SPLINE SX(.) AS A LINEAR COMBINATION OF B-SPLINES
    24  C             SX(I)=SUM(COEF(J)*N(J,I), J=I1-1,I1,...,NK)
    25  C                                          FOR I=I1,I1+1,...,N
    26  C     WHERE N(J,I)=THE I-TH COMPONENT OF THE J-TH LINEAR B-SPLINE.
    27  C     DENOTE BY <.,.> THE INNER PRODUCT OF TWO VECTORS AND,
    28  C     THE SPLINE COEFFICIENTS COEF(.) ARE DETERMINED BY SOLVING THE
    29  C     NORMAL EQUATIONS
    30  C             D(J)*COEF(J-1)+E(J)*COEF(J)+D(J+1)*COEF(J+1)=B(J)
    31  C                                          FOR J=I1-1,I1,...,NK
    32  C     WHERE
    33  C             D(J)=<N(J,.),N(J-1,.)>, J=I1-1,I1,...,NK
    34  C             E(J)=<N(J,.),N(J,.)>, J=I1-1,I1,...,NK
    35  C             B(J)=<N(J,.),F(.)>, J=I1-1,I1,...,NK.
    36  C......................................................................
    37        I0=I1-1
    38  C
    39  C.....DERIVE COEF(.) BY FACTORIZATION
    40  C
    41        UE(I0)=E(I0)
    42        COEF(I0)=B(I0)
    43        DO 10 I=I0+1,NK
    44           UE(I)=E(I)-D(I)/UE(I-1)*D(I)
    45  10       COEF(I)=B(I)-D(I)*COEF(I-1)/UE(I-1)
    46        COEF(NK)=COEF(NK)/UE(NK)
    47        DO 20 I=NK-1,I0,-1
    48  20       COEF(I)=(COEF(I)-D(I+1)*COEF(I+1))/UE(I)
    49  C
    50        RETURN
    51        END



COEFF  Local Symbols

NAME                      CLASS        TYPE          EXPLANATION

N . . . . . . . . . . . . argument
I1. . . . . . . . . . . . argument
NK. . . . . . . . . . . . argument
UE. . . . . . . . . . . . argument
D . . . . . . . . . . . . argument
B . . . . . . . . . . . . argument
E . . . . . . . . . . . . argument
COEF. . . . . . . . . . . argument

I . . . . . . . . . . . . local        INTEGER       temporary
I0. . . . . . . . . . . . local        INTEGER       I0=I1-1


COEFF  Global Symbols

NAME                      CLASS        NUMBER of lines of code
                                       including comments
COEFF . . . . . . . . . . SUBROUTINE   51



Subroutine SXATXI
-----------------

 Line#  Source Line

     1  C.......................................................................
     2  C     GENERATE SPLINE SX(.) AT X(.) FROM COEF(.) OVER AKN(.).
     3  C.......................................................................
     4        SUBROUTINE SXATXI(SX,X,COEF,AKN,IAKN,I1,N,NK)
     5  *     IMPLICIT DOUBLE PRECISION  (A-H,O-Z)
     6        DIMENSION SX(I1:N),X(I1:N),COEF(I1-1:N),AKN(I1-2:N),IAKN(I1-1:N)
     7  C
     8  C.... I N P U T ....
     9  C     X,COEF,AKN,IAKN,I1,N,NK  AS THEY ARE DEFINED IN SUBROUTINE L2CXFT.
    10  C
    11  C.... O U T P U T ....
    12  C     SX(I1:N) REAL ARRAY CONTAINING THE SPLINE COMPONENTS AT X(I)
    13  C               I=I1,I1+1,...,N.
    14  C
    15  C.... M E T H O D (GENERATE SPLINE COMPONENTS FROM COEFFICIENTS) ....
    16  C     SEE ALGORITHM 5.8 OF L.L. SCHUMAKER, SPLINE FUNCTIONS: BASIC
    17  C     THEORY, J. WILEY AND SONS, 1981, P.194 .
    18  C.......................................................................
    19        I0=I1-1
    20        SX(I1)=COEF(I0)
    21        SX(N)=COEF(NK)
    22        I=I1+1
    23        L=I0
    24  50    IF (I.LT.N .AND. IAKN(L).LT.I .AND. I.LE.IAKN(L+1)) THEN
    25            DENOM=AKN(L+1)-AKN(L)
    26            A1=(X(I)-AKN(L))/DENOM
    27            A2=1-A1
    28            SX(I)=COEF(L)*A2+COEF(L+1)*A1
    29            I=I+1
    30            GO TO 50
    31        END IF
    32        L=L+1
    33        IF (L.LT.NK) GO TO 50
    34  C
    35        RETURN
    36        END


SXATXI  Local Symbols

NAME                      CLASS       TYPE          EXPLANATION

NK. . . . . . . . . . . . argument
N . . . . . . . . . . . . argument
I1. . . . . . . . . . . . argument
IAKN. . . . . . . . . . . argument
AKN . . . . . . . . . . . argument
COEF. . . . . . . . . . . argument
X . . . . . . . . . . . . argument
SX. . . . . . . . . . . . argument

I . . . . . . . . . . . . local       INTEGER       temporary, I1  I  N
L . . . . . . . . . . . . local       INTEGER       temporary, I0  L  NK
A1. . . . . . . . . . . . local       REAL          temporary
A2. . . . . . . . . . . . local       REAL          temporary
DENOM . . . . . . . . . . local       REAL          temporary
I0. . . . . . . . . . . . local       INTEGER       I0=I1-1


SXATXI  Global Symbols

NAME                      CLASS        NUMBER of lines of code
                                       including comments
SXATXI. . . . . . . . . . SUBROUTINE   36



Subroutine LAGRNG
-----------------

 Line#  Source Line

     1  C.......................................................................
     2  C     THIS SUBROUTINE CALCULATES THE LAGRANGE MULTIPLIERS PAR(.)
     3  C      ASSOCIATED WITH THE SPLINE SX(.) IN SUBROUTINE L2CXFT.
     4  C.......................................................................
     5        SUBROUTINE LAGRNG(PAR,SX,F,IACT,NACT,EC,DC,UE,I1,N)
     6  *     IMPLICIT DOUBLE PRECISION (A-H,O-Z)
     7        DIMENSION SX(I1:N),F(I1:N),DC(I1:N),EC(I1:N),UE(I1-1:N),
     8       1  IACT(I1:N),PAR(I1:N)
     9  C
    10  C.... I N P U T ....
    11  C     SX,F,IACT,DC,EC,I1,N,NACT  AS THEY ARE DEFINED IN SUBROUTINE
    12  C             L2CXFT.
    13  C
    14  C.... O U T P U T ....
    15  C     PAR(I1:N-2) REAL ARRAY CONTAINING THE LAGRANGE MULTIPLIERS SO
    16  C             THAT PAR(IACT(I)), I=I1,I1+1,...,NACT ARE THE MULTI-
    17  C             PLIERS OF THE ACTIVE CONSTRAINTS WHILE THE REMAINING
    18  C             MULTIPLIERS EQUAL TO ZERO.
    19  C
    20  C.... W O R K I N G  S P A C E ....
    21  C     UE(I1-1:NK+1) REAL ARRAY THAT PROVIDES WORKING SPACE FOR THE
    22  C             FACTORIZATION THAT GIVES PAR(.). IT KEEPS THE
    23  C             DIAGONAL ELEMENTS OF THE FORWARD SWEEP OF THE
    24  C             FACTORIZATION.
    25  C
    26  C.... M E T H O D (CALCULATE THE LAGRANGE MULTIPLIERS) .....
    27  C     THE FIRST ORDER OPTIMALITY CONDITIONS ARE
    28  C             SUM(PAR(II)*A(II,J))=2*(SX(II+1)-F(II+1)),
    29  C                                   FOR II=IACT(I), I=I1,...,NACT
    30  C      WHERE A(II,J) DENOTES THE J-TH COMPONENT OF THE II-TH SECOND
    31  C      DIVIDED DIFFERENCE. ONLY THE A(II,J) FOR J=II,II+1,II+2 ARE
    32  C      NON-ZERO. THESE CONDITIONS CONSTITUTE AN OVERDETERMINED SYSTEM
    33  C      OF EQUATIONS. CHOOSE THE EQUATIONS THAT CORRESPOND TO THE SECOND
    34  C      NON-ZERO COMPONENT OF EACH A(II,.) AND SOLVE BY GAUSS ELIMINATION
    35  C      WITHOUT PIVOTING THE DERIVED BLOCK DIAGONAL POSITIVE DEFINITE
    36  C      SYSTEM OF EQUATIONS. PROCEED AS IT IS EXPLAINED IN THE TEXTUAL
    37  C      PART OF THIS ALGORITHM.
    38  C.......................................................................
    39        IF (NACT.LE.I1-1) GO TO 170
    40  C
    41  C     THE GRADIENT OF THE OBJECTIVE FUNCTION IS DEFINED BY, SAY,
    42  C      GRAD(I)=2*(SX(I+1)-F(I+1)), I=I1,I1+1,...,N-2. HOWEVER, INSTEAD
    43  C      OF AN ARRAY GRAD(.) THE SUBROUTINE USES DIRECTLY THE VALUES OF
    44  C      THE GRADIENT AT X(.) WHEN NECESSARY.
    45  C
    46  C     CALCULATE SIZE K OF A BLOCK OF THE LAGRANGE COEFFICIENT
    47  C      MATRIX.
    48  C
    49        I=I1
    50  110   K=1
    51  120   IF (I.LT.NACT .AND. IACT(I).EQ.IACT(I+1)-1) THEN
    52            I=I+1
    53            K=K+1
    54            GO TO 120
    55        END IF
    56  C
    57  130   IF (K.EQ.1) THEN
    58            II=IACT(I)
    59            PAR(II)=(SX(II+1)-F(II+1))/EC(II)
    60        ELSE
    61  C
    62  C         FACTORIZE THE K*K 3/DIAG SYSTEM OF LAGRANGE COEF.
    63  C
    64            UE(I-K+1)=EC(IACT(I-K+1))
    65            DO 140 L=I-K+2,I
    66               DI=DC(IACT(L))
    67  140          UE(L)=EC(IACT(L))-DI/UE(L-1)*DI
    68  C
    69  C         USE THIS FACTORIZATION TO SOLVE FOR PAR(.).
    70  C
    71            GRAD=SX(IACT(I-K+1)+1)-F(IACT(I-K+1)+1)
    72            PAR(IACT(I-K+1))=GRAD
    73            DO 150 L=I-K+2,I
    74               GRAD=SX(IACT(L)+1)-F(IACT(L)+1)
    75  150          PAR(IACT(L))=GRAD-DC(IACT(L))*PAR(IACT(L-1))/UE(L-1)
    76            PAR(IACT(I))=PAR(IACT(I))/UE(I)
    77            DO 160 L=I-1,I-K+1,-1
    78  160          PAR(IACT(L))=PAR(IACT(L))/UE(L)-DC(IACT(L+1))*
    79       1                                     PAR(IACT(L+1))/UE(L)
    80        END IF
    81        I=I+1
    82        IF (I-NACT) 110,110,170
    83  C
    84  170   RETURN
    85        END

LAGRNG  Local Symbols

NAME                      CLASS      TYPE          EXPLANATIONS

N . . . . . . . . . . . . argument
I1. . . . . . . . . . . . argument
UE. . . . . . . . . . . . argument
DC. . . . . . . . . . . . argument
EC. . . . . . . . . . . . argument
NACT. . . . . . . . . . . argument
IACT. . . . . . . . . . . argument
F . . . . . . . . . . . . argument
SX. . . . . . . . . . . . argument
PAR . . . . . . . . . . . argument

I . . . . . . . . . . . . local      INTEGER       temporary, I1  I  N
K . . . . . . . . . . . . local      INTEGER       matrix size, 1  K  NACT-I0
L . . . . . . . . . . . . local      INTEGER       temporary
DI. . . . . . . . . . . . local      REAL          temporary
II. . . . . . . . . . . . local      INTEGER       temporary
GRAD. . . . . . . . . . . local      REAL          GRADient evaluation

LAGRNG  Global Symbols
NAME                      CLASS         NUMBER of lines of code
                                        including comments
LAGRNG. . . . . . . . . . SUBROUTINE    85



Subroutine ADDKNT
-----------------

 Line#  Source Line

     1  C......................................................................
     2  C     THIS SUBROUTINE INSERTS A KNOT, NAMELY THE DATA POINT X(INKNOT),
     3  C      INTO THE SPLINE KNOT SEQUENCE OF THE THE LINEAR SPLINE
     4  C      APPROXIMATION SX(.) DEFINED IN SUBROUTINE L2CXFT.
     5  C
     6  C     CALLS SUBROUTINE PLUS.
     7  C......................................................................
     8        SUBROUTINE ADDKNT(INKNOT,E,B,D,X,F,AKN,IAKN,IACT,NK,NACT,I1,N)
     9  *     IMPLICIT DOUBLE PRECISION (A-H,O-Z)
    10        DIMENSION E(I1-1:N),B(I1-1:N),D(I1-1:N),X(I1:N),F(I1:N),
    11       1  AKN(I1-2:N),IAKN(I1-1:N),IACT(I1:N)
    12  C
    13  C.... I N P U T ....
    14  C     INKNOT  INTEGER VARIABLE, SUCH THAT X(INKNOT) IS INSERTED
    15  C             INTO THE KNOT SEQUENCE AKN(.).
    16  C     E,B,D,X,F,AKN,IAKN,IACT,I1,N,NK,NACT  AS THEY ARE
    17  C             DEFINED IN SUBROUTINE L2CXFT.
    18  C
    19  C.... O U T P U T ....
    20  C     E,B,D,AKN,IAKN,IACT  AFTER INSERTING X(INKNOT) INTO AKN(.).
    21  C     NK      INCREASED BY ONE.
    22  C     NACT    DECREASED BY ONE.
    23  C
    24  C.... M E T H O D ....
    25  C     FIND POSITION J IN THE KNOT SEQUENCE AKN(.) SUCH THAT
    26  C      AKN(J-1) < X(INKNOT) < AKN(J) BEFORE INSERTION AND
    27  C      AKN(J)=X(INKNOT) AFTER INSERTION.
    28  C     CALL SUBROUTINE PLUS TO MODIFY THE NORMAL EQUATIONS THAT ARE
    29  C      AFFECTED BY THE KNOT INSERTION. HENCE THE 'HAT' BASIS FUNCTIONS
    30  C      AFFECTED BY THE INSERTION HAVE TO BE DETERMINED. THE J-TH BASIS
    31  C      FUNCTION IS DEFINED FROM X(IP) TO X(IR), AND IS CENTERED AT
    32  C      X(IQ). ALSO THE (J-1)-TH BASIS FUNCTIONS IS CENTERED AT X(IP) AND
    33  C      IS DEFINED FROM X(IPL) TO X(IQ). THE (J+1)-TH BASIS FUNCTION
    34  C      IS CENTERED AT X(IR) AND IS DEFINED FROM X(IQ) TO X(IRR).
    35  C     REVISE IACT(.), THE INDICES OF THE ACTIVE CONSTRAINTS.
    36  C......................................................................
    37        I0=I1-1
    38  C
    39  C     GIVEN X(INKNOT), APPLY BISECTION IN [I0,NK) IN ORDER TO FIND IP
    40  C      SUCH THAT  AKN(IP) < X(INKNOT) < AKN(IP+1).
    41  C
    42        IP=I0
    43        IR=NK
    44  20    IF (IR-IP.EQ.1) GO TO 30
    45        IQ=(IP+IR)/2
    46        IF (INKNOT .LT. IAKN(IQ)) THEN
    47            IR=IQ
    48        ELSE
    49            IP=IQ
    50        END IF
    51        GO TO 20
    52  30    CONTINUE
    53  C
    54        DO 100 I=NK,IP+1,-1
    55           B(I+1)=B(I)
    56           E(I+1)=E(I)
    57           D(I+1)=D(I)
    58           AKN(I+1)=AKN(I)
    59  100      IAKN(I+1)=IAKN(I)
    60        J=IP+1
    61        E(J)=0.
    62        B(J)=0.
    63        D(J)=0.
    64        NK=NK+1
    65        AKN(J)=X(INKNOT)
    66        IAKN(J)=INKNOT
    67  C
    68  C     DEFINE SUPPORTS OF NEW BASIS FUNCTIONS THAT FOLLOW THE KNOT
    69  C      INSERTION.
    70  C
    71        IF (J.EQ.I1) THEN
    72            IPL=I1
    73        ELSE
    74            IPL=IAKN(J-2)
    75        END IF
    76  C
    77        IF (J.EQ.NK-1) THEN
    78            IRR=N
    79        ELSE
    80            IRR=IAKN(J+2)
    81        END IF
    82  C
    83        IP=IAKN(J-1)
    84        IQ=IAKN(J)
    85        IR=IAKN(J+1)
    86  C
    87  C     MODIFY NORMAL EQUATIONS.
    88  C
    89        CALL PLUS(X,F,AKN,E,B,D,NK,I1,N,IPL,IP,IQ,IR,IRR,J)
    90  C
    91  C     REVISE ACTIVE CONSTRAINTS.
    92  C      NACT>=I1 BECAUSE THE KNOT INSERTION SHOWS THAT THERE EXISTS
    93  C      AT LEAST ONE ACTIVE CONSTRAINT.
    94  C
    95        IF (NACT.EQ.I1) GO TO 140
    96  C
    97  C     I1<INKNOT<N, K=INKNOT-1=ACTIVE CONSTRAINT TO BE DELETED.
    98  C     GIVEN K, APPLY BISECTION IN [I1,NACT] IN ORDER TO FIND
    99  C      IQ SUCH THAT IACT(IQ).EQ.K .
   100  C
   101        K=INKNOT-1
   102        IQ=I1
   103        IF (K.EQ.IACT(I1)) GO TO 120
   104        IF (K.EQ.IACT(NACT)) GO TO 140
   105        IP=I1
   106        IR=NACT
   107  110   IQ=(IP+IR)/2
   108        IF (IACT(IQ).EQ.K) GO TO 120
   109        IF (IACT(IQ).LT.K) THEN
   110            IP=IQ
   111        ELSE
   112            IR=IQ
   113        END IF
   114        GO TO 110
   115  120   CONTINUE
   116        DO 130 I=IQ,NACT-1
   117  130      IACT(I)=IACT(I+1)
   118  140   IACT(NACT)=0
   119        NACT=NACT-1
   120  C
   121  200   RETURN
   122        END


ADDKNT  Local Symbols

NAME                      CLASS       TYPE         EXPLANATION

N . . . . . . . . . . . . argument
I1. . . . . . . . . . . . argument
NACT. . . . . . . . . . . argument
NK. . . . . . . . . . . . argument
IACT. . . . . . . . . . . argument
IAKN. . . . . . . . . . . argument
AKN . . . . . . . . . . . argument
F . . . . . . . . . . . . argument
X . . . . . . . . . . . . argument
D . . . . . . . . . . . . argument
B . . . . . . . . . . . . argument
E . . . . . . . . . . . . argument
INKNOT. . . . . . . . . . argument

I . . . . . . . . . . . . local       INTEGER      temporary
J . . . . . . . . . . . . local       INTEGER      index of inserted knot
K . . . . . . . . . . . . local       INTEGER      temporary
IP. . . . . . . . . . . . local       INTEGER      defined in the comments
IQ. . . . . . . . . . . . local       INTEGER              - " -
IR. . . . . . . . . . . . local       INTEGER              - " -
IPL . . . . . . . . . . . local       INTEGER              - " -
IRR . . . . . . . . . . . local       INTEGER              - " -
I0. . . . . . . . . . . . local       INTEGER      I0=I1-1


ADDKNT  Global Symbols

NAME                      CLASS        NUMBER of lines of code
                                       including comments
ADDKNT. . . . . . . . . . SUBROUTINE   122
PLUS. . . . . . . . . . . external



Subroutine PLUS
---------------

 Line#  Source Line

     1  C.......................................................................
     2  C     THIS SUBROUTINE REVISES THE (J-1), THE J AND THE (J+1) NORMAL
     3  C      EQUATIONS OF SPLINE SX(.), AFTER X(IQ) IS INSERTED IN THE KNOT
     4  C      SEQUENCE AND AKN(J) IS REDEFINED AS AKN(J)=X(IQ).
     5  C.......................................................................
     6        SUBROUTINE PLUS(X,F,AKN,E,B,D,NK,I1,N,IPL,IP,IQ,IR,IRR,J)
     7  *     IMPLICIT DOUBLE PRECISION (A-H,O-Z)
     8        DIMENSION X(I1:N),F(I1:N),AKN(I1-2:N),E(I1-1:N),B(I1-1:N),
     9       1  D(I1-1:N),SV(24)
    10  C
    11  C.... I N P U T ....
    12  C     E,B,D,AKN,X,F,I1,N,NK  AS THEY ARE DEFINED IN SUBROUTINE L2CXFT.
    13  C     J      INTEGER VARIABLE, AS DEFINED IN SUBROUTINE ADDKNT, INDEX
    14  C            OF NEW INSERTED KNOT.
    15  C     IP     INTEGER VARIABLE, DATA INDEX OF THE KNOT ADJACENT TO
    16  C             THE KNOT AKN(J) AT THE LEFT, IP=IAKN(J-1).
    17  C     IPL    IF J=I1 THEN IPL=I1 ELSE IPL=IAKN(J-1).
    18  C     IQ     INTEGER VARIABLE, DATA INDEX OF INSERTED KNOT, IQ=IAKN(J).
    19  C     IR     INTEGER VARIABLE, DATA INDEX OF THE KNOT ADJACENT TO
    20  C             THE KNOT AKN(J) AT THE RIGHT, IR=IAKN(J+1).
    21  C     IRR    IF J=NK-1 THEN IRR=N ELSE IRR=IAKN(J+1).
    22  C
    23  C.... W O R K I N G  S P A C E ...
    24  C     SV(1:24) REAL ARRAY WHOSE ELEMENTS PROVIDE TEMPORARY STORAGE
    25  C            FOR THE CALCULATIONS OF (E(K),B(K), K=J-1,J,J+1) AND
    26  C            (D(K), K=J,J+1).
    27  C
    28  C.... M E T H O D ....
    29  C     GIVEN THE DATA POINTS X(IPL), X(IP), X(IQ), X(IR) AND X(IRR)
    30  C      AS THE METHOD IN SUBROUTINE ADDKNT DESCRIBES, THEN CALCULATE
    31  C      AB INITIO THE ELEMENTS OF E(K) AND B(K) FOR K=J-1,J,J+1
    32  C      AND D(K) FOR K=J,J+1 (SEE C. DE BOOR, A PRACTICAL GUIDE
    33  C      TO SPLINES, SPRINGER-VERLAG, 1978).
    34  C.......................................................................
    35  C     CALCULATE THE SCALAR PRODUCTS WHICH DEFINE E(.), B(.) AND D(.).
    36  C      SEE COMMENTS IN THE BEGINNING OF SUBROUTINE L2CXFT.
    37  C
    38        DO 50 I=1,24
    39  50       SV(I)=0.
    40  C
    41        DO 100 I=IP,IQ-1
    42           SV(1)=X(I)-AKN(J-1)
    43           SV(2)=AKN(J)-X(I)
    44           SV(3)=SV(3)+SV(2)*SV(2)
    45           SV(4)=SV(4)+SV(1)*SV(1)
    46           SV(5)=SV(5)+SV(2)*SV(1)
    47           SV(6)=SV(6)+SV(2)*F(I)
    48  100      SV(7)=SV(7)+SV(1)*F(I)
    49  C
    50        DO 200 I=IQ,IR-1
    51           SV(14)=AKN(J+1)-X(I)
    52           SV(2)=X(I)-AKN(J)
    53           SV(15)=SV(15)+SV(14)*SV(14)
    54           SV(16)=SV(16)+SV(2)*SV(2)
    55           SV(17)=SV(17)+SV(14)*SV(2)
    56           SV(18)=SV(18)+SV(14)*F(I)
    57  200      SV(19)=SV(19)+SV(2)*F(I)
    58  C
    59        IF (J.EQ.NK-1) THEN
    60            SV(11)=(AKN(J+1)-AKN(J))**2
    61            SV(9)=(AKN(J+1)-AKN(J))*F(N)
    62        ELSE
    63            DO 300 I=IR,IRR-1
    64               SV(24)=AKN(J+2)-X(I)
    65               SV(9)=SV(9)+SV(24)*F(I)
    66  300          SV(11)=SV(11)+SV(24)*SV(24)
    67        END IF
    68  C
    69        IF (I1.LT.J) THEN
    70            DO 400 I=IPL,IP-1
    71               SV(23)=X(I)-AKN(J-2)
    72               SV(8)=SV(8)+SV(23)*F(I)
    73  400          SV(10)=SV(10)+SV(23)*SV(23)
    74        END IF
    75  C
    76  C     CALCULATE B(J-1),B(J),B(J+1).
    77  C
    78        SV(2)=AKN(J-1)-AKN(J-2)
    79        SV(14)=AKN(J)-AKN(J-1)
    80        SV(21)=AKN(J+1)-AKN(J)
    81        SV(22)=AKN(J+2)-AKN(J+1)
    82  C
    83        IF (J.EQ.I1) THEN
    84            B(J-1)=SV(6)/SV(14)
    85        ELSE
    86            B(J-1)=SV(8)/SV(2)+SV(6)/SV(14)
    87        END IF
    88        B(J)=SV(7)/SV(14)+SV(18)/SV(21)
    89  C
    90        IF (J.EQ.NK-1) THEN
    91            B(J+1)=SV(19)/SV(21)+F(N)
    92        ELSE
    93            B(J+1)=SV(19)/SV(21)+SV(9)/SV(22)
    94        END IF
    95  C
    96  C     CALCULATE E(J-1),E(J),E(J+1),D(J-1),D(J).
    97  C
    98        SV(2)=SV(2)*SV(2)
    99        SV(14)=SV(14)*SV(14)
   100        SV(21)=SV(21)*SV(21)
   101        SV(22)=SV(22)*SV(22)
   102  C
   103        IF (J.EQ.I1) THEN
   104            E(J-1)=SV(3)/SV(14)
   105        ELSE
   106            E(J-1)=SV(10)/SV(2)+SV(3)/SV(14)
   107        END IF
   108        E(J)=SV(4)/SV(14)+SV(15)/SV(21)
   109  C
   110        IF (J.EQ.NK-1) THEN
   111            E(J+1)=SV(16)/SV(21)+1
   112        ELSE
   113            E(J+1)=SV(16)/SV(21)+SV(11)/SV(22)
   114        END IF
   115        D(J)=SV(5)/SV(14)
   116        D(J+1)=SV(17)/SV(21)
   117  C
   118        RETURN
   119        END


PLUS  Local Symbols

NAME                      CLASS       TYPE         EXPLANATION

J . . . . . . . . . . . . argument
IRR . . . . . . . . . . . argument
IR. . . . . . . . . . . . argument
IQ. . . . . . . . . . . . argument
IP. . . . . . . . . . . . argument
IPL . . . . . . . . . . . argument
N . . . . . . . . . . . . argument
I1. . . . . . . . . . . . argument
NK. . . . . . . . . . . . argument
D . . . . . . . . . . . . argument
B . . . . . . . . . . . . argument
E . . . . . . . . . . . . argument
AKN . . . . . . . . . . . argument
F . . . . . . . . . . . . argument
X . . . . . . . . . . . . argument

I . . . . . . . . . . . . local       INTEGER      temporary
SV. . . . . . . . . . . . local       REAL         see comments


PLUS  Global Symbols

NAME                      CLASS         NUMBER of lines of code
                                        including comments
PLUS. . . . . . . . . . . SUBROUTINE    119



Subroutine DELKNT
-----------------

 Line#  Source Line

     1  C.......................................................................
     2  C     THIS SUBROUTINE DELETES THE KNOT AKN(KNOUT) OF THE LINEAR
     3  C      SPLINE APPROXIMATION SX(.) DEFINED IN SUBROUTINE L2CXFT.
     4  C
     5  C     CALLS SUBROUTINE MINUS1.
     6  C.......................................................................
     7        SUBROUTINE DELKNT(E,B,D,AKN,IAKN,IACT,NK,NACT,I1,N,KNOUT)
     8  *     IMPLICIT DOUBLE PRECISION (A-H,O-Z)
     9        DIMENSION E(I1-1:N),B(I1-1:N),D(I1-1:N),AKN(I1-2:N),IAKN(I1-1:N),
    10       1  IACT(I1:N)
    11  C
    12  C.... I N P U T ....
    13  C     KNOUT  INTEGER VARIABLE, SUCH THAT AKN(KNOUT) IS THE KNOT TO
    14  C             BE DELETED FROM THE KNOT SEQUENCE AKN(.).
    15  C     E,B,D,AKN,IAKN,IACT,I1,N,NK,NACT  AS THEY ARE DEFINED IN
    16  C             SUBROUTINE L2CXFT.
    17  C
    18  C.... O U T P U T ....
    19  C     E,B,D,AKN,IAKN,IACT  AFTER DELETING THE KNOT AKN(KNOUT).
    20  C     NK      DECREASED BY ONE.
    21  C     NACT    INCREASED BY ONE.
    22  C
    23  C.... M E T H O D ....
    24  C     SINCE AKN(J) IS DELETED THE J-TH NORMAL EQUATION IS DELETED TOO.
    25  C      THEN CALL SUBROUTINE MINUS1 TO MODIFY THE (J-1) AND (J+1) NORMAL
    26  C      EQUATIONS. SHIFT E,B,D,AKN AND IAKN.
    27  C     REVISE IACT(.), THE INDICES OF THE ACTIVE CONSTRAINTS.
    28  C.......................................................................
    29        I0=I1-1
    30        J=IAKN(KNOUT)-1
    31  C
    32  C     MODIFY NORMAL EQUATIONS.
    33  C
    34        CALL MINUS1(E,B,D,AKN,I1,N,KNOUT)
    35  C
    36  C     SHIFT ARRAYS.
    37  C
    38        DO 5 I=KNOUT,NK-1
    39           AKN(I)=AKN(I+1)
    40           IAKN(I)=IAKN(I+1)
    41           E(I)=E(I+1)
    42           B(I)=B(I+1)
    43  5        D(I)=D(I+1)
    44  C
    45  C     SET LAST POSITION TO ZERO.
    46  C
    47        AKN(NK)=0.
    48        IAKN(NK)=0
    49        E(NK)=0.
    50        B(NK)=0.
    51        D(NK)=0.
    52        NK=NK-1
    53  C
    54  C     UPDATE IACT(.).
    55  C
    56  C     GIVEN J=IAKN(KNOUT)-1, APPLY BISECTION IN [I1,NACT] IN ORDER
    57  C      TO FIND IR SUCH THAT  IACT(IR-1) < J < IACT(IR) , OR
    58  C      IQ IS OUTSIDE [I1,NACT].
    59  C
    60        IF (NACT.EQ.I0) THEN
    61            IR=I1
    62            GO TO 130
    63        END IF
    64        IF (J.LT.IACT(I1)) THEN
    65            IR=I1
    66            GO TO 110
    67        END IF
    68        IF (J.GT.IACT(NACT)) THEN
    69            IR=NACT+1
    70            GO TO 130
    71        END IF
    72  C
    73  C     APPLY BISECTION.
    74  C
    75        IP=I1
    76        IR=NACT
    77  100   IQ=(IP+IR)/2
    78        IF (IR-IP.EQ.1) GO TO 110
    79        IF (J.LT.IACT(IQ)) THEN
    80            IR=IQ
    81        ELSE
    82            IP=IQ
    83        END IF
    84        GO TO 100
    85  110   CONTINUE
    86        DO 120 I=NACT,IR,-1
    87  120      IACT(I+1)=IACT(I)
    88  130   IACT(IR)=J
    89        NACT=NACT+1
    90  C
    91        RETURN
    92        END



DELKNT  Local Symbols

NAME                      CLASS       TYPE          EXPLANATION

KNOUT . . . . . . . . . . argument
N . . . . . . . . . . . . argument
I1. . . . . . . . . . . . argument
NACT. . . . . . . . . . . argument
NK. . . . . . . . . . . . argument
IACT. . . . . . . . . . . argument
IAKN. . . . . . . . . . . argument
AKN . . . . . . . . . . . argument
D . . . . . . . . . . . . argument
B . . . . . . . . . . . . argument
E . . . . . . . . . . . . argument

I . . . . . . . . . . . . local       INTEGER       temporary
J . . . . . . . . . . . . local       INTEGER       temporary
IP. . . . . . . . . . . . local       INTEGER       temporary
IQ. . . . . . . . . . . . local       INTEGER       temporary
IR. . . . . . . . . . . . local       INTEGER       temporary
I0. . . . . . . . . . . . local       INTEGER       I0=I1-1


DELKNT  Global Symbols

NAME                      CLASS         NUMBER of lines of code
                                        including comments
DELKNT. . . . . . . . . . SUBROUTINE    92
MINUS1. . . . . . . . . . external



Subroutine MINUS1
-----------------

 Line#  Source Line

     1  C......................................................................
     2  C     THIS SUBROUTINE REVISES THE (J-1) AND (J+1) NORMAL EQUATIONS
     3  C      OF SX(.) AFTER DELETING THE KNOT AKN(J).
     4  C     THE MODIFIED ELEMENTS REMAIN STORED IN THE SAME POSITIONS.
     5  C......................................................................
     6        SUBROUTINE MINUS1(E,B,D,AKN,I1,N,J)
     7  *     IMPLICIT DOUBLE PRECISION (A-H,O-Z)
     8        DIMENSION E(I1-1:N),B(I1-1:N),D(I1-1:N),AKN(I1-2:N)
     9  C
    10  C.... I N P U T ....
    11  C     J       INTEGER VARIABLE, SUCH THAT AKN(J) IS THE DELETED KNOT.
    12  C     E,B,D,AKN,I1,N  AS THEY ARE DEFINED IN SUBROUTINE L2CXFT.
    13  C
    14  C.... O U T P U T ....
    15  C     E(J-1),E(J+1),B(J-1),B(J),D(J+1) THE ONLY ELEMENTS OF THE
    16  C             NORMAL EQUATIONS THAT NEED BE MODIFIED BECAUSE OF J-TH
    17  C             KNOT DELETION.
    18  C
    19  C.... M E T H O D ....
    20  C     REF: FORMULAE (2.9) AND (2.10) IN "THE MINIMUM SUM OF
    21  C          SQUARES CHANGE TO UNIVARIATE DATA THAT GIVES CONVEXITY",
    22  C          BY I.C.DEMETRIOU AND M.J.D.POWELL, TO APPEAR IN IMA J. OF
    23  C          NUMERICAL ANALYSIS, 1991.
    24  C......................................................................
    25        C1=(AKN(J)-AKN(J-1))/(AKN(J+1)-AKN(J-1))
    26        C2=(AKN(J+1)-AKN(J))/(AKN(J+1)-AKN(J-1))
    27        E(J-1)=E(J-1)+C2*C2*E(J)+2*C2*D(J)
    28        E(J+1)=C1*C1*E(J)+E(J+1)+2*C1*D(J+1)
    29        D(J+1)=C1*D(J)+C2*D(J+1)+C1*C2*E(J)
    30        B(J-1)=B(J-1)+C2*B(J)
    31        B(J+1)=C1*B(J)+B(J+1)
    32  C
    33        RETURN
    34        END

MINUS1  Local Symbols

NAME                      CLASS       TYPE      EXPLANATION

J . . . . . . . . . . . . argument
N . . . . . . . . . . . . argument
I1. . . . . . . . . . . . argument
AKN . . . . . . . . . . . argument
D . . . . . . . . . . . . argument
B . . . . . . . . . . . . argument
E . . . . . . . . . . . . argument
C1. . . . . . . . . . . . local       REAL      temporary
C2. . . . . . . . . . . . local       REAL      temporary

MINUS1  Global Symbols

NAME                      CLASS         NUMBER of lines of code
                                        including comments
MINUS1. . . . . . . . . . SUBROUTINE    34



Subroutine MESSGE
-----------------

 Line#  Source Line

     1  C.......................................................................
     2  C     MESSAGES ASSOCIATED WITH THE OPERATIONS OF SUBROUTINE L2CXFT.
     3  C.......................................................................
     4        SUBROUTINE MESSGE(TEMP,ITEMP1,ITEMP2,ITER,LABEL)
     5  *     IMPLICIT DOUBLE PRECISION (A-H,O-Z)
     6        DIMENSION ITER(*)
     7  C
     8  C.... I N P U T ....
     9  C     TEMP,ITEMP1,ITEMP2   VARIABLES THAT ALLOW VALUES TO PASS FROM
    10  C                 SUBROUTINE L2CXFT.
    11  C     ITER(*)    INTEGER ARRAY, HOLDING NUMBER OF ITERATIONS. IT IS
    12  C                 DEFINED IN SUBROUTINE L2CXFT.
    13  C     LABEL      INTEGER VARIABLE, INDICATING THE NEAREST LABEL IN
    14  C                 SUBROUTINE L2CXFT, WHERE THE MESSAGE IS CAUSED.
    15  C
    16  C.... O U T P U T ....
    17  C     VARIOUS MESSAGES THAT ARE ACTIVATED ONLY IF THE ARGUMENT IPRINT
    18  C      OF SUBROUTINE L2CXFT HAS THE VALUE 1.
    19  C......................................................................
    20  C
    21        IF (LABEL.EQ.10) THEN
    22            PRINT 1010
    23  1010      FORMAT(//5X,'ERROR RETURN FROM L2CXFT BECAUSE THE ',
    24       1            /5X,'DATA LOWER BOUND EXCEEDS THE UPPER BOUND.')
    25            GO TO 2000
    26        END IF
    27  C
    28        IF (LABEL.EQ.20) THEN
    29            PRINT 1020
    30  1020      FORMAT(//5X,'THE DATA ITSELF IS THE REQUIRED APPROXIMATION.')
    31            GO TO 2000
    32        END IF
    33  C
    34        IF (LABEL.EQ.160) THEN
    35            PRINT 1160,ITER(1),ITEMP1,TEMP,ITEMP2
    36  1160      FORMAT (//5X,'ITERATIONS = ',I5,
    37       1            /5X,'NUMBER OF VIOLATED CONSTRAINTS    =',I5,
    38       2            /5X,'MAXIMUM CONSTRAINT  VIOLATION     =',E20.10,
    39       3            /5X,'                AT DATA POINT     =',I5)
    40            GO TO 2000
    41        END IF
    42  C
    43        IF (LABEL.EQ.170) THEN
    44            PRINT 1170
    45  1170      FORMAT (//5X,'L2CXFT RETURNS BECAUSE THE ACCURACY IS'
    46       1      ' INSUFFICIENT',/5X,'TO MAINTAIN INCREASING THE '
    47       2      'FUNCTION VALUES.')
    48            GO TO 2000
    49        END IF
    50  C
    51        IF (LABEL.EQ.180) THEN
    52            PRINT 1180
    53  1180      FORMAT (/5X,'ITERATIVE REFINEMENT IS INITIATED.')
    54            GO TO 2000
    55        END IF
    56  C
    57        IF (LABEL.EQ.210) THEN
    58            PRINT 1210,ITER(1)
    59  1210      FORMAT (//5X,'L2CXFT QUITS ON ITERATION COUNT = ',I5)
    60            GO TO 2000
    61        END IF
    62  C
    63        IF (LABEL.EQ.220) THEN
    64            PRINT 1220,TEMP
    65  1220      FORMAT (/5X,'MULTIPLIER OF INSERTED CONSTRAINT =',E20.10)
    66            GO TO 2000
    67        END IF
    68  C
    69        IF (LABEL.EQ.350) THEN
    70            PRINT 1350,ITEMP1,TEMP
    71  1350      FORMAT (/5X,'ITERATION IN THE DUAL SPACE DUE TO ROUND OFF',
    72       1      /5X,'CONSTRAINT INDEX    = ',I5,
    73       2      /5X,'LAGRANGE MULTIPLIER = ',E20.10)
    74            GO TO 2000
    75        END IF
    76  C
    77        IF (LABEL.EQ.1000) THEN
    78            PRINT 1500,ITEMP2,ITER(2),ITER(4),ITEMP1,ITER(6),ITER(5)
    79  1500      FORMAT (//5X,'---------------------------------------',
    80       1             /5X,'RETURN FROM L2CXFT WITH MODE = ',I5,
    81       2            //5X,'INITIAL ACTIVE SET  = ',I5,
    82       3             /5X,'STARTING ACTIVE SET = ',I5,
    83       4             /5X,'FINAL ACTIVE SET    = ',I5,
    84       5            //5X,'ADDITIONS OF CONSTRAINTS = ',I5,
    85       6             /5X,'DELETIONS OF CONSTRAINTS = ',I5,
    86       7             /5X,'---------------------------------------')
    87            GO TO 2000
    88        END IF
    89  C
    90  2000  RETURN
    91        END


MESSGE  Local Symbols

NAME                      CLASS       TYPE

LABEL . . . . . . . . . . argument
ITER. . . . . . . . . . . argument
ITEMP2. . . . . . . . . . argument
ITEMP1. . . . . . . . . . argument
TEMP  . . . . . . . . . . argument


MESSGE  Global Symbols

NAME                      CLASS         NUMBER of lines of code
                                        including comments
MESSGE. . . . . . . . . . SUBROUTINE    91




\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
APPENDIX B

DRIVER PROGRAMS FOR L2CXFT AND AN EXAMPLE WITH OUTPUT
=====================================================

Appendix B presents two driver programs, PROG1 and  PROG2,  a  random  number
generator, RND, and an example with output in order to demonstrate the use of
subroutine L2CXFT. Their source listings are stated after  demonstrating  the
use of PROG1 and PROG2. One  more  driver  program,  PROGMULT,  is  given  in
machine readable form that combines, in a way, PROG1 and PROG2  in  order  to
provide a multiple testing of subroutine L2CXFT on a  variety  of  data  sets
(see Appendix C for more details). The drivers have been tested with as  many
as 2000 data points on a variety of data sets and some results are  presented
by Demetriou and Powell [2] in double precision arithmetics. We also use  the
double precision version in the following presentation.

PROG1 demonstrates the use of L2CXFT when the data  is  read  from,  and  the
results are directed to, files. The driver reads  unformattedly  values   for
I1 and N. Then N-I1+1 data pairs are read according to
      DO xxx I=I1,N
         READ (2,*) X(I),F(I)
xxx   CONTINUE
Then  the  best  least  squares  piecewise  monotonic approximation to F(.) is
computed and I1, N, X(.) and SX(.) are directed to files according to
      WRITE (3,xx) I1,N
xx    FORMAT (2I5)
      DO xxx I=I1,N
         WRITE (3,yy) X(I),SX(I)
xxx   CONTINUE
yy    FORMAT (2E20.10)

At the end of the calculation the following information is printed: MODE, the
number of constraints of the initial active  set,  starting  active  set  and
final active set, as well as the number of constraint additions and deletions
during the quadratic programming  calculation.  Further,  PROG1  employs  the
parameter IFILE. If IFILE=1 then some screen output shows the  arrays  X,  F,
SX, PAR(.) and the B-spline coefficients.

PROG2 generates 'pseudorandomly' data and directs this data to a  file.  Then
this file can be used as data for the driver PROG1. For our testing needs the
data is generated by adding uniformly distributed  random  numbers  from  the
interval (-SIZE,SIZE) to given function measurements  {f(X(i)):  i=I1,...,N}.
The FUNCTION RND(SIZE) that generates the random numbers is also included  in
the source listings of this appendix. The user need only provide  PROG2  with
values for SIZE, I1 and N, as well as  an  analytic  form  for  f(x).  As  an
example, data is produced by PROG2 which  is  then  used  by  PROG1.  A  full
description of this process follows.

The function that provided measurements for our example  is  f(x)=1/(1+10x ),
x[0,1]. We let the parameter settings I1=1, N=75 and SIZE=50/N**2 and, PROG2
added uniformly distributed random errors  from  [-SIZE,SIZE]  to  a  set  of
equally spaced values of f(x) on [0,1]. Then I1, N and the  arrays  X(.)  and
F(.), in pairs, were directed to the file XFDTA

    1   75
     .0000000000E+00        .9911113824E+00
     .1351351351E-01        .9998738459E+00
     .2702702703E-01        .1000430642E+01
          ...                   ...
      See the DATA POINTS   See the MEASUREMENTS
      column in table of    column in table of
      output below.         output below.
          ...                   ...
     .9729729730E+00        .1009989017E+00
     .9864864865E+00        .9102340505E-01
     .1000000000E+01        .8969148878E-01

and the following message typed,

     DATA HAS BEEN GENERATED AND KEPT IN FILE "XFDTA".
Stop - Program terminated.

Then PROG1 (with parameters IFILE=1 and IPRINT=0) was applied  on  this  data
and, subroutine L2CXFT performed the  smoothing  calculation  and  terminated
with the messages

     X-F DATA SUPPLY FOR SMOOTHING FROM DATAFILE "XFDTA".

and
       -----------------------------------
       RETURN FROM L2CXFT WITH MODE =    1

       INITIAL ACTIVE SET  =   66
       STARTING ACTIVE SET =   63
       FINAL ACTIVE SET    =   66

       ADDITIONS OF CONSTRAINTS =   4
       DELETIONS OF CONSTRAINTS =   1
       -----------------------------------

Next, PROG1 directed I1, N and the arrays X(.) and SX(.) of the  best  convex
approximation to the file CXAPPX,

    1   75
     .0000000000E+00       .1057801533E+01
     .1351351351E-01       .1034305484E+01
     .2702702703E-01       .1010809436E+01
          ...                   ...
     See the DATA POINTS   See the APPROXIMATION
     column in table of    column in table of
     output below.         output below.
          ...                   ...
     .9729729730E+00       .9568015062E-01
     .9864864865E+00       .9398053942E-01
     .1000000000E+01       .9228092821E-01

followed by the message

     THE BEST CONVEX APPROXIMATION TO THE DATA IS NOW KEPT IN FILE "CXAPPX".

Also I1, NK and the arrays IAKN(.) and COEF(.), in pairs,  were  directed  to
the file SPLNCF

    1    8
    1     .1057801533E+01
   27     .4469042731E+00
   32     .3623895708E+00
   35     .3162726998E+00
   43     .2321288414E+00
   52     .1702519103E+00
   55     .1570835459E+00
   70     .1007789843E+00
   75     .9228092821E-01

followed by the message

     SPLINE KNOTS AND COEFFICIENTS OF THE BEST CONVEX
        APPROXIMATION TO THE DATA ARE NOW KEPT IN FILE ........... "SPLNCF".

Further, since we had given the value 1 to the parameter IFILE in PROG1,  the
following tables of results were printed

            KNOT      DATA INDEX      B-SPLINE COEF
            (AKN)      (IAKN)          (COEF)

    0     .00000000    1               .1057801533E+01
    1     .35135135   27               .4469042731E+00
    2     .41891892   32               .3623895708E+00
    3     .45945946   35               .3162726998E+00
    4     .56756757   43               .2321288414E+00
    5     .68918919   52               .1702519103E+00
    6     .72972973   55               .1570835459E+00
    7     .93243243   70               .1007789843E+00
    8    1.00000000   75               .9228092821E-01


       DATA POINTS      MEASUREMENTS        APPROXIMATION       LAGRANGE MULT
       (X)              (F)                 (SX)                (PAR)

    1     .00000000     .9911113824E+00     .1057801533E+01
    2     .01351351     .9998738459E+00     .1034305484E+01     .1802436490E-02
    3     .02702703     .1000430642E+01     .1010809436E+01     .4535457799E-02
    4     .04054054     .9804201092E+00     .9873133872E+00     .7548987043E-02
    5     .05405405     .9749307567E+00     .9638173388E+00     .1074882110E-01
    6     .06756757     .9485036911E+00     .9403212904E+00     .1364829251E-01
    7     .08108108     .9351919856E+00     .9168252419E+00     .1632661796E-01
    8     .09459459     .9266702715E+00     .8933291935E+00     .1850854492E-01
    9     .10810811     .8917348320E+00     .8698331451E+00     .1978936168E-01
   10     .12162162     .8705276552E+00     .8463370967E+00     .2047824094E-01
   11     .13513514     .8423695333E+00     .8228410483E+00     .2051332133E-01
   12     .14864865     .8172096148E+00     .7993449998E+00     .2002060483E-01
   13     .16216216     .7873528206E+00     .7758489513E+00     .1904506089E-01
   14     .17567568     .7672464307E+00     .7523529028E+00     .1775860156E-01
   15     .18918919     .7446563511E+00     .7288568544E+00     .1606961446E-01
   16     .20270270     .7087908899E+00     .7053608060E+00     .1395361394E-01
   17     .21621622     .6764816234E+00     .6818647576E+00     .1174490844E-01
   18     .22972973     .6597534730E+00     .6583687092E+00     .9681693062E-02
   19     .24324324     .6292289289E+00     .6348726608E+00     .7581051633E-02
   20     .25675676     .6033681049E+00     .6113766122E+00     .5632943482E-02
   21     .27027027     .5713176841E+00     .5878805638E+00     .3901281490E-02
   22     .28378378     .5482620069E+00     .5643845154E+00     .2617264893E-02
   23     .29729730     .5332726348E+00     .5408884670E+00     .1768991768E-02
   24     .31081081     .5174363187E+00     .5173924185E+00     .1126551945E-02
   25     .32432432     .4811492550E+00     .4938963701E+00     .4829256308E-03
   26     .33783784     .4661344530E+00     .4704003217E+00     .1838159416E-03
   27     .35135135     .4388445390E+00     .4469042731E+00     .0000000000E+00
   28     .36486486     .4308129616E+00     .4300013327E+00     .3401471183E-04
   29     .37837838     .4148342422E+00     .4130983922E+00     .4609350657E-04
   30     .39189189     .3936472277E+00     .3961954517E+00     .1125743650E-04
   31     .40540541     .3822276153E+00     .3792925113E+00     .4529228621E-04
   32     .41891892     .3603576069E+00     .3623895708E+00     .0000000000E+00
   33     .43243243     .3476972646E+00     .3470172805E+00     .9625657018E-05
   34     .44594595     .3313534700E+00     .3316449902E+00     .8733658904E-06
   35     .45945946     .3137283704E+00     .3162726998E+00     .0000000000E+00
   36     .47297297     .3084224841E+00     .3057547175E+00     .6789229450E-04
   37     .48648649     .2941926320E+00     .2952367352E+00     .6368279013E-04
   38     .50000000     .2836337689E+00     .2847187529E+00     .8769229225E-04
   39     .51351351     .2765812185E+00     .2742007706E+00     .1410256874E-03
   40     .52702703     .2637914026E+00     .2636827883E+00     .1300226541E-03
   41     .54054054     .2553451315E+00     .2531648060E+00     .1160841004E-03
   42     .55405405     .2415498315E+00     .2426468237E+00     .4321783140E-04
   43     .56756757     .2296762383E+00     .2321288414E+00     .0000000000E+00
   44     .58108108     .2198608080E+00     .2252536268E+00     .2306873814E-04
   45     .59459459     .2190642499E+00     .2183784123E+00     .1918893361E-03
   46     .60810811     .2186406030E+00     .2115031977E+00     .3421737818E-03
   47     .62162162     .2077401845E+00     .2046279832E+00     .2995553818E-03
   48     .63513514     .1925459533E+00     .1977527686E+00     .1728234320E-03
   49     .64864865     .1957873476E+00     .1908775540E+00     .1868162198E-03
   50     .66216216     .1798640641E+00     .1840023394E+00     .6811188346E-04
   51     .67567568     .1791396944E+00     .1771271249E+00     .6125282717E-04
   52     .68918919     .1669535356E+00     .1702519103E+00     .0000000000E+00
   53     .70270270     .1651361009E+00     .1658624555E+00     .2789243543E-04
   54     .71621622     .1660217703E+00     .1614730007E+00     .7541607680E-04
   55     .72972973     .1525184943E+00     .1570835459E+00     .0000000000E+00
   56     .74324324     .1506779945E+00     .1533299085E+00     .4796369670E-04
   57     .75675676     .1469861249E+00     .1495762710E+00     .1676007451E-03
   58     .77027027     .1514887930E+00     .1458226336E+00     .3572417417E-03
   59     .78378378     .1411938339E+00     .1420689961E+00     .3937432944E-03
   60     .79729730     .1381971644E+00     .1383153587E+00     .4538978805E-03
   61     .81081081     .1303065363E+00     .1345617213E+00     .5172469069E-03
   62     .82432432     .1330563368E+00     .1308080838E+00     .6956009318E-03
   63     .83783784     .1275538311E+00     .1270544464E+00     .8131913626E-03
   64     .85135135     .1286051712E+00     .1233008089E+00     .9172849096E-03
   65     .86486486     .1264505898E+00     .1195471715E+00     .8780173127E-03
   66     .87837838     .1121119828E+00     .1157935340E+00     .6521708420E-03
   67     .89189189     .1163518117E+00     .1120398966E+00     .5258257556E-03
   68     .90540541     .1077965264E+00     .1082862591E+00     .2829424227E-03
   69     .91891892     .9800759018E-01     .1045326217E+00     .5329510986E-04
   70     .93243243     .9460574443E-01     .1007789843E+00     .0000000000E+00
   71     .94594595     .9911817866E-01     .9907937305E-01     .1135492096E-03
   72     .95945946     .1017700997E+00     .9737976183E-01     .2260496198E-03
   73     .97297297     .1009989017E+00     .9568015062E-01     .2198922491E-03
   74     .98648649     .9102340505E-01     .9398053942E-01     .6998484936E-04
   75    1.00000000     .8969148878E-01     .9228092821E-01
 ------------------------------------------------
  VALUE OF OBJECTIVE FUNCTION AT THE OPTIMUM=     .1136788507E-01
Stop program terminated.


Finally, if IPRINT=1 then there is some printing in each iteration  that  may
serve as an initial test of subroutine L2CXFT for new users. For the  current
data these results coming from subroutine MESSGE are as follows:

     ITERATIONS =     0
     NUMBER OF VIOLATED CONSTRAINTS    =    3
     MAXIMUM CONSTRAINT  VIOLATION     =    -.1381250278E-02
                     AT DATA POINT     =   42

     MULTIPLIER OF INSERTED CONSTRAINT =     .5779924941E-04


     ITERATIONS =     1
     NUMBER OF VIOLATED CONSTRAINTS    =    2
     MAXIMUM CONSTRAINT  VIOLATION     =    -.6702386795E-03
                     AT DATA POINT     =   56

     MULTIPLIER OF INSERTED CONSTRAINT =     .4663869703E-04


     ITERATIONS =     2
     NUMBER OF VIOLATED CONSTRAINTS    =    1
     MAXIMUM CONSTRAINT  VIOLATION     =    -.3060547553E-03
                     AT DATA POINT     =   44

     MULTIPLIER OF INSERTED CONSTRAINT =     .2291508895E-04


     ITERATIONS =     3
     NUMBER OF VIOLATED CONSTRAINTS    =    1
     MAXIMUM CONSTRAINT  VIOLATION     =    -.3200326395E-04
                     AT DATA POINT     =   34

     MULTIPLIER OF INSERTED CONSTRAINT =     .8733658904E-06



Main program PROG1
------------------

 Line#  Source Line

     1        PROGRAM PROG1
     2  C
     3  C     SAMPLE PROGRAM THAT DEMONSTRATES SUBROUTINE L2CXFT WHEN THE
     4  C      DATA IS READ FROM, AND THE RESULTS ARE DIRECTED TO, FILES.
     5  C
     6  C     CALLS SUBROUTINE L2CXFT.
     7  C.......................................................................
     8        PARAMETER (IX1=1,
     9       1           NX=2000,
    10       2           IX0=IX1-1,
    11       3           IFILE=1,
    12       4           IPRINT=0)
    13  *     IMPLICIT DOUBLE PRECISION (A-H,O-Z)
    14        DIMENSION X(IX1:NX),F(IX1:NX),SX(IX1:NX),COEF(IX0:NX),
    15       1  AKN(IX0-1:NX),IAKN(IX0:NX),IACT(IX1:NX),ITER(10),
    16       2  PAR(IX1:NX),PAROLD(IX1:NX),RES(IX0:NX),DC(IX0:NX),EC(IX0:NX),
    17       3  E(IX0:NX),B(IX0:NX),D(IX0:NX),Z(IX0:NX),U(IX0:NX),SXOLD(IX1:NX)
    18  C
    19  C......................................................................
    20  C.... I N P U T ....
    21  C     X,F,SX,COEF,AKN,IAKN,IACT,ITER : ARRAYS THAT ARE EXPLAINED IN
    22  C               SUBROUTINE L2CXFT.
    23  C     I1,N      LOWER,UPPER INDICES OF DATA ARRAYS X(.) AND F(.). THEY
    24  C               ARE EXPLAINED IN SUBROUTINE L2CXFT.
    25  C     'XFDTA'   DATAFILE THAT HOLDS I1 AND N, AND THE DATA PAIRS
    26  C               X(I),F(I) FOR I=I1,I1+1,...,N. 'DATA' IS PROVIDED
    27  C               BY THE USER (OR BY PROG3 FOR TESTING PURPOSES).
    28  C     IFILE     INTEGER PARAMETER WHOSE DEFAULT VALUE IS 0.
    29  C               IF IFILE=1  THEN SOME PRINTOUT IS ACTIVATED AT THE
    30  C                           END OF THE SMOOTHING PROCESS.
    31  C     IPRINT    INTEGER PARAMETER WHOSE DEFAULT VALUE IS O.
    32  C               IF IPRINT=1 THEN SUBROUTINE MESSGE IS CALLED BY SUB-
    33  C                           ROUTINE L2CXFT TO PRINT INTERMEDIATE
    34  C                           RESULTS (USEFUL TO SUBRTN L2CXFT INSTALTN).
    35  C
    36  C.... O U T P U T
    37  C     RESULTS FROM THE CALL OF SUBROUTINE L2CXFT: THE LEAST SQUARES
    38  C      BEST CONVEX FIT TO THE DATA X(.)-F(.).
    39  C
    40  C     FILE 'CXAPPX' KEEPS THE BEST CONVEX FIT.
    41  C     FILE 'SPLNCF' KEEPS SPLINE KNOTS AND COEFFICIENTS OF BEST FIT.
    42  C......................................................................
    43  C
    44  C      READ (UNFORMATTEDLY) DATA FROM DATAFILE.
    45  C
    46        OPEN (2,FILE='XFDTA')
    47              REWIND 2
    48              READ (2,*) I1,N
    49              I0=I1-1
    50              DO 100 I=I1,N
    51  100            READ (2,*) X(I),F(I)
    52        CLOSE(2)
    53        PRINT 1110
    54  1110  FORMAT(/5X,'X-F DATA SUPPLY FOR SMOOTHING FROM DATAFILE "XFDTA".')
    55  C
    56  C     CALCULATE THE BEST CONVEX FIT TO DATA.
    57  C
    58        CALL L2CXFT(X,F,SX,I1,N,AKN,IAKN,COEF,NK,IACT,NACT,PAR,
    59       1  ITER,SXOLD,E,B,D,Z,U,DC,EC,PAROLD,RES,IPRINT,MODE)
    60  C
    61  C     SEND RESULTS TO FILES.
    62  C
    63        OPEN (3,FILE='CXAPPX')
    64              WRITE (3,120) I1,N
    65  120         FORMAT (2I5)
    66              DO 130 I=I1,N
    67  130            WRITE (3,140) X(I),SX(I)
    68  140            FORMAT(2E20.10)
    69        CLOSE(3)
    70        PRINT 1140
    71  1140  FORMAT(/5X,'THE BEST CONVEX APPROXIMATION TO THE DATA ',
    72       1               'IS NOW KEPT IN FILE "CXAPPX". ')
    73  C
    74        OPEN (4,FILE='SPLNCF')
    75              WRITE (4,150) I1,NK
    76  150         FORMAT (2I5)
    77              DO 160 I=I1-1,NK
    78  160            WRITE (4,170) IAKN(I),COEF(I)
    79  170            FORMAT(I5,E20.10)
    80        CLOSE(4)
    81        PRINT 1170
    82  1170  FORMAT(/5X,'SPLINE KNOTS AND COEFFICIENTS OF THE BEST CONVEX',
    83       1      /5X,'   APPROXIMATION TO THE DATA ARE NOW KEPT IN FILE ',
    84       2          '........... "SPLNCF". ')
    85  C
    86  C     PRINTOUT.
    87  C      THE USER: IF N=LARGE, MAY DIRECT THIS PRINTOUT TO A FILE.
    88  C
    89        IF (IFILE.EQ.1) THEN
    90            WRITE (*,1200) (J,AKN(J),IAKN(J),COEF(J),J=I0,NK)
    91  1200      FORMAT(////
    92       1     12X,4HKNOT,6X,10HDATA INDEX,6X,13HB-SPLINE COEF/
    93       2     12X,5H(AKN),6X,6H(IAKN),10X,6H(COEF)//
    94       3     (I5,F14.8,I5,10X,E20.10))
    95  C
    96            DO 1310 I=I1,N
    97               IF (I.EQ.I1) THEN
    98                   WRITE (*,1250) I,X(I),F(I),SX(I)
    99               ELSE IF (I.EQ.N) THEN
   100                        WRITE (*,1260) I,X(I),F(I),SX(I)
   101               ELSE
   102                   WRITE (*,1300) I,X(I),F(I),SX(I),PAR(I-1)
   103               ENDIF
   104  1250         FORMAT(/////7X,11HDATA POINTS,6X,12HMEASUREMENTS,8X,
   105       1        13HAPPROXIMATION,7X,13HLAGRANGE MULT/
   106       2        7X,3H(X),14X,3H(F),17X,4H(SX),16X,5H(PAR)//
   107       3        (I5,F14.8,E20.10,E20.10))
   108  1260          FORMAT(I5,F14.8,E20.10,E20.10)
   109  1300          FORMAT(I5,F14.8,E20.10,E20.10,E20.10)
   110  1310      CONTINUE
   111  C
   112           ANORM2=0.0
   113           DO 1350 I=I1,N
   114  1350        ANORM2=ANORM2+(SX(I)-F(I))*(SX(I)-F(I))
   115              WRITE(*,1400) ANORM2
   116  1400        FORMAT(/2X,43HVALUE OF OBJECTIVE FUNCTION AT THE OPTIMUM=,
   117       1       E20.10)
   118        END IF
   119  C
   120        STOP
   121        END

PROG1  Local Symbols (for explanations see calling subroutine)

NAME                      CLASS   TYPE

RES . . . . . . . . . . . local   REAL ARRAY
B . . . . . . . . . . . . local   REAL ARRAY
U . . . . . . . . . . . . local   REAL ARRAY
I . . . . . . . . . . . . local   INTEGER
J . . . . . . . . . . . . local   INTEGER
N . . . . . . . . . . . . local   INTEGER
NK. . . . . . . . . . . . local   INTEGER
MODE. . . . . . . . . . . local   INTEGER
NACT. . . . . . . . . . . local   INTEGER
ANORM2. . . . . . . . . . local   REAL
ITER. . . . . . . . . . . local   INTEGER ARRAY
I0. . . . . . . . . . . . local   INTEGER
I1. . . . . . . . . . . . local   INTEGER
X . . . . . . . . . . . . local   REAL ARRAY
SX. . . . . . . . . . . . local   REAL ARRAY
D . . . . . . . . . . . . local   REAL ARRAY
Z . . . . . . . . . . . . local   REAL ARRAY
E . . . . . . . . . . . . local   REAL ARRAY
AKN . . . . . . . . . . . local   REAL ARRAY
F . . . . . . . . . . . . local   REAL ARRAY
DC. . . . . . . . . . . . local   REAL ARRAY
COEF. . . . . . . . . . . local   REAL ARRAY
EC. . . . . . . . . . . . local   REAL ARRAY
IACT. . . . . . . . . . . local   INTEGER ARRAY
PAR . . . . . . . . . . . local   REAL ARRAY
SXOLD . . . . . . . . . . local   REAL ARRAY
IAKN. . . . . . . . . . . local   INTEGER ARRAY
PAROLD. . . . . . . . . . local   REAL ARRAY

PROG1  Symbolic Constant    Type        Explanation              Value

IX1 . . . . . . . . . . .   INTEGER     lower data index             1
NX. . . . . . . . . . . .   INTEGER     upper data index          2000
IX0 . . . . . . . . . . .   INTEGER     IX0=IX1-1                    0
IFILE . . . . . . . . . .   INTEGER     switch for directing
                                        results to an output file    1
IPRINT. . . . . . . . . .   INTEGER     switch for deriving
                                        printing output from
                                        subroutine L2CXFT            0

PROG1  Global Symbols

NAME                      CLASS

L2CXFT. . . . . . . . . . external
main. . . . . . . . . . . driver program for L2CXFT



Main program PROG2
------------------

 Line#  Source Line

     1        PROGRAM PROG2
     2  C
     3  C     SAMPLE PROGRAM THAT GENERATES PSEUDORANDOMLY DATA FOR
     4  C      TESTING THE SUBROUTINE L2CXFT.
     5  C
     6  C     CALLS FUNCTION RND.
     7  C.......................................................................
     8  *     IMPLICIT DOUBLE PRECISION (A-H,O-Z)
     9        PARAMETER (I1=1,
    10       1           N=75,
    11       2           XA=0.0,
    12       3           XB=1.0,
    13       4           SIZE=50.0/N**2)
    14        DIMENSION X(I1:N),F(I1:N)
    15  C
    16  C.... I N P U T  AND  P A R A M E T E R S  (SET BY THE USER) ....
    17  C     I1        LOWER DATA INDEX.
    18  C     N         UPPER DATA INDEX.
    19  C     XA        LEFT LIMIT OF X(.), X(I1)=XA.
    20  C     XB        RIGHT LIMIT OF X(.), X(N)=XB.
    21  C     SIZE      RELATIVE MAGNITUDE OF NOISE.
    22  C                RECOMMENTED VALUES FOR SIZE THAT COVER A WIDE RANGE
    23  C                OF DATA BEHAVIOUR ARE (WHEN I1=1)
    24  C                = 0
    25  C                = 4/N**2
    26  C                = 10/N**2
    27  C                = 50/N**2
    28  C                = 250/N**2
    29  C                = 1000/N**2
    30  C
    31  C.... O U T P U T  (DIRECTED TO THE FILE "XFDTA") ....
    32  C     X(I1:N)   DATA POINTS (ABSCISSAE).
    33  C     F(I1:N)   FUNCTION MEASUREMENTS (INCLUDING NOISE).
    34  C
    35  C.... M E T H O D  (USER INTERFACE) ....
    36  C     THIS PROGRAM GENERATES RANDOMLY DATA AS FOLLOWS:
    37  C      A CONTINOUS (+CONVEX) FUNCTION F(X) DEFINED ON [XA,XB]
    38  C      IS SUPPLIED BY THE USER. THEN F(X) IS EVALUATED ON THE
    39  C      GRID XA=X(I1)<X(I1+1)<...<X(N)=XB AND THEN WE ADD
    40  C      TO THE FUNCTION VALUES RANDOM NUMBERS FROM THE UNIFORM
    41  C      DISTRIBUTION OVER THE INTERVAL [-SIZE,SIZE].
    42  C      THE TYPE OF THE FUNCTION, THE LIMITS OF THE DATA AND THE SIZE
    43  C      OF THE MAGNITUDE OF THE RANDOM NUMBERS ARE UPON THE USER'S
    44  C      DECISION. THE GRID NEED NOT BE EQUALLY SPACED.
    45  C
    46  C     THE METHOD THAT PRODUCES THE PSEUDO-RANDOM NUMBERS MAY BE
    47  C      FOUND IN FUNCTION RND(.).
    48  C
    49  C     THE DATA ARE GENERATED AND THEN DIRECTED TO FILE "XFDTA". THIS
    50  C      FILE IS INPUT TO PROGRAM PROG1.
    51  C......................................................................
    52  C
    53  C     SET DATA POINTS.
    54  C
    55        STEP=(XB-XA)/(N-I1)
    56        X(I1)=XA
    57        A=X(I1)
    58        DO 20 I=I1+1,N-1
    59           X(I)=A+STEP
    60  20       A=X(I)
    61        X(N)=XB
    62  C
    63  C     GENERATE DATA BY ADDING NOISE TO FUNCTION MEASUREMENTS OF THE
    64  C      RUNGE FUNCTION FROM 0.0 TO 1.0.
    65  C     ISEED IS SET BY THE USER. IT CAN BE ANY INTEGER SUCH THAT
    66  C       1 .LE. ISEED .LE. 65535 .
    67  C
    68        ISEED=1
    69        DO 50 I=I1,N
    70  50       F(I)=1/(1+10*X(I)*X(I))+SIZE*RND(ISEED)
    71  C
    72  C     SEND (X,F) DATA PAIRS TO A DATAFILE.
    73  C
    74        OPEN (2,FILE='XFDTA')
    75              WRITE (2,120) I1,N
    76  120         FORMAT (2I5)
    77              DO 130 I=I1,N
    78  130            WRITE (2,140) X(I),F(I)
    79  140            FORMAT (2E20.10)
    80        CLOSE(2)
    81        PRINT 1140
    82  1140  FORMAT(/5X,'DATA HAS BEEN GENERATED AND KEPT IN FILE "XFDTA".')
    83  C
    84        STOP
    85        END

PROG2  Local Symbols

NAME                      CLASS   TYPE

A . . . . . . . . . . . . local   REAL
F . . . . . . . . . . . . local   REAL ARRAY
I . . . . . . . . . . . . local   INTEGER
X . . . . . . . . . . . . local   REAL ARRAY
ISEED . . . . . . . . . . local   INTEGER
STEP. . . . . . . . . . . local   REAL


PROG2  Symbolic Constant   Type                Value

I1. . . . . . . . . . . .  INTEGER                           1
N . . . . . . . . . . . .  INTEGER                          75
XA. . . . . . . . . . . .  REAL               0.0000000E+000
XB. . . . . . . . . . . .  REAL               1.0000000E+000
SIZE. . . . . . . . . . .  REAL               8.8888891E-003

PROG2  Global Symbols

NAME                      CLASS                                   TYPE

RND . . . . . . . . . . . external                                REAL
main. . . . . . . . . . . program generating pseudorandomly
                          data for testing subroutine L2CXFT.



Function RND
------------

 Line#  Source Line

     1  C.....................................................................
     2  C     THIS FUNCTION GENERATES RANDOM NUMBERS SUCH THAT
     3  C               -1 < RND < 1
     4  C      WHICH ARE ADDED TO GIVEN FUNCTION MEASUREMENTS, IN ORDER
     5  C       TO CONSTRUCT DATA SETS FOR TESTING THE SUBROUTINE L2CXFT.
     6  C.....................................................................
     7        FUNCTION RND(ISEED)
     8  *     DOUBLE PRECISION RND
     9  C
    10  C     FUNCTION RND CAN GENERATE 65536 "RANDOM" NUMBERS BEFORE
    11  C      REPEATING ITSELF. IT WILL WORK ON MOST COMPUTERS FOR
    12  C      WHICH  2**31-1 .LT. MAXINT.
    13  C
    14  C.... I N P U T ....
    15  C     ISEED     INTEGER VARIABLE BETWEEN 1 AND 65535.
    16  C
    17  C.... O U T P U T ....
    18  C     RND       THE RETURN OF THE FUNCTION EVALUATION,
    19  C               BETWEEN -1 AND 1.
    20  C
    21  C.... M E T H O D (LINEAR CONGRUENTIAL)
    22  C      EACH NUMBER IN THE RANDOM SEQUENCE, R(K) SAY,
    23  C      IS CALCULATED FROM ITS PREDECESSOR, R(K-1), USING THE FORMULA:
    24  C               R(K)=(MULTIPLIER * R(K-1) + INCREMENT) MOD 2**16
    25  C      WHERE MULTIPLIER=25173 AND INCREMENT=13849.
    26  C
    27  C..... REF: P.GROGONO, PROGRAMMING IN PASCAL, ADDISON-WESLEY PUB.CO.,
    28  C          1980, P.118.
    29  C.....................................................................
    30        RND=FLOAT(ISEED)/65535.
    31        RND=2*RND-1
    32        ISEED=25173*ISEED+13849
    33        ISEED=MOD(ISEED,65536)
    34  C
    35        RETURN
    36        END


RND  Local Symbols

NAME                      CLASS

RND . . . . . . . . . . . function name
ISEED . . . . . . . . . . argument


RND  Global Symbols

NAME                      CLASS     TYPE        NUMBER of lines of code
                                                including comments
RND . . . . . . . . . . . FUNCTION  REAL        36




\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
APPENDIX C

INSTALLATION AND TESTING OF SUBROUTINE L2CXFT
=============================================

1. OVERVIEW
-----------
This appendix gives technical details about installation, compilation, linking
and running of the Fortran codes related to this work.

Eleven subroutines compose this software, whose purpose is stated in Section3
of the textual part of subroutine L2CXFT (Demetriou [1]). The codes  have  all
been compiled and executed successfully on the VAX 8810 at  Athens  University
of Economics, on  the  CDC  CYBER  171  computer  at  University  of  Ioannina
(Greece), on the T800 Inmos Transputer, on the MacintoshII and on MS-DOS  6.0
with the Microsoft Fortran 4.0 and 5.0.

We remind the names of the Fortran modules in  Appendix  A  (subroutines)  and
Appendix B (drivers and RND-generator). All modules preserve their name in the
single or double precision version (see comment about double precision in  the
beginning of Appendix A). The modules may also be found  in  machine  readable
forms with name extension .FOR.

Single precision codes
     L2CXFT.FOR
     L2ILS.FOR
     CFLGRF.FOR
     COEFF.FOR
     LAGRANG.FOR
     SXATXI.FOR
     ADDKNT.FOR
     PLUS.FOR
     DELKNT.FOR
     MINUS1.FOR
     MESSGE.FOR
     PROG1.FOR
     PROG2.FOR
     PROGMULT.FOR
     RND.FOR
          (15 modules)

Double precision codes
     L2CXFT.FOR
     L2ILS.FOR
     CFLGRF.FOR
     COEFF.FOR
     LAGRANG.FOR
     SXATXI.FOR
     ADDKNT.FOR
     PLUS.FOR
     DELKNT.FOR
     MINUS1.FOR
     MESSGE.FOR
     PROG1.FOR
     PROG2.FOR
     PROGMULT.FOR
     RND.FOR
          (15 modules)

2. INSTALLING THE SOURCE CODES
------------------------------
Copy all files from the diskette directory \DBL (or \SGL) to  a  directory  of
your computer system.

3. GENERATING DATA SETS FOR TESTING SUBROUTINE L2CXFT
-----------------------------------------------------
Consider the parameter settings of PROG2.FOR. Compile the  source  code  files
PROG2.FOR and RND.FOR. Link the resultant  objective  codes  with  the  system
Fortran library and call the executable code PROG2.EXE. Execute  PROG2.EXE  in
order to generate a data set to be used by subroutine  L2CXFT.  The  generated
data set is called,  by  default,  XFDTA.  Follow  the  process  described  in
Appendix B for more details. Comments are included in the  source  codes  that
explain the use of PROG2.FOR and RND.FOR.

4. APPLYING SUBROUTINE L2CXFT TO A DATA SET
-------------------------------------------
Suppose that the files mentioned in paragraph 2 are held in the same directory
with the data set file XFDTA that  was  produced  as  paragraph  3  describes.
Consider the parameter settings of PROG1.FOR. In  order  to  apply  subroutine
L2CXFT to the file XFDTA follow the process:

     1. Compile the following files
     PROG1.FOR
     L2CXFT.FOR
     L2ILS.FOR
     CFLGRF.FOR
     COEFF.FOR
     LAGRANG.FOR
     SXATXI.FOR
     ADDKNT.FOR
     PLUS.FOR
     DELKNT.FOR
     MINUS1.FOR
     MESSGE.FOR

     2. Link the resultant objective codes with the system Fortran library and
     call the executable code PROG1.EXE.

     3. Execute PROG1.EXE. Then the best convex fit to XFDTA is calculated and
     held in the file CXAPPX. Follow Appendix  B  for  details.  Comments  are
     included in the source code of PROG1.FOR that explain its use.

5. MULTIPLE TESTING OF SUBROUTINE L2CXFT ON SUBSTANTIALLY DIFFERENT DATA SETS
-----------------------------------------------------------------------------
Suppose that the installation described in  paragraph  2  has  been  completed
successfully. In order to show the performance of the  presented  codes  on  a
variety of data, we apply the program PROGMULT.FOR that generates data  as  it
is described in its source code and in Section 4 of Demetriou and Powell  [2]:
It lets the data size take the values N=20, 50, 100, 500, 1000, 2000, and  the
error magnitude take the values  SIZE=0,  10/(N*N),  50/(N*N),  250/(N*N)  and
1000/(N*N). For each value of SIZE, variable N takes all its values while  the
data sets are generated as PROG2.FOR describes. Each combination of SIZE and N
gives a short output about the active set changes of the current  calculation.
In order to apply PROGMULT.FOR follow the process:

     1. Compile the following files
     PROGMULT.FOR
     L2CXFT.FOR
     L2ILS.FOR
     CFLGRF.FOR
     COEFF.FOR
     LAGRANG.FOR
     SXATXI.FOR
     ADDKNT.FOR
     PLUS.FOR
     DELKNT.FOR
     MINUS1.FOR
     MESSGE.FOR
     RND.FOR

     2. Link the resultant objective codes with the system Fortran library and
     call the executable code PROGMULT.EXE.

     3. Execute PROGMULT.EXE. The results  are  presented  in  the  tables  of
     Demetriou and Powell [2]  accompanied  by  CPU  times  on  a  T800  Inmos
     transputer operating in a Macintosh II environment.




\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
APPENDIX D

REMARKS ON THE FORTRAN LISTINGS
===============================

This appendix addresses some details  of  the  fortran  subroutines  that  are
listed in Appendix A. Each of the eleven subroutines is considered  separately
in the order they appear in Appendix A. In order to make the code readable and
reasonably self-described,  all  Fortran  modules  begin  with  comments  that
explain the input and output arguments,  the  working  space  and  the  method
followed. Also, comments inside the code help readability. The references have
cited in the beginning of this document. For terminology,  equation  numbering
and references cited throughout this appendix, the reader should refer to  the
textual part of this work (Demetriou [1]).

SUBROUTINE L2CXFT
-----------------
Initially it is checked whether  N<I1  and  the  cases  I1=N  and  I1+1=N  are
considered. The instructions that include label 50  set  the  normals  of  the
constraints (1.2). The arrays EC(.) and DC(.) keep in EC(i)  and  DC(i+1)  the
second and the third component respectively of i-th divided  difference  (1.3)
scaled by (X(i+2)-X(i))/2, where i ranges from I1 to N-2. Arrays EC and DC are
used in the calculation of the Lagrange multipliers (Subroutine LAGRNG).

The following block of instructions  employs  subroutine  L2ILS  to  calculate
SX(.) and sets for first time the active set IACT.

The instructions that include labels 90 and  150  are  applied  no  more  than
|IACT| times inserting one knot at a time into the spline approximation  until
all Lagrange multipliers become non-negative. Each cycle  applies  subroutines
CFLGRF and ADDKNT. We let INKNOT=IPAR+1 be the data point  index  of  the  new
knot, where IPAR is the index of the most negative  Lagrange  multiplier.  The
value of INKNOT comes from the fact that the IPAR-th constraint is relaxed  by
inserting a knot at X(IPAR+1).

The block of instructions that includes labels 150-160 is always reached  with
non-negative {PAR(IACT(i)):i=I1,I1+1,..., NACT}. Here the feasibility of  the
constraints is examined. If no constraint violation is found then the  program
finishes. Otherwise KNTOUT denotes the index of the most violated  knot  among
the violated normalized constraints and IAKNJ denotes the  corresponding  data
point index.

The following test although unnecessary in theory, is a safeguard  to  prevent
an infinite loop. It is not activated when the first  main  iteration  begins.
Between labels 160 and 190 Powell's test checks for increase of the  objective
function as described in the paragraph that includes expression (2.7). If  the
test on the strict increase of (2.7) is  not  satisfied  then  the  subroutine
either (ITEST=1) returns with MODE=2 or (ITEST=0)  the  parameters  ITREF  and
ITEST are  both  set  to  one.  Now  (ITREF=1),  the  iteration  proceeds  and
subroutine CFLGRF activates iterative refinement in order to  correct  COEF(.)
and PAR(.).

Then subroutine DELKNT drops KNTOUT from the spline  knots  and  since  CFLGRF
should return  a  strictly  positive  value  to  PAR(IAKNJ-1),  the  condition
PAR(IAKNJ-1)0 is forced in order that the index IAKNJ-1 remain  in  IACT,  as
was noted in Section 2.

The block of instructions between labels 300-360 is entered if  at  least  one
negative Lagrange multipliers occurs. The instructions between labels  300-310
follow those in Lawson and Hanson [5, p.306]. The instructions between  labels
300-340 perform linear interpolation in order to recover the non-negativity of
PAR(IACT(.)), as already discussed in the penultimate paragraph of Section  2,
and branch to the block that tests termination. Since round-off errors in  the
calculation between labels 300-310 that implies THETA may cause some values of
PAROLD(IACT(.)) be negative, the instructions that  include  label  360  treat
them as being zero by excluding their indices from IACT (cf. p.164, Lawson and
Hanson [5]).

SUBROUTINE L2ILS
----------------
This subroutine  implements  Algorithm1  of  Demetriou  and  Powell  [4].  It
provides in only O(N-I1) arithmetic operations an excellent starting point for
the quadratic programming  calculation  defined  in  Section  1.  It  is  also
described in the textual part of this algorithm.

SUBROUTINE CFLGRF
-----------------
This subroutine initially calls subroutine COEFF to calculate the coefficients
{COEF(i): i=I1-1,I1, ...,NK} of the linear spline SX(.) that is represented by
the equations (2.4). Then subroutine  SXATXI  derives  the  spline  components
{SX(i): i=I1,I1+1,...,N} at {X(i): i=I1,I1+1,... ,N} from  COEF(.).  Then  the
Lagrange multipliers  {PAR(IACT(i)):  i=I1,I1+1,...,NACT}  are  calculated  by
calling subroutine LAGRNG. Because rounding errors may accumulate and  disturb
the  accuracy  of  the  spline  coefficients  and  the  Lagrange  multipliers,
iterative improvement of COEFF(.) and PAR(.) is applied when CFLGRF is  called
with the input parameter ITREF=1. The code for the refinement  of  COEF(.)  is
straightforward,  while  we  duplicate  part  of  the  code  that  appears  in
subroutine LAGRNG in order to correct  PAR(.).  The  total  work  required  by
subroutine CFLGRF amounts to O(N-I1) operations.

SUBROUTINE COEFF
----------------
This subroutine calculates the coefficients {COEF(i):  i=I1-1,I1,  ...,NK}  of
the linear spline SX(.)  that  is  represented  by  the  equations  (2.4).  It
requires O(NK-I1) operations.

SUBROUTINE SXATXI
-----------------
This subroutine calculates the spline components {SX(i): i=I1, I1+1,...,N}  at
{X(i):  i=I1,I1+1,...,N}  from  the  spline  coefficients  COEF(.)  (see,  for
example, p.194 in Schumaker [10]). It requires O(N-I1) operations.

SUBROUTINE LAGRNG
-----------------
This   subroutine   calculates   the   Lagrange   multipliers   {PAR(IACT(i)):
i=I1,I1+1,...,NACT} from  the  block  diagonal  positive  definite  system  of
equations that is derived from (2.5), due to the method referred to in Section
2. The main advantage in this calculation  is  that  it  utilizes  this  block
diagonal structure of the coefficient matrix for deriving the multipliers  but
the blocks are not known in advance. So  the  calculation  proceeds  by  first
detecting  the size of a block, and  then  applying  to  this  block  Cholesky
factorization, followed by a forward and a backward substitution in  order  to
derive the associated Lagrange multipliers. Due to (2.6), the  following  part
of the code finds the size of a block, say K, by counting the  number  of  the
consecutive components of IACT that  are  indices  of  consecutive  constraint
normals. Further, the index I ranges from I1 to NACT.
       I=I1
110    K=1
120    IF (I.LT.NACT .AND. IACT(I).EQ.IACT(I+1)-1) THEN
           I=I+1
           K=K+1
           GO TO 120
       END IF

Then  the  block  of  instructions  between  labels  130-140  apply   Cholesky
factorization to  the  K*K  tridiagonal  block  whose  diagonal  is  given  by
{EC(IACT(ll)): ll=I-K+1,I-K+2,...,I} and  its  subdiagonal  by  {DC(IACT(ll)):
ll=I+K+2,I+K+3,...I}. Working space that keeps the diagonal  elements  of  the
lower triangular factor is provided by the array UE(.). The instructions  that
include labels 150-160 apply standard forward  and  backward  substitution  to
calculate PAR(IACT(ll)) for ll=I-K+1,...,I. Then I is incremented by  one  and
the instructions that include labels 110-160 are repeated  until  I=NACT.  The
work required by subroutine LAGRNG amounts to O(NACT-I1) operations.

SUBROUTINE ADDKNT
-----------------
The purpose of this subroutine is to insert a knot into  AKN(.).  Let  INKNOT,
I1<INKNOT<N, be the data  index  of  a  knot  that  is  to  be  inserted.  The
instructions between labels 20-30 apply a  bisection  search  and  locate  the
integer J in the interval [I1,NK] that satisfies
                        AKN(J-1) < X(INKNOT) < AKN(J) .
The  instructions  that  include   label100   set   ARRAY(i+1)=ARRAY(i)   for
i=NK,NK-1,...,J, where ARRAY is any of the arrays E, B, D, AKN and IAKN.  Then
set NK=NK+1, AKN(J)=X(INKNOT) and IAKN(J)=INKNOT, and  the  following  changes
need to be made in the system of the normal equations. The new equation
                D(J)COEF(J-1)+E(J)COEF(J)+D(J+1)COEF(J+1)=B(J)
is adjoined to the system, and the equations
      D(ll)COEF(ll-1)+E(ll)COEF(ll)+D(ll+1)COEF(ll+1)=B(ll) ,  ll=J-1,J+1
need to be revised. Therefore  the  supports  of  the  "hat"  basis  functions
centered at  the  J-1,  J  and  (J+1)-th  knot  have  to  be  identified.  Let
X(IP)=AKN(J-1), X(IQ)=AKN(J) and X(IR)=AKN(J+1). If J=I1 or J=NK-1 the support
of the basis function  degenerates  to  the  interval  [AKN(I1-1),AKN(I1)]  or
[AKN(NK-1),AKN(NK)] respectively. Thus we define
                         / I1       ,  if J = I1
                   IPL =
                         \ IAKN(J-2),  if J > I1
and
                         / IAKN(J+2),  if J < NK-1
                   IRR =
                         \ N        ,  if J = NK-1.

In effect the (J-1)-th basis function is defined on [X(IPL), X(IQ)], the  J-th
basis  function  on  [X(IP),X(IR)]  and  the  (J+1)-th   basis   function   on
[X(IQ),X(IRR]. Therefore subroutine PLUS is safely applied  to calculate E(ll)
and B(ll) for ll=J-1,J,J+1 and D(ll) for ll=J,J+1.  Finally  the  instructions
that include label 110 revise  IACT(.)  and  reduce  NACT  by  one.  The  work
required by subroutine ADDKNT amounts to at most O(N-I1) operations.

SUBROUTINE PLUS
---------------
This subroutine is called by subroutine ADDKNT to revise the  equations  (2.4)
after inserting the data point X(INKNOT) into AKN(.). The  arguments  J,  IPL,
IP,  IR  and  IRR  have  already  been  defined  in  subroutine  ADDKNT.   The
calculations that are employed in this subroutine are based on the definitions
of the arrays E, D, B that follow the equation (2.4).  The  work  required  by
subroutine PLUS amounts to O(IR-IP) operations.

SUBROUTINE DELKNT
-----------------
This subroutine removes the knot AKN(KNTOUT),  I1-1<KNTOUT<NK,  from  {AKN(i):
i=I1-1,I1,...,NK}, revises the equations (2.4) by  calling  subroutine  MINUS1
and sets ARRAY(i)=ARRAY(i+1) for i=KNTOUT, KNTOUT+1,...,NK, where ARRAY is any
of the arrays E, B, D, AKN and IAKN. Finaly  it  revises  the  active  set  by
adding the constraint with index IAKN(KNTOUT) into IACT(.). The work  required
by subroutine DELKNT amounts to O(NK-KNTOUT) operations.

SUBROUTINE MINUS1
-----------------
This subroutine is called by subroutine DELKNT to revise the elements  E(J-1),
D(J), B(J-1), E(J+1), D(J+1) and B(J+1) when the knot AKN(J)  is  deleted.  It
implements formulae (2.9) and (2.10) of Demetriou and  Powell  [4].  The  work
required by subroutine MINUS1 amounts to O(1) operations.

SUBROUTINE MESSGE
-----------------
This subroutine includes messages associated with the operation of  subroutine
L2CXFT. It is activated when the input parameter IPRINT of L2CXFT  is  set  to
one. The PRINT statement is used for printing.

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
February 1995                                       Kifissia by Athens, Greece
                                                    I C DEMETRIOU (PhD Cantab)
