!***********************************************************************************
!                 This file contains all the subroutines and functions             * 
!                             required to run FAMOUS                               *
!                                                                                  *
!***********************************************************************************
!*                                                                                 *
!*                                 F A M O U S                                     *
!*                                                                                 * 
!*                  Frequency Analysis Mapping On Unusual Sampling                 * 
!*                  -         -        -       -  -       -                        * 
!*                           Program designed and written by                       * 
!*                          F. Mignard   OCA/Cassiopee & CNRS                      * 
!*                           francois.mignard@obs-nice.fr                          * 
!*                            Version 4.6 - December 2005                          * 
!*                                                                                 *
!*               SEARCH OF A SET OF FREQUENCIES IN A DISCRETE TIMES SERIES         *
!*                                                                                 *
!***********************************************************************************
! Version : 05/04/05 - replaces previous of 28/03/05
! Version : 12/07/05 - replaces previous of 05/04/05
! Version : 10/10/05 - replaces previous of 12/07/05   :: time data in input file not necessarily in increasing order
! Version : 25/11/05 - replaces previous of 10/10/05   :: iterative filtering, deletion of windowing, fine tuning of SDV for singular values
!***************************************************
! 
!                                   What FAMOUS does 
!                                   ----------------
! Famous carries out the frequency analysis of a time signal, with any kind of
! sampling. It can be used in many different situations to find periods in a signal,
! to represent the results of a numerical integration in solar system dynamics as
! as quasi-periodic function and identify the frequencies, to  obtain a convenient
! and compact expression of a signal containing many periodic lines, to remove the
! periodic or quasi-periodic components of a times series, etc.
!
! Usually time-series  derived from observations are not regularly sampled 
! (and may even be very very irregularly sampled in the case of astronomy or Earth
! science) and the main feature of this software is to handle these samplings.
! However it works very nicely on  regular sampling, providing  better results 
! than a standard FFT (accuracy in the frequencies, amplitudes and phases, 
! evaluation of the uncertainty), being obviously slower than a FFT.
!     
!***********************************************************************************
! Make sure that you have read the readme file before running the program          !           
! on your favorite data. If you want to learn how FAMOUS works, it might           !
! be adivsable that you start with the simulation mode by using the driver         !
! famous_driver_simul.f90 instead of the standard famous_driver.f90.               !
!                                                                                  !
! This software is offered without warranty of any kind, either expressed          !
! or implied.  The author would appreciate, however, any reports of bugs           !
! or other difficulties that may be encountered.                                   !
!***********************************************************************************
!
!
!  This file contains the two F90 modules needed to run FAMOUS :
!
!  module Levenberg_Marquardt  from MINIPACK and F90 version from A. Miller
!                            : performs non linear least squares.
!
!  module famouslib  : this is the main module for FAMOUS.
!                      it contains about 50 routines.
!                      it starts at line 2132 (string : 'module famouslib')
!
!  The modules must be compiled in this order,  in case you prefer to
!  edit them in two separate files.
!
!
!***********************************************************************************
!*************************
MODULE Levenberg_Marquardt
!*************************
!
! MINPACK routines which are used by both LMDIF & LMDER
! 25 October 2001:
!    Changed INTENT of iflag in several places to IN OUT.
!    Changed INTENT of fvec to IN OUT in user routine FCN.
!    Removed arguments diag and qtv from LMDIF & LMDER.
!    Replaced several DO loops with array operations.
! amiller @ bigpond.net.au

IMPLICIT NONE
INTEGER, PARAMETER :: dp = SELECTED_REAL_KIND(12, 60)

PRIVATE
PUBLIC :: dp, lmdif1, lmdif, lmder1, lmder, enorm

CONTAINS


SUBROUTINE lmdif1(fcn, m, n, x, fvec, tol, info, iwa)
 
! Code converted using TO_F90 by Alan Miller
! Date: 1999-12-11  Time: 00:51:44

! N.B. Arguments WA & LWA have been removed.

INTEGER, INTENT(IN)        :: m
INTEGER, INTENT(IN)        :: n
REAL (dp), INTENT(IN OUT)  :: x(:)
REAL (dp), INTENT(OUT)     :: fvec(:)
REAL (dp), INTENT(IN)      :: tol
INTEGER, INTENT(OUT)       :: info
INTEGER, INTENT(OUT)       :: iwa(:)

! EXTERNAL fcn

INTERFACE
  SUBROUTINE fcn(m, n, x, fvec, iflag)
    IMPLICIT NONE
    INTEGER, PARAMETER         :: dp = SELECTED_REAL_KIND(12, 60)
    INTEGER, INTENT(IN)        :: m, n
    REAL (dp), INTENT(IN)      :: x(:)
    REAL (dp), INTENT(IN OUT)  :: fvec(:)
    INTEGER, INTENT(IN OUT)    :: iflag
  END SUBROUTINE fcn
END INTERFACE

!  **********

!  subroutine lmdif1

!  The purpose of lmdif1 is to minimize the sum of the squares of m nonlinear
!  functions in n variables by a modification of the Levenberg-Marquardt
!  algorithm.  This is done by using the more general least-squares
!  solver lmdif.  The user must provide a subroutine which calculates the
!  functions.  The jacobian is then calculated by a forward-difference
!  approximation.

!  the subroutine statement is

!    subroutine lmdif1(fcn, m, n, x, fvec, tol, info, iwa)

!  where

!    fcn is the name of the user-supplied subroutine which calculates
!      the functions.  fcn must be declared in an external statement in the
!      user calling program, and should be written as follows.

!      subroutine fcn(m, n, x, fvec, iflag)
!      integer m, n, iflag
!      REAL (dp) x(n), fvec(m)
!      ----------
!      calculate the functions at x and return this vector in fvec.
!      ----------
!      return
!      end

!      the value of iflag should not be changed by fcn unless
!      the user wants to terminate execution of lmdif1.
!      In this case set iflag to a negative integer.

!    m is a positive integer input variable set to the number of functions.

!    n is a positive integer input variable set to the number of variables.
!      n must not exceed m.

!    x is an array of length n.  On input x must contain an initial estimate
!      of the solution vector.  On output x contains the final estimate of
!      the solution vector.

!    fvec is an output array of length m which contains
!      the functions evaluated at the output x.

!    tol is a nonnegative input variable.  Termination occurs when the
!      algorithm estimates either that the relative error in the sum of
!      squares is at most tol or that the relative error between x and the
!      solution is at most tol.

!    info is an integer output variable.  If the user has terminated execution,
!      info is set to the (negative) value of iflag.  See description of fcn.
!      Otherwise, info is set as follows.

!      info = 0  improper input parameters.

!      info = 1  algorithm estimates that the relative error
!                in the sum of squares is at most tol.

!      info = 2  algorithm estimates that the relative error
!                between x and the solution is at most tol.

!      info = 3  conditions for info = 1 and info = 2 both hold.

!      info = 4  fvec is orthogonal to the columns of the
!                jacobian to machine precision.

!      info = 5  number of calls to fcn has reached or exceeded 200*(n+1).

!      info = 6  tol is too small. no further reduction in
!                the sum of squares is possible.

!      info = 7  tol is too small.  No further improvement in
!                the approximate solution x is possible.

!    iwa is an integer work array of length n.

!    wa is a work array of length lwa.

!    lwa is a positive integer input variable not less than m*n+5*n+m.

!  subprograms called

!    user-supplied ...... fcn

!    minpack-supplied ... lmdif

!  argonne national laboratory. minpack project. march 1980.
!  burton s. garbow, kenneth e. hillstrom, jorge j. more

!  **********
INTEGER   :: maxfev, mode, nfev, nprint
REAL (dp) :: epsfcn, ftol, gtol, xtol, fjac(m,n)
REAL (dp), PARAMETER :: factor = 100._dp, zero = 0.0_dp

info = 0

!     check the input parameters for errors.

IF (n <= 0 .OR. m < n .OR. tol < zero) GO TO 10

!     call lmdif.

maxfev = 200*(n + 1)
ftol = tol
xtol = tol
gtol = zero
epsfcn = zero
mode = 1
nprint = 0
CALL lmdif(fcn, m, n, x, fvec, ftol, xtol, gtol, maxfev, epsfcn,   &
           mode, factor, nprint, info, nfev, fjac, iwa)
IF (info == 8) info = 4

10 RETURN

!     last card of subroutine lmdif1.

END SUBROUTINE lmdif1



SUBROUTINE lmdif(fcn, m, n, x, fvec, ftol, xtol, gtol, maxfev, epsfcn,  &
                 mode, factor, nprint, info, nfev, fjac, ipvt)
 
! N.B. Arguments LDFJAC, DIAG, QTF, WA1, WA2, WA3 & WA4 have been removed.

integer,   intent(in)        :: m
integer,   intent(in)        :: n
real (dp), intent(in out)    :: x(:)
real (dp), intent(out)       :: fvec(:)
real (dp), intent(in)        :: ftol
real (dp), intent(in)        :: xtol
real (dp), intent(in out)    :: gtol
integer,   intent(in out)    :: maxfev
real (dp), intent(in out)    :: epsfcn
integer,   intent(in)        :: mode
real (dp), intent(in)        :: factor
integer,   intent(in)        :: nprint
integer,   intent(out)       :: info
integer,   intent(out)       :: nfev
real (dp), intent(out)       :: fjac(:,:)    ! fjac(ldfjac,n)
integer,   intent(out)       :: ipvt(:)

! external fcn

interface
  subroutine fcn(m, n, x, fvec, iflag)
    implicit none
    integer,   parameter         :: dp = selected_real_kind(12, 60)
    integer,   intent(in)        :: m, n
    real (dp), intent(in)        :: x(:)
    real (dp), intent(in out)    :: fvec(:)
    integer,   intent(in out)    :: iflag
  end subroutine fcn
end interface

!  **********

!  subroutine lmdif

!  The purpose of lmdif is to minimize the sum of the squares of m nonlinear
!  functions in n variables by a modification of the Levenberg-Marquardt
!  algorithm.  The user must provide a subroutine which calculates the
!  functions.  The jacobian is then calculated by a forward-difference
!  approximation.

!  the subroutine statement is

!    subroutine lmdif(fcn, m, n, x, fvec, ftol, xtol, gtol, maxfev, epsfcn,
!                     diag, mode, factor, nprint, info, nfev, fjac,
!                     ldfjac, ipvt, qtf, wa1, wa2, wa3, wa4)

! N.B. 7 of these arguments have been removed in this version.

!  where

!    fcn is the name of the user-supplied subroutine which calculates the
!      functions.  fcn must be declared in an external statement in the user
!      calling program, and should be written as follows.

!      subroutine fcn(m, n, x, fvec, iflag)
!      integer m, n, iflag
!      REAL (dp) x(:), fvec(m)
!      ----------
!      calculate the functions at x and return this vector in fvec.
!      ----------
!      return
!      end

!      the value of iflag should not be changed by fcn unless
!      the user wants to terminate execution of lmdif.
!      in this case set iflag to a negative integer.

!    m is a positive integer input variable set to the number of functions.

!    n is a positive integer input variable set to the number of variables.
!      n must not exceed m.

!    x is an array of length n.  On input x must contain an initial estimate
!      of the solution vector.  On output x contains the final estimate of the
!      solution vector.

!    fvec is an output array of length m which contains
!      the functions evaluated at the output x.

!    ftol is a nonnegative input variable.  Termination occurs when both the
!      actual and predicted relative reductions in the sum of squares are at
!      most ftol.  Therefore, ftol measures the relative error desired
!      in the sum of squares.

!    xtol is a nonnegative input variable.  Termination occurs when the
!      relative error between two consecutive iterates is at most xtol.
!      Therefore, xtol measures the relative error desired in the approximate
!      solution.

!    gtol is a nonnegative input variable.  Termination occurs when the cosine
!      of the angle between fvec and any column of the jacobian is at most
!      gtol in absolute value.  Therefore, gtol measures the orthogonality
!      desired between the function vector and the columns of the jacobian.

!    maxfev is a positive integer input variable.  Termination occurs when the
!      number of calls to fcn is at least maxfev by the end of an iteration.

!    epsfcn is an input variable used in determining a suitable step length
!      for the forward-difference approximation.  This approximation assumes
!      that the relative errors in the functions are of the order of epsfcn.
!      If epsfcn is less than the machine precision, it is assumed that the
!      relative errors in the functions are of the order of the machine
!      precision.

!    diag is an array of length n.  If mode = 1 (see below), diag is
!      internally set.  If mode = 2, diag must contain positive entries that
!      serve as multiplicative scale factors for the variables.

!    mode is an integer input variable.  If mode = 1, the variables will be
!      scaled internally.  If mode = 2, the scaling is specified by the input
!      diag. other values of mode are equivalent to mode = 1.

!    factor is a positive input variable used in determining the initial step
!      bound.  This bound is set to the product of factor and the euclidean
!      norm of diag*x if nonzero, or else to factor itself.  In most cases
!      factor should lie in the interval (.1,100.). 100. is a generally
!      recommended value.

!    nprint is an integer input variable that enables controlled printing of
!      iterates if it is positive.  In this case, fcn is called with iflag = 0
!      at the beginning of the first iteration and every nprint iterations
!      thereafter and immediately prior to return, with x and fvec available
!      for printing.  If nprint is not positive, no special calls
!      of fcn with iflag = 0 are made.

!    info is an integer output variable.  If the user has terminated
!      execution, info is set to the (negative) value of iflag.
!      See description of fcn.  Otherwise, info is set as follows.

!      info = 0  improper input parameters.

!      info = 1  both actual and predicted relative reductions
!                in the sum of squares are at most ftol.

!      info = 2  relative error between two consecutive iterates <= xtol.

!      info = 3  conditions for info = 1 and info = 2 both hold.

!      info = 4  the cosine of the angle between fvec and any column of
!                the Jacobian is at most gtol in absolute value.

!      info = 5  number of calls to fcn has reached or exceeded maxfev.

!      info = 6  ftol is too small. no further reduction in
!                the sum of squares is possible.

!      info = 7  xtol is too small. no further improvement in
!                the approximate solution x is possible.

!      info = 8  gtol is too small. fvec is orthogonal to the
!                columns of the jacobian to machine precision.

!    nfev is an integer output variable set to the number of calls to fcn.

!    fjac is an output m by n array. the upper n by n submatrix
!      of fjac contains an upper triangular matrix r with
!      diagonal elements of nonincreasing magnitude such that

!             t     t           t
!            p *(jac *jac)*p = r *r,

!      where p is a permutation matrix and jac is the final calculated
!      Jacobian.  Column j of p is column ipvt(j) (see below) of the
!      identity matrix. the lower trapezoidal part of fjac contains
!      information generated during the computation of r.

!    ldfjac is a positive integer input variable not less than m
!      which specifies the leading dimension of the array fjac.

!    ipvt is an integer output array of length n.  ipvt defines a permutation
!      matrix p such that jac*p = q*r, where jac is the final calculated
!      jacobian, q is orthogonal (not stored), and r is upper triangular
!      with diagonal elements of nonincreasing magnitude.
!      Column j of p is column ipvt(j) of the identity matrix.

!    qtf is an output array of length n which contains
!      the first n elements of the vector (q transpose)*fvec.

!    wa1, wa2, and wa3 are work arrays of length n.

!    wa4 is a work array of length m.

!  subprograms called

!    user-supplied ...... fcn

!    minpack-supplied ... dpmpar,enorm,fdjac2,lmpar,qrfac

!    fortran-supplied ... dabs,dmax1,dmin1,dsqrt,mod

!  argonne national laboratory. minpack project. march 1980.
!  burton s. garbow, kenneth e. hillstrom, jorge j. more

!  **********
INTEGER   :: i, iflag, iter, j, l
REAL (dp) :: actred, delta, dirder, epsmch, fnorm, fnorm1, gnorm,  &
             par, pnorm, prered, ratio, sum, temp, temp1, temp2, xnorm
REAL (dp) :: diag(n), qtf(n), wa1(n), wa2(n), wa3(n), wa4(m)
REAL (dp), PARAMETER :: one = 1.0_dp, p1 = 0.1_dp, p5 = 0.5_dp,  &
                        p25 = 0.25_dp, p75 = 0.75_dp, p0001 = 0.0001_dp, &
                        zero = 0.0_dp

!     epsmch is the machine precision.

epsmch = EPSILON(zero)

info = 0
iflag = 0
nfev = 0

!     check the input parameters for errors.

IF (n <= 0 .OR. m < n .OR. ftol < zero .OR. xtol < zero .OR. gtol < zero  &
    .OR. maxfev <= 0 .OR. factor <= zero) GO TO 300
IF (mode /= 2) GO TO 20
DO  j = 1, n
  IF (diag(j) <= zero) GO TO 300
END DO

!     evaluate the function at the starting point and calculate its norm.

20 iflag = 1
CALL fcn(m, n, x, fvec, iflag)
nfev = 1
IF (iflag < 0) GO TO 300
fnorm = enorm(m, fvec)

!     initialize levenberg-marquardt parameter and iteration counter.

par = zero
iter = 1

!     beginning of the outer loop.

!        calculate the jacobian matrix.

30 iflag = 2
CALL fdjac2(fcn, m, n, x, fvec, fjac, iflag, epsfcn)
nfev = nfev + n
IF (iflag < 0) GO TO 300

!        If requested, call fcn to enable printing of iterates.

IF (nprint <= 0) GO TO 40
iflag = 0
IF (MOD(iter-1,nprint) == 0) CALL fcn(m, n, x, fvec, iflag)
IF (iflag < 0) GO TO 300

!        Compute the qr factorization of the jacobian.

40 CALL qrfac(m, n, fjac, .true., ipvt, wa1, wa2)

!        On the first iteration and if mode is 1, scale according
!        to the norms of the columns of the initial jacobian.

IF (iter /= 1) GO TO 80
IF (mode == 2) GO TO 60
DO  j = 1, n
  diag(j) = wa2(j)
  IF (wa2(j) == zero) diag(j) = one
END DO

!        On the first iteration, calculate the norm of the scaled x
!        and initialize the step bound delta.

60 wa3(1:n) = diag(1:n)*x(1:n)
xnorm = enorm(n, wa3)
delta = factor*xnorm
IF (delta == zero) delta = factor

!        Form (q transpose)*fvec and store the first n components in qtf.

80 wa4(1:m) = fvec(1:m)
DO  j = 1, n
  IF (fjac(j,j) == zero) GO TO 120
  sum = DOT_PRODUCT( fjac(j:m,j), wa4(j:m) )
  temp = -sum/fjac(j,j)
  DO  i = j, m
    wa4(i) = wa4(i) + fjac(i,j)*temp
  END DO
  120 fjac(j,j) = wa1(j)
  qtf(j) = wa4(j)
END DO

!        compute the norm of the scaled gradient.

gnorm = zero
IF (fnorm == zero) GO TO 170
DO  j = 1, n
  l = ipvt(j)
  IF (wa2(l) == zero) CYCLE
  sum = zero
  DO  i = 1, j
    sum = sum + fjac(i,j)*(qtf(i)/fnorm)
  END DO
  gnorm = MAX(gnorm, ABS(sum/wa2(l)))
END DO

!        test for convergence of the gradient norm.

170 IF (gnorm <= gtol) info = 4
IF (info /= 0) GO TO 300

!        rescale if necessary.

IF (mode == 2) GO TO 200
DO  j = 1, n
  diag(j) = MAX(diag(j), wa2(j))
END DO

!        beginning of the inner loop.

!           determine the Levenberg-Marquardt parameter.

200 CALL lmpar(n, fjac, ipvt, diag, qtf, delta, par, wa1, wa2)

!           store the direction p and x + p. calculate the norm of p.

DO  j = 1, n
  wa1(j) = -wa1(j)
  wa2(j) = x(j) + wa1(j)
  wa3(j) = diag(j)*wa1(j)
END DO
pnorm = enorm(n, wa3)

!           on the first iteration, adjust the initial step bound.

IF (iter == 1) delta = MIN(delta, pnorm)

!           evaluate the function at x + p and calculate its norm.

iflag = 1
CALL fcn(m, n, wa2, wa4, iflag)
nfev = nfev + 1
IF (iflag < 0) GO TO 300
fnorm1 = enorm(m, wa4)

!           compute the scaled actual reduction.

actred = -one
IF (p1*fnorm1 < fnorm) actred = one - (fnorm1/fnorm)**2

!           Compute the scaled predicted reduction and
!           the scaled directional derivative.

DO  j = 1, n
  wa3(j) = zero
  l = ipvt(j)
  temp = wa1(l)
  DO  i = 1, j
    wa3(i) = wa3(i) + fjac(i,j)*temp
  END DO
END DO
temp1 = enorm(n,wa3)/fnorm
temp2 = (SQRT(par)*pnorm)/fnorm
prered = temp1**2 + temp2**2/p5
dirder = -(temp1**2 + temp2**2)

!           compute the ratio of the actual to the predicted reduction.

ratio = zero
IF (prered /= zero) ratio = actred/prered

!           update the step bound.

IF (ratio <= p25) THEN
  IF (actred >= zero) temp = p5
  IF (actred < zero) temp = p5*dirder/(dirder + p5*actred)
  IF (p1*fnorm1 >= fnorm .OR. temp < p1) temp = p1
  delta = temp*MIN(delta,pnorm/p1)
  par = par/temp
ELSE
  IF (par /= zero .AND. ratio < p75) GO TO 260
  delta = pnorm/p5
  par = p5*par
END IF

!           test for successful iteration.

260 IF (ratio < p0001) GO TO 290

!           successful iteration. update x, fvec, and their norms.

DO  j = 1, n
  x(j) = wa2(j)
  wa2(j) = diag(j)*x(j)
END DO
fvec(1:m) = wa4(1:m)
xnorm = enorm(n, wa2)
fnorm = fnorm1
iter = iter + 1

!           tests for convergence.

290 IF (ABS(actred) <= ftol .AND. prered <= ftol .AND. p5*ratio <= one) info = 1
IF (delta <= xtol*xnorm) info = 2
IF (ABS(actred) <= ftol .AND. prered <= ftol  &
    .AND. p5*ratio <= one .AND. info == 2) info = 3
IF (info /= 0) GO TO 300

!           tests for termination and stringent tolerances.

IF (nfev >= maxfev) info = 5
IF (ABS(actred) <= epsmch .AND. prered <= epsmch  &
    .AND. p5*ratio <= one) info = 6
IF (delta <= epsmch*xnorm) info = 7
IF (gnorm <= epsmch) info = 8
IF (info /= 0) GO TO 300

!           end of the inner loop. repeat if iteration unsuccessful.

IF (ratio < p0001) GO TO 200

!        end of the outer loop.

GO TO 30

!     termination, either normal or user imposed.

300 IF (iflag < 0) info = iflag
iflag = 0
IF (nprint > 0) CALL fcn(m, n, x, fvec, iflag)
RETURN

!     last card of subroutine lmdif.

END SUBROUTINE lmdif



SUBROUTINE lmder1(fcn, m, n, x, fvec, fjac, tol, info, ipvt)

 
! Code converted using TO_F90 by Alan Miller
! Date: 1999-12-09  Time: 12:45:54

! N.B. Arguments LDFJAC, WA & LWA have been removed.

INTEGER, INTENT(IN)        :: m
INTEGER, INTENT(IN)        :: n
REAL (dp), INTENT(IN OUT)  :: x(:)
REAL (dp), INTENT(OUT)     :: fvec(:)
REAL (dp), INTENT(IN OUT)  :: fjac(:,:)    ! fjac(ldfjac,n)
REAL (dp), INTENT(IN)      :: tol
INTEGER, INTENT(OUT)       :: info
INTEGER, INTENT(IN OUT)    :: ipvt(:)


 EXTERNAL fcn

!INTERFACE
!  SUBROUTINE fcn(m, n, x, fvec, fjac, iflag)
!    IMPLICIT NONE
!    INTEGER, PARAMETER         :: dp = SELECTED_REAL_KIND(12, 60)
!    INTEGER, INTENT(IN)        :: m, n
!    REAL (8),  INTENT(IN)      :: x(:)
!    REAL (8),  INTENT(IN OUT)  :: fvec(:)
!    REAL (8),  INTENT(OUT)     :: fjac(:,:)
!    INTEGER, INTENT(IN OUT)    :: iflag
!  END SUBROUTINE fcn
!END INTERFACE

!  **********

!  subroutine lmder1

!  The purpose of lmder1 is to minimize the sum of the squares of
!  m nonlinear functions in n variables by a modification of the
!  levenberg-marquardt algorithm.  This is done by using the more
!  general least-squares solver lmder.  The user must provide a
!  subroutine which calculates the functions and the jacobian.

!  the subroutine statement is

!    subroutine lmder1(fcn, m, n, x, fvec, fjac, tol, info, ipvt)

!  where

!    fcn is the name of the user-supplied subroutine which
!      calculates the functions and the jacobian.  fcn must
!      be declared in an interface statement in the user
!      calling program, and should be written as follows.

!      subroutine fcn(m, n, x, fvec, fjac, iflag)
!      integer   :: m, n, ldfjac, iflag
!      REAL (dp) :: x(:), fvec(:), fjac(:,:)
!      ----------
!      if iflag = 1 calculate the functions at x and
!      return this vector in fvec. do not alter fjac.
!      if iflag = 2 calculate the jacobian at x and
!      return this matrix in fjac. do not alter fvec.
!      ----------
!      return
!      end

!      the value of iflag should not be changed by fcn unless
!      the user wants to terminate execution of lmder1.
!      in this case set iflag to a negative integer.

!    m is a positive integer input variable set to the number of functions.

!    n is a positive integer input variable set to the number
!      of variables.  n must not exceed m.

!    x is an array of length n. on input x must contain
!      an initial estimate of the solution vector. on output x
!      contains the final estimate of the solution vector.

!    fvec is an output array of length m which contains
!      the functions evaluated at the output x.

!    fjac is an output m by n array. the upper n by n submatrix
!      of fjac contains an upper triangular matrix r with
!      diagonal elements of nonincreasing magnitude such that

!             t     t           t
!            p *(jac *jac)*p = r *r,

!      where p is a permutation matrix and jac is the final calculated
!      Jacobian.  Column j of p is column ipvt(j) (see below) of the
!      identity matrix.  The lower trapezoidal part of fjac contains
!      information generated during the computation of r.

!    ldfjac is a positive integer input variable not less than m
!      which specifies the leading dimension of the array fjac.

!    tol is a nonnegative input variable. termination occurs
!      when the algorithm estimates either that the relative
!      error in the sum of squares is at most tol or that
!      the relative error between x and the solution is at most tol.

!    info is an integer output variable.  If the user has terminated
!      execution, info is set to the (negative) value of iflag.
!      See description of fcn.  Otherwise, info is set as follows.

!      info = 0  improper input parameters.

!      info = 1  algorithm estimates that the relative error
!                in the sum of squares is at most tol.

!      info = 2  algorithm estimates that the relative error
!                between x and the solution is at most tol.

!      info = 3  conditions for info = 1 and info = 2 both hold.

!      info = 4  fvec is orthogonal to the columns of the
!                jacobian to machine precision.

!      info = 5  number of calls to fcn with iflag = 1 has reached 100*(n+1).

!      info = 6  tol is too small.  No further reduction in
!                the sum of squares is possible.

!      info = 7  tol is too small.  No further improvement in
!                the approximate solution x is possible.

!    ipvt is an integer output array of length n. ipvt
!      defines a permutation matrix p such that jac*p = q*r,
!      where jac is the final calculated jacobian, q is
!      orthogonal (not stored), and r is upper triangular
!      with diagonal elements of nonincreasing magnitude.
!      column j of p is column ipvt(j) of the identity matrix.

!    wa is a work array of length lwa.

!    lwa is a positive integer input variable not less than 5*n+m.

!  subprograms called

!    user-supplied ...... fcn

!    minpack-supplied ... lmder

!  argonne national laboratory. minpack project. march 1980.
!  burton s. garbow, kenneth e. hillstrom, jorge j. more

!  **********
INTEGER   :: maxfev, mode, nfev, njev, nprint
REAL (dp) :: ftol, gtol, xtol
REAL (dp), PARAMETER :: factor = 100._dp, zero = 0.0_dp

info = 0

!     check the input parameters for errors.

IF ( n <= 0 .OR. m < n .OR. tol < zero ) GO TO 10

!     call lmder.

maxfev = 100*(n + 1)
ftol = tol
xtol = tol
gtol = zero
mode = 1
nprint = 0
CALL lmder(fcn, m, n, x, fvec, fjac, ftol, xtol, gtol, maxfev,  &
           mode, factor, nprint, info, nfev, njev, ipvt)
IF (info == 8) info = 4

10 RETURN

!     last card of subroutine lmder1.

END SUBROUTINE lmder1



SUBROUTINE lmder(fcn, m, n, x, fvec, fjac, ftol, xtol, gtol, maxfev, &
                 mode, factor, nprint, info, nfev, njev, ipvt)


 
! Code converted using TO_F90 by Alan Miller
! Date: 1999-12-09  Time: 12:45:50

! N.B. Arguments LDFJAC, DIAG, QTF, WA1, WA2, WA3 & WA4 have been removed.

INTEGER, INTENT(IN)        :: m
INTEGER, INTENT(IN)        :: n
REAL (dp), INTENT(IN OUT)  :: x(:)
REAL (dp), INTENT(OUT)     :: fvec(m)
REAL (dp), INTENT(OUT)     :: fjac(:,:)    ! fjac(ldfjac,n)
REAL (dp), INTENT(IN)      :: ftol
REAL (dp), INTENT(IN)      :: xtol
REAL (dp), INTENT(IN OUT)  :: gtol
INTEGER, INTENT(IN OUT)    :: maxfev
INTEGER, INTENT(IN)        :: mode
REAL (dp), INTENT(IN)      :: factor
INTEGER, INTENT(IN)        :: nprint
INTEGER, INTENT(OUT)       :: info
INTEGER, INTENT(OUT)       :: nfev
INTEGER, INTENT(OUT)       :: njev
INTEGER, INTENT(OUT)       :: ipvt(:)

external fcn

!INTERFACE
!  SUBROUTINE fcn(m, n, x, fvec, fjac, iflag)
!    IMPLICIT NONE
!    INTEGER, PARAMETER :: dp = SELECTED_REAL_KIND(12, 60)
!    INTEGER, INTENT(IN)        :: m, n
!    REAL (dp), INTENT(IN)      :: x(:)
!    REAL (dp), INTENT(IN OUT)  :: fvec(:)
!    REAL (dp), INTENT(OUT)     :: fjac(:,:)
!    INTEGER, INTENT(IN OUT)    :: iflag
!  END SUBROUTINE fcn
!END INTERFACE


!  **********

!  subroutine lmder

!  the purpose of lmder is to minimize the sum of the squares of
!  m nonlinear functions in n variables by a modification of
!  the levenberg-marquardt algorithm. the user must provide a
!  subroutine which calculates the functions and the jacobian.

!  the subroutine statement is

!    subroutine lmder(fcn,m,n,x,fvec,fjac,ldfjac,ftol,xtol,gtol,
!                     maxfev,diag,mode,factor,nprint,info,nfev,
!                     njev,ipvt,qtf,wa1,wa2,wa3,wa4)

!  where

!    fcn is the name of the user-supplied subroutine which
!      calculates the functions and the jacobian. fcn must
!      be declared in an external statement in the user
!      calling program, and should be written as follows.

!      subroutine fcn(m,n,x,fvec,fjac,ldfjac,iflag)
!      integer m,n,ldfjac,iflag
!      REAL (dp) x(:),fvec(m),fjac(ldfjac,n)
!      ----------
!      if iflag = 1 calculate the functions at x and
!      return this vector in fvec. do not alter fjac.
!      if iflag = 2 calculate the jacobian at x and
!      return this matrix in fjac.  Do not alter fvec.
!      ----------
!      return
!      end

!      the value of iflag should not be changed by fcn unless
!      the user wants to terminate execution of lmder.
!      in this case set iflag to a negative integer.

!    m is a positive integer input variable set to the number
!      of functions.

!    n is a positive integer input variable set to the number
!      of variables. n must not exceed m.

!    x is an array of length n. on input x must contain
!      an initial estimate of the solution vector. on output x
!      contains the final estimate of the solution vector.

!    fvec is an output array of length m which contains
!      the functions evaluated at the output x.

!    fjac is an output m by n array. the upper n by n submatrix
!      of fjac contains an upper triangular matrix r with
!      diagonal elements of nonincreasing magnitude such that

!             t     t           t
!            p *(jac *jac)*p = r *r

!      where p is a permutation matrix and jac is the final calculated
!      jacobian.  Column j of p is column ipvt(j) (see below) of the
!      identity matrix.  The lower trapezoidal part of fjac contains
!      information generated during the computation of r.

!    ldfjac is a positive integer input variable not less than m
!      which specifies the leading dimension of the array fjac.

!    ftol is a nonnegative input variable.  Termination occurs when both
!      the actual and predicted relative reductions in the sum of squares
!      are at most ftol.   Therefore, ftol measures the relative error
!      desired in the sum of squares.

!    xtol is a nonnegative input variable. termination
!      occurs when the relative error between two consecutive
!      iterates is at most xtol. therefore, xtol measures the
!      relative error desired in the approximate solution.

!    gtol is a nonnegative input variable.  Termination occurs when the
!      cosine of the angle between fvec and any column of the jacobian is
!      at most gtol in absolute value.  Therefore, gtol measures the
!      orthogonality desired between the function vector and the columns
!      of the jacobian.

!    maxfev is a positive integer input variable.  Termination occurs when
!      the number of calls to fcn with iflag = 1 has reached maxfev.

!    diag is an array of length n.  If mode = 1 (see below), diag is
!      internally set.  If mode = 2, diag must contain positive entries
!      that serve as multiplicative scale factors for the variables.

!    mode is an integer input variable.  if mode = 1, the
!      variables will be scaled internally.  if mode = 2,
!      the scaling is specified by the input diag.  other
!      values of mode are equivalent to mode = 1.

!    factor is a positive input variable used in determining the
!      initial step bound. this bound is set to the product of
!      factor and the euclidean norm of diag*x if nonzero, or else
!      to factor itself. in most cases factor should lie in the
!      interval (.1,100.).100. is a generally recommended value.

!    nprint is an integer input variable that enables controlled printing
!      of iterates if it is positive.  In this case, fcn is called with
!      iflag = 0 at the beginning of the first iteration and every nprint
!      iterations thereafter and immediately prior to return, with x, fvec,
!      and fjac available for printing.  fvec and fjac should not be
!      altered.  If nprint is not positive, no special calls of fcn with
!      iflag = 0 are made.

!    info is an integer output variable.  If the user has terminated
!      execution, info is set to the (negative) value of iflag.
!      See description of fcn.  Otherwise, info is set as follows.

!      info = 0  improper input parameters.

!      info = 1  both actual and predicted relative reductions
!                in the sum of squares are at most ftol.

!      info = 2  relative error between two consecutive iterates
!                is at most xtol.

!      info = 3  conditions for info = 1 and info = 2 both hold.

!      info = 4  the cosine of the angle between fvec and any column of
!                the jacobian is at most gtol in absolute value.

!      info = 5  number of calls to fcn with iflag = 1 has reached maxfev.

!      info = 6  ftol is too small.  No further reduction in
!                the sum of squares is possible.

!      info = 7  xtol is too small.  No further improvement in
!                the approximate solution x is possible.

!      info = 8  gtol is too small.  fvec is orthogonal to the
!                columns of the jacobian to machine precision.

!    nfev is an integer output variable set to the number of
!      calls to fcn with iflag = 1.

!    njev is an integer output variable set to the number of
!      calls to fcn with iflag = 2.

!    ipvt is an integer output array of length n.  ipvt
!      defines a permutation matrix p such that jac*p = q*r,
!      where jac is the final calculated jacobian, q is
!      orthogonal (not stored), and r is upper triangular
!      with diagonal elements of nonincreasing magnitude.
!      column j of p is column ipvt(j) of the identity matrix.

!    qtf is an output array of length n which contains
!      the first n elements of the vector (q transpose)*fvec.

!    wa1, wa2, and wa3 are work arrays of length n.

!    wa4 is a work array of length m.

!  subprograms called

!    user-supplied ...... fcn

!    minpack-supplied ... dpmpar,enorm,lmpar,qrfac

!    fortran-supplied ... ABS,MAX,MIN,SQRT,mod

!  argonne national laboratory. minpack project. march 1980.
!  burton s. garbow, kenneth e. hillstrom, jorge j. more

!  **********
INTEGER   :: i, iflag, iter, j, l
REAL (dp) :: actred, delta, dirder, epsmch, fnorm, fnorm1, gnorm,  &
             par, pnorm, prered, ratio, sum, temp, temp1, temp2, xnorm
REAL (dp) :: diag(n), qtf(n), wa1(n), wa2(n), wa3(n), wa4(m)
REAL (dp), PARAMETER :: one = 1.0_dp, p1 = 0.1_dp, p5 = 0.5_dp,  &
                        p25 = 0.25_dp, p75 = 0.75_dp, p0001 = 0.0001_dp, &
                        zero = 0.0_dp

!     epsmch is the machine precision.

epsmch = EPSILON(zero)

info = 0
iflag = 0
nfev = 0
njev = 0

!     check the input parameters for errors.

IF (n <= 0 .OR. m < n .OR. ftol < zero .OR. xtol < zero .OR. gtol < zero  &
    .OR. maxfev <= 0 .OR. factor <= zero) GO TO 300
IF (mode /= 2) GO TO 20
DO  j = 1, n
  IF (diag(j) <= zero) GO TO 300
END DO

!     evaluate the function at the starting point and calculate its norm.

20 iflag = 1

CALL fcn(m, n, x, fvec, fjac, iflag)
 
nfev = 1
IF (iflag < 0) GO TO 300
fnorm = enorm(m, fvec)

!     initialize levenberg-marquardt parameter and iteration counter.

par = zero
iter = 1

!     beginning of the outer loop.

!        calculate the jacobian matrix.

30 iflag = 2
CALL fcn(m, n, x, fvec, fjac, iflag)
njev = njev + 1
IF (iflag < 0) GO TO 300

!        if requested, call fcn to enable printing of iterates.

IF (nprint <= 0) GO TO 40
iflag = 0
IF (MOD(iter-1,nprint) == 0) CALL fcn(m, n, x, fvec, fjac, iflag)
IF (iflag < 0) GO TO 300

!        compute the qr factorization of the jacobian.

40 CALL qrfac(m, n, fjac, .true., ipvt, wa1, wa2)

!        on the first iteration and if mode is 1, scale according
!        to the norms of the columns of the initial jacobian.

IF (iter /= 1) GO TO 80
IF (mode == 2) GO TO 60
DO  j = 1, n
  diag(j) = wa2(j)
  IF (wa2(j) == zero) diag(j) = one
END DO

!        on the first iteration, calculate the norm of the scaled x
!        and initialize the step bound delta.

60 wa3(1:n) = diag(1:n)*x(1:n)
xnorm = enorm(n,wa3)
delta = factor*xnorm
IF (delta == zero) delta = factor

!        form (q transpose)*fvec and store the first n components in qtf.

80 wa4(1:m) = fvec(1:m)
DO  j = 1, n
  IF (fjac(j,j) == zero) GO TO 120
  sum = DOT_PRODUCT( fjac(j:m,j), wa4(j:m) )
  temp = -sum/fjac(j,j)
  DO  i = j, m
    wa4(i) = wa4(i) + fjac(i,j)*temp
  END DO
  120 fjac(j,j) = wa1(j)
  qtf(j) = wa4(j)
END DO

!        compute the norm of the scaled gradient.

gnorm = zero
IF (fnorm == zero) GO TO 170
DO  j = 1, n
  l = ipvt(j)
  IF (wa2(l) == zero) CYCLE
  sum = zero
  DO  i = 1, j
    sum = sum + fjac(i,j)*(qtf(i)/fnorm)
  END DO
  gnorm = MAX(gnorm,ABS(sum/wa2(l)))
END DO

!        test for convergence of the gradient norm.

170 IF (gnorm <= gtol) info = 4
IF (info /= 0) GO TO 300

!        rescale if necessary.

IF (mode == 2) GO TO 200
DO  j = 1, n
  diag(j) = MAX(diag(j), wa2(j))
END DO

!        beginning of the inner loop.

!           determine the levenberg-marquardt parameter.

200 CALL lmpar(n, fjac, ipvt, diag, qtf, delta, par, wa1, wa2)

!           store the direction p and x + p. calculate the norm of p.

DO  j = 1, n
  wa1(j) = -wa1(j)
  wa2(j) = x(j) + wa1(j)
  wa3(j) = diag(j)*wa1(j)
END DO
pnorm = enorm(n, wa3)

!           on the first iteration, adjust the initial step bound.

IF (iter == 1) delta = MIN(delta,pnorm)

!           evaluate the function at x + p and calculate its norm.

iflag = 1
CALL fcn(m, n, wa2, wa4, fjac, iflag)
nfev = nfev + 1
IF (iflag < 0) GO TO 300
fnorm1 = enorm(m, wa4)

!           compute the scaled actual reduction.

actred = -one
IF (p1*fnorm1 < fnorm) actred = one - (fnorm1/fnorm)**2

!           compute the scaled predicted reduction and
!           the scaled directional derivative.

DO  j = 1, n
  wa3(j) = zero
  l = ipvt(j)
  temp = wa1(l)
  wa3(1:j) = wa3(1:j) + fjac(1:j,j)*temp
END DO
temp1 = enorm(n,wa3)/fnorm
temp2 = (SQRT(par)*pnorm)/fnorm
prered = temp1**2 + temp2**2/p5
dirder = -(temp1**2 + temp2**2)

!           compute the ratio of the actual to the predicted reduction.

ratio = zero
IF (prered /= zero) ratio = actred/prered

!           update the step bound.

IF (ratio <= p25) THEN
  IF (actred >= zero) temp = p5
  IF (actred < zero) temp = p5*dirder/(dirder + p5*actred)
  IF (p1*fnorm1 >= fnorm .OR. temp < p1) temp = p1
  delta = temp*MIN(delta, pnorm/p1)
  par = par/temp
ELSE
  IF (par /= zero .AND. ratio < p75) GO TO 260
  delta = pnorm/p5
  par = p5*par
END IF

!           test for successful iteration.

260 IF (ratio < p0001) GO TO 290

!           successful iteration. update x, fvec, and their norms.

DO  j = 1, n
  x(j) = wa2(j)
  wa2(j) = diag(j)*x(j)
END DO
fvec(1:m) = wa4(1:m)
xnorm = enorm(n,wa2)
fnorm = fnorm1
iter = iter + 1

!           tests for convergence.

290 IF (ABS(actred) <= ftol .AND. prered <= ftol .AND. p5*ratio <= one) info = 1
IF (delta <= xtol*xnorm) info = 2
IF (ABS(actred) <= ftol .AND. prered <= ftol  &
    .AND. p5*ratio <= one .AND. info == 2) info = 3
IF (info /= 0) GO TO 300

!           tests for termination and stringent tolerances.

IF (nfev >= maxfev) info = 5
IF (ABS(actred) <= epsmch .AND. prered <= epsmch  &
    .AND. p5*ratio <= one) info = 6
IF (delta <= epsmch*xnorm) info = 7
IF (gnorm <= epsmch) info = 8
IF (info /= 0) GO TO 300

!           end of the inner loop. repeat if iteration unsuccessful.

IF (ratio < p0001) GO TO 200

!        end of the outer loop.

GO TO 30

!     termination, either normal or user imposed.

300 IF (iflag < 0) info = iflag
iflag = 0
IF (nprint > 0) CALL fcn(m, n, x, fvec, fjac, iflag)
RETURN

!     last card of subroutine lmder.

END SUBROUTINE lmder



SUBROUTINE lmpar(n, r, ipvt, diag, qtb, delta, par, x, sdiag)
 
! Code converted using TO_F90 by Alan Miller
! Date: 1999-12-09  Time: 12:46:12

! N.B. Arguments LDR, WA1 & WA2 have been removed.

implicit none

INTEGER, INTENT(IN)        :: n
REAL (dp), INTENT(IN OUT)  :: r(:,:)
INTEGER, INTENT(IN)        :: ipvt(:)
REAL (dp), INTENT(IN)      :: diag(:)
REAL (dp), INTENT(IN)      :: qtb(:)
REAL (dp), INTENT(IN)      :: delta
REAL (dp), INTENT(OUT)     :: par  
REAL (dp), INTENT(OUT)     :: x(:)
REAL (dp), INTENT(OUT)     :: sdiag(:)

!  **********

!  subroutine lmpar

!  Given an m by n matrix a, an n by n nonsingular diagonal matrix d,
!  an m-vector b, and a positive number delta, the problem is to determine a
!  value for the parameter par such that if x solves the system

!        a*x = b ,     sqrt(par)*d*x = 0 ,

!  in the least squares sense, and dxnorm is the euclidean
!  norm of d*x, then either par is zero and

!        (dxnorm-delta) <= 0.1*delta ,

!  or par is positive and

!        abs(dxnorm-delta) <= 0.1*delta .

!  This subroutine completes the solution of the problem if it is provided
!  with the necessary information from the r factorization, with column
!  qpivoting, of a.  That is, if a*p = q*r, where p is a permutation matrix,
!  q has orthogonal columns, and r is an upper triangular matrix with diagonal
!  elements of nonincreasing magnitude, then lmpar expects the full upper
!  triangle of r, the permutation matrix p, and the first n components of
!  (q transpose)*b.
!  On output lmpar also provides an upper triangular matrix s such that

!         t   t                   t
!        p *(a *a + par*d*d)*p = s *s .

!  s is employed within lmpar and may be of separate interest.

!  Only a few iterations are generally needed for convergence of the algorithm.
!  If, however, the limit of 10 iterations is reached, then the output par
!  will contain the best value obtained so far.

!  the subroutine statement is

!    subroutine lmpar(n,r,ldr,ipvt,diag,qtb,delta,par,x,sdiag, wa1,wa2)

!  where

!    n is a positive integer input variable set to the order of r.

!    r is an n by n array. on input the full upper triangle
!      must contain the full upper triangle of the matrix r.
!      On output the full upper triangle is unaltered, and the
!      strict lower triangle contains the strict upper triangle
!      (transposed) of the upper triangular matrix s.

!    ldr is a positive integer input variable not less than n
!      which specifies the leading dimension of the array r.

!    ipvt is an integer input array of length n which defines the
!      permutation matrix p such that a*p = q*r. column j of p
!      is column ipvt(j) of the identity matrix.

!    diag is an input array of length n which must contain the
!      diagonal elements of the matrix d.

!    qtb is an input array of length n which must contain the first
!      n elements of the vector (q transpose)*b.

!    delta is a positive input variable which specifies an upper
!      bound on the euclidean norm of d*x.

!    par is a nonnegative variable. on input par contains an
!      initial estimate of the levenberg-marquardt parameter.
!      on output par contains the final estimate.

!    x is an output array of length n which contains the least
!      squares solution of the system a*x = b, sqrt(par)*d*x = 0,
!      for the output par.

!    sdiag is an output array of length n which contains the
!      diagonal elements of the upper triangular matrix s.

!    wa1 and wa2 are work arrays of length n.

!  subprograms called

!    minpack-supplied ... dpmpar,enorm,qrsolv

!    fortran-supplied ... ABS,MAX,MIN,SQRT

!  argonne national laboratory. minpack project. march 1980.
!  burton s. garbow, kenneth e. hillstrom, jorge j. more

!  **********
INTEGER   :: iter, j, jm1, jp1, k, l, nsing
REAL (dp) :: dxnorm, dwarf, fp, gnorm, parc, parl, paru, sum, temp
REAL (dp) :: wa1(n), wa2(n)
REAL (dp), PARAMETER :: p1 = 0.1_dp, p001 = 0.001_dp, zero = 0.0_dp

!     dwarf is the smallest positive magnitude.

dwarf = TINY(zero)

!     compute and store in x the gauss-newton direction. if the
!     jacobian is rank-deficient, obtain a least squares solution.

par = 0d0  ! must be initialised before its first use
nsing = n
DO  j = 1, n
  wa1(j) = qtb(j)
  IF (r(j,j) == zero .AND. nsing == n) nsing = j - 1
  IF (nsing < n) wa1(j) = zero
END DO

DO  k = 1, nsing
  j = nsing - k + 1
  wa1(j) = wa1(j)/r(j,j)
  temp = wa1(j)
  jm1 = j - 1
  wa1(1:jm1) = wa1(1:jm1) - r(1:jm1,j)*temp
END DO

DO  j = 1, n
  l = ipvt(j)
  x(l) = wa1(j)
END DO

!     initialize the iteration counter.
!     evaluate the function at the origin, and test
!     for acceptance of the gauss-newton direction.

iter = 0
wa2(1:n) = diag(1:n)*x(1:n)
dxnorm = enorm(n, wa2)
fp = dxnorm - delta
IF (fp <= p1*delta) GO TO 220

!     if the jacobian is not rank deficient, the newton
!     step provides a lower bound, parl, for the zero of
!     the function.  Otherwise set this bound to zero.

parl = zero
IF (nsing < n) GO TO 120
DO  j = 1, n
  l = ipvt(j)
  wa1(j) = diag(l)*(wa2(l)/dxnorm)
END DO
DO  j = 1, n
  sum = DOT_PRODUCT( r(1:j-1,j), wa1(1:j-1) )
  wa1(j) = (wa1(j) - sum)/r(j,j)
END DO
temp = enorm(n,wa1)
parl = ((fp/delta)/temp)/temp

!     calculate an upper bound, paru, for the zero of the function.

120 DO  j = 1, n
  sum = DOT_PRODUCT( r(1:j,j), qtb(1:j) )
  l = ipvt(j)
  wa1(j) = sum/diag(l)
END DO
gnorm = enorm(n,wa1)
paru = gnorm/delta
IF (paru == zero) paru = dwarf/MIN(delta,p1)

!     if the input par lies outside of the interval (parl,paru),
!     set par to the closer endpoint.

par = MAX(par,parl)
par = MIN(par,paru)
IF (par == zero) par = gnorm/dxnorm

!     beginning of an iteration.

150 iter = iter + 1

!        evaluate the function at the current value of par.

IF (par == zero) par = MAX(dwarf, p001*paru)
temp = SQRT(par)
wa1(1:n) = temp*diag(1:n)
CALL qrsolv(n, r, ipvt, wa1, qtb, x, sdiag)
wa2(1:n) = diag(1:n)*x(1:n)
dxnorm = enorm(n, wa2)
temp = fp
fp = dxnorm - delta

!        if the function is small enough, accept the current value
!        of par. also test for the exceptional cases where parl
!        is zero or the number of iterations has reached 10.

IF (ABS(fp) <= p1*delta .OR. parl == zero .AND. fp <= temp  &
    .AND. temp < zero .OR. iter == 10) GO TO 220

!        compute the newton correction.

DO  j = 1, n
  l = ipvt(j)
  wa1(j) = diag(l)*(wa2(l)/dxnorm)
END DO
DO  j = 1, n
  wa1(j) = wa1(j)/sdiag(j)
  temp = wa1(j)
  jp1 = j + 1
  wa1(jp1:n) = wa1(jp1:n) - r(jp1:n,j)*temp
END DO
temp = enorm(n,wa1)
parc = ((fp/delta)/temp)/temp

!        depending on the sign of the function, update parl or paru.

IF (fp > zero) parl = MAX(parl,par)
IF (fp < zero) paru = MIN(paru,par)

!        compute an improved estimate for par.

par = MAX(parl, par+parc)

!        end of an iteration.

GO TO 150

!     termination.

220 IF (iter == 0) par = zero
RETURN

!     last card of subroutine lmpar.

END SUBROUTINE lmpar



SUBROUTINE qrfac(m, n, a, pivot, ipvt, rdiag, acnorm)
 
! Code converted using TO_F90 by Alan Miller
! Date: 1999-12-09  Time: 12:46:17

! N.B. Arguments LDA, LIPVT & WA have been removed.

INTEGER, INTENT(IN)        :: m
INTEGER, INTENT(IN)        :: n
REAL (dp), INTENT(IN OUT)  :: a(:,:)
LOGICAL, INTENT(IN)        :: pivot
INTEGER, INTENT(OUT)       :: ipvt(:)
REAL (dp), INTENT(OUT)     :: rdiag(:)
REAL (dp), INTENT(OUT)     :: acnorm(:)

!  **********

!  subroutine qrfac

!  This subroutine uses Householder transformations with column pivoting
!  (optional) to compute a qr factorization of the m by n matrix a.
!  That is, qrfac determines an orthogonal matrix q, a permutation matrix p,
!  and an upper trapezoidal matrix r with diagonal elements of nonincreasing
!  magnitude, such that a*p = q*r.  The householder transformation for
!  column k, k = 1,2,...,min(m,n), is of the form

!                        t
!        i - (1/u(k))*u*u

!  where u has zeros in the first k-1 positions.  The form of this
!  transformation and the method of pivoting first appeared in the
!  corresponding linpack subroutine.

!  the subroutine statement is

!    subroutine qrfac(m, n, a, lda, pivot, ipvt, lipvt, rdiag, acnorm, wa)

! N.B. 3 of these arguments have been omitted in this version.

!  where

!    m is a positive integer input variable set to the number of rows of a.

!    n is a positive integer input variable set to the number of columns of a.

!    a is an m by n array.  On input a contains the matrix for
!      which the qr factorization is to be computed.  On output
!      the strict upper trapezoidal part of a contains the strict
!      upper trapezoidal part of r, and the lower trapezoidal
!      part of a contains a factored form of q (the non-trivial
!      elements of the u vectors described above).

!    lda is a positive integer input variable not less than m
!      which specifies the leading dimension of the array a.

!    pivot is a logical input variable.  If pivot is set true,
!      then column pivoting is enforced.  If pivot is set false,
!      then no column pivoting is done.

!    ipvt is an integer output array of length lipvt.  ipvt
!      defines the permutation matrix p such that a*p = q*r.
!      Column j of p is column ipvt(j) of the identity matrix.
!      If pivot is false, ipvt is not referenced.

!    lipvt is a positive integer input variable.  If pivot is false,
!      then lipvt may be as small as 1.  If pivot is true, then
!      lipvt must be at least n.

!    rdiag is an output array of length n which contains the
!      diagonal elements of r.

!    acnorm is an output array of length n which contains the norms of the
!      corresponding columns of the input matrix a.
!      If this information is not needed, then acnorm can coincide with rdiag.

!    wa is a work array of length n.  If pivot is false, then wa
!      can coincide with rdiag.

!  subprograms called

!    minpack-supplied ... dpmpar,enorm

!    fortran-supplied ... MAX,SQRT,MIN

!  argonne national laboratory. minpack project. march 1980.
!  burton s. garbow, kenneth e. hillstrom, jorge j. more

!  **********
INTEGER   :: i, j, jp1, k, kmax, minmn
REAL (dp) :: ajnorm, epsmch, sum, temp, wa(n)
REAL (dp), PARAMETER :: one = 1.0_dp, p05 = 0.05_dp, zero = 0.0_dp

!     epsmch is the machine precision.

epsmch = EPSILON(zero)

!     compute the initial column norms and initialize several arrays.

DO  j = 1, n
  acnorm(j) = enorm(m,a(1:,j))
  rdiag(j) = acnorm(j)
  wa(j) = rdiag(j)
  IF (pivot) ipvt(j) = j
END DO

!     Reduce a to r with Householder transformations.

minmn = MIN(m,n)
DO  j = 1, minmn
  IF (.NOT.pivot) GO TO 40
  
!        Bring the column of largest norm into the pivot position.
  
  kmax = j
  DO  k = j, n
    IF (rdiag(k) > rdiag(kmax)) kmax = k
  END DO
  IF (kmax == j) GO TO 40
  DO  i = 1, m
    temp = a(i,j)
    a(i,j) = a(i,kmax)
    a(i,kmax) = temp
  END DO
  rdiag(kmax) = rdiag(j)
  wa(kmax) = wa(j)
  k = ipvt(j)
  ipvt(j) = ipvt(kmax)
  ipvt(kmax) = k
  
!     Compute the Householder transformation to reduce the
!     j-th column of a to a multiple of the j-th unit vector.
  
  40 ajnorm = enorm(m-j+1, a(j:,j))
  IF (ajnorm == zero) CYCLE
  IF (a(j,j) < zero) ajnorm = -ajnorm
  a(j:m,j) = a(j:m,j)/ajnorm
  a(j,j) = a(j,j) + one
  
!     Apply the transformation to the remaining columns and update the norms.
  
  jp1 = j + 1
  DO  k = jp1, n
    sum = DOT_PRODUCT( a(j:m,j), a(j:m,k) )
    temp = sum/a(j,j)
    a(j:m,k) = a(j:m,k) - temp*a(j:m,j)
    IF (.NOT.pivot .OR. rdiag(k) == zero) CYCLE
    temp = a(j,k)/rdiag(k)
    rdiag(k) = rdiag(k)*SQRT(MAX(zero, one-temp**2))
    IF (p05*(rdiag(k)/wa(k))**2 > epsmch) CYCLE
    rdiag(k) = enorm(m-j, a(jp1:,k))
    wa(k) = rdiag(k)
  END DO
  rdiag(j) = -ajnorm
END DO
RETURN

!     last card of subroutine qrfac.

END SUBROUTINE qrfac



SUBROUTINE qrsolv(n, r, ipvt, diag, qtb, x, sdiag)
 
! N.B. Arguments LDR & WA have been removed.

INTEGER, INTENT(IN)        :: n
REAL (dp), INTENT(IN OUT)  :: r(:,:)
INTEGER, INTENT(IN)        :: ipvt(:)
REAL (dp), INTENT(IN)      :: diag(:)
REAL (dp), INTENT(IN)      :: qtb(:)
REAL (dp), INTENT(OUT)     :: x(:)
REAL (dp), INTENT(OUT)     :: sdiag(:)

!  **********

!  subroutine qrsolv

!  Given an m by n matrix a, an n by n diagonal matrix d, and an m-vector b,
!  the problem is to determine an x which solves the system

!        a*x = b ,     d*x = 0 ,

!  in the least squares sense.

!  This subroutine completes the solution of the problem if it is provided
!  with the necessary information from the qr factorization, with column
!  pivoting, of a.  That is, if a*p = q*r, where p is a permutation matrix,
!  q has orthogonal columns, and r is an upper triangular matrix with diagonal
!  elements of nonincreasing magnitude, then qrsolv expects the full upper
!  triangle of r, the permutation matrix p, and the first n components of
!  (q transpose)*b.  The system a*x = b, d*x = 0, is then equivalent to

!               t       t
!        r*z = q *b ,  p *d*p*z = 0 ,

!  where x = p*z. if this system does not have full rank,
!  then a least squares solution is obtained.  On output qrsolv
!  also provides an upper triangular matrix s such that

!         t   t               t
!        p *(a *a + d*d)*p = s *s .

!  s is computed within qrsolv and may be of separate interest.

!  the subroutine statement is

!    subroutine qrsolv(n, r, ldr, ipvt, diag, qtb, x, sdiag, wa)

! N.B. Arguments LDR and WA have been removed in this version.

!  where

!    n is a positive integer input variable set to the order of r.

!    r is an n by n array.  On input the full upper triangle must contain
!      the full upper triangle of the matrix r.
!      On output the full upper triangle is unaltered, and the strict lower
!      triangle contains the strict upper triangle (transposed) of the
!      upper triangular matrix s.

!    ldr is a positive integer input variable not less than n
!      which specifies the leading dimension of the array r.

!    ipvt is an integer input array of length n which defines the
!      permutation matrix p such that a*p = q*r.  Column j of p
!      is column ipvt(j) of the identity matrix.

!    diag is an input array of length n which must contain the
!      diagonal elements of the matrix d.

!    qtb is an input array of length n which must contain the first
!      n elements of the vector (q transpose)*b.

!    x is an output array of length n which contains the least
!      squares solution of the system a*x = b, d*x = 0.

!    sdiag is an output array of length n which contains the
!      diagonal elements of the upper triangular matrix s.

!    wa is a work array of length n.

!  subprograms called

!    fortran-supplied ... ABS,SQRT

!  argonne national laboratory. minpack project. march 1980.
!  burton s. garbow, kenneth e. hillstrom, jorge j. more

!  **********
INTEGER   :: i, j, k, kp1, l, nsing
REAL (dp) :: COS, cotan, qtbpj, SIN, sum, TAN, temp, wa(n)
REAL (dp), PARAMETER :: p5 = 0.5_dp, p25 = 0.25_dp, zero = 0.0_dp

!     Copy r and (q transpose)*b to preserve input and initialize s.
!     In particular, save the diagonal elements of r in x.

DO  j = 1, n
  r(j:n,j) = r(j,j:n)
  x(j) = r(j,j)
  wa(j) = qtb(j)
END DO

!     Eliminate the diagonal matrix d using a givens rotation.

DO  j = 1, n
  
!        Prepare the row of d to be eliminated, locating the
!        diagonal element using p from the qr factorization.
  
  l = ipvt(j)
  IF (diag(l) == zero) CYCLE
  sdiag(j:n) = zero
  sdiag(j) = diag(l)
  
!     The transformations to eliminate the row of d modify only a single
!     element of (q transpose)*b beyond the first n, which is initially zero.
  
  qtbpj = zero
  DO  k = j, n
    
!        Determine a givens rotation which eliminates the
!        appropriate element in the current row of d.
    
    IF (sdiag(k) == zero) CYCLE
    IF (ABS(r(k,k)) < ABS(sdiag(k))) THEN
      cotan = r(k,k)/sdiag(k)
      SIN = p5/SQRT(p25 + p25*cotan**2)
      COS = SIN*cotan
    ELSE
      TAN = sdiag(k)/r(k,k)
      COS = p5/SQRT(p25 + p25*TAN**2)
      SIN = COS*TAN
    END IF
    
!        Compute the modified diagonal element of r and
!        the modified element of ((q transpose)*b,0).
    
    r(k,k) = COS*r(k,k) + SIN*sdiag(k)
    temp = COS*wa(k) + SIN*qtbpj
    qtbpj = -SIN*wa(k) + COS*qtbpj
    wa(k) = temp
    
!        Accumulate the tranformation in the row of s.
    
    kp1 = k + 1
    DO  i = kp1, n
      temp = COS*r(i,k) + SIN*sdiag(i)
      sdiag(i) = -SIN*r(i,k) + COS*sdiag(i)
      r(i,k) = temp
    END DO
  END DO
  
!     Store the diagonal element of s and restore
!     the corresponding diagonal element of r.
  
  sdiag(j) = r(j,j)
  r(j,j) = x(j)
END DO

!     Solve the triangular system for z.  If the system is singular,
!     then obtain a least squares solution.

nsing = n
DO  j = 1, n
  IF (sdiag(j) == zero .AND. nsing == n) nsing = j - 1
  IF (nsing < n) wa(j) = zero
END DO

DO  k = 1, nsing
  j = nsing - k + 1
  sum = DOT_PRODUCT( r(j+1:nsing,j), wa(j+1:nsing) )
  wa(j) = (wa(j) - sum)/sdiag(j)
END DO

!     Permute the components of z back to components of x.

DO  j = 1, n
  l = ipvt(j)
  x(l) = wa(j)
END DO
RETURN

!     last card of subroutine qrsolv.

END SUBROUTINE qrsolv



FUNCTION enorm(n,x) RESULT(fn_val)
 
! Code converted using TO_F90 by Alan Miller
! Date: 1999-12-09  Time: 12:45:34

INTEGER, INTENT(IN)    :: n
REAL (dp), INTENT(IN)  :: x(:)
REAL (dp)              :: fn_val

!  **********

!  function enorm

!  given an n-vector x, this function calculates the euclidean norm of x.

!  the euclidean norm is computed by accumulating the sum of squares in
!  three different sums.  The sums of squares for the small and large
!  components are scaled so that no overflows occur.  Non-destructive
!  underflows are permitted.  Underflows and overflows do not occur in the
!  computation of the unscaled sum of squares for the intermediate
!  components.  The definitions of small, intermediate and large components
!  depend on two constants, rdwarf and rgiant.  The main restrictions on
!  these constants are that rdwarf**2 not underflow and rgiant**2 not
!  overflow.  The constants given here are suitable for every known computer.

!  the function statement is

!    REAL (dp) function enorm(n,x)

!  where

!    n is a positive integer input variable.

!    x is an input array of length n.

!  subprograms called

!    fortran-supplied ... ABS,SQRT

!  argonne national laboratory. minpack project. march 1980.
!  burton s. garbow, kenneth e. hillstrom, jorge j. more

!  **********
INTEGER   :: i
REAL (dp) :: agiant, floatn, s1, s2, s3, xabs, x1max, x3max
REAL (dp), PARAMETER :: one = 1.0_dp, zero = 0.0_dp, rdwarf = 3.834E-20_dp,  &
                        rgiant = 1.304E+19_dp

s1 = zero
s2 = zero
s3 = zero
x1max = zero
x3max = zero
floatn = n
agiant = rgiant/floatn
DO  i = 1, n
  xabs = ABS(x(i))
  IF (xabs > rdwarf .AND. xabs < agiant) GO TO 70
  IF (xabs <= rdwarf) GO TO 30
  
!              sum for large components.
  
  IF (xabs <= x1max) GO TO 10
  s1 = one + s1*(x1max/xabs)**2
  x1max = xabs
  GO TO 20

  10 s1 = s1 + (xabs/x1max)**2

  20 GO TO 60
  
!              sum for small components.
  
  30 IF (xabs <= x3max) GO TO 40
  s3 = one + s3*(x3max/xabs)**2
  x3max = xabs
  GO TO 60

  40 IF (xabs /= zero) s3 = s3 + (xabs/x3max)**2

  60 CYCLE
  
!           sum for intermediate components.
  
  70 s2 = s2 + xabs**2
END DO

!     calculation of norm.

IF (s1 == zero) GO TO 100
fn_val = x1max*SQRT(s1 + (s2/x1max)/x1max)
GO TO 120

100 IF (s2 == zero) GO TO 110
IF (s2 >= x3max) fn_val = SQRT(s2*(one + (x3max/s2)*(x3max*s3)))
IF (s2 < x3max) fn_val = SQRT(x3max*((s2/x3max) + (x3max*s3)))
GO TO 120

110 fn_val = x3max*SQRT(s3)

120 RETURN

!     last card of function enorm.

END FUNCTION enorm



SUBROUTINE fdjac2(fcn, m, n, x, fvec, fjac, iflag, epsfcn)
 
! Code converted using TO_F90 by Alan Miller
! Date: 1999-12-09  Time: 12:45:44

! N.B. Arguments LDFJAC & WA have been removed.

INTEGER, INTENT(IN)        :: m
INTEGER, INTENT(IN)        :: n
REAL (dp), INTENT(IN OUT)  :: x(n)
REAL (dp), INTENT(IN)      :: fvec(m)
REAL (dp), INTENT(OUT)     :: fjac(:,:)    ! fjac(ldfjac,n)
INTEGER, INTENT(IN OUT)    :: iflag
REAL (dp), INTENT(IN)      :: epsfcn

INTERFACE
  SUBROUTINE fcn(m, n, x, fvec, iflag)
    IMPLICIT NONE
    INTEGER, PARAMETER :: dp = SELECTED_REAL_KIND(12, 60)
    INTEGER, INTENT(IN)        :: m, n
    REAL (dp), INTENT(IN)      :: x(:)
    REAL (dp), INTENT(IN OUT)  :: fvec(:)
    INTEGER, INTENT(IN OUT)    :: iflag
  END SUBROUTINE fcn
END INTERFACE

!  **********

!  subroutine fdjac2

!  this subroutine computes a forward-difference approximation
!  to the m by n jacobian matrix associated with a specified
!  problem of m functions in n variables.

!  the subroutine statement is

!    subroutine fdjac2(fcn,m,n,x,fvec,fjac,ldfjac,iflag,epsfcn,wa)

!  where

!    fcn is the name of the user-supplied subroutine which calculates the
!      functions.  fcn must be declared in an external statement in the user
!      calling program, and should be written as follows.

!      subroutine fcn(m,n,x,fvec,iflag)
!      integer m,n,iflag
!      REAL (dp) x(n),fvec(m)
!      ----------
!      calculate the functions at x and
!      return this vector in fvec.
!      ----------
!      return
!      end

!      the value of iflag should not be changed by fcn unless
!      the user wants to terminate execution of fdjac2.
!      in this case set iflag to a negative integer.

!    m is a positive integer input variable set to the number of functions.

!    n is a positive integer input variable set to the number of variables.
!      n must not exceed m.

!    x is an input array of length n.

!    fvec is an input array of length m which must contain the
!      functions evaluated at x.

!    fjac is an output m by n array which contains the
!      approximation to the jacobian matrix evaluated at x.

!    ldfjac is a positive integer input variable not less than m
!      which specifies the leading dimension of the array fjac.

!    iflag is an integer variable which can be used to terminate
!      the execution of fdjac2.  see description of fcn.

!    epsfcn is an input variable used in determining a suitable step length
!      for the forward-difference approximation.  This approximation assumes
!      that the relative errors in the functions are of the order of epsfcn.
!      If epsfcn is less than the machine precision, it is assumed that the
!      relative errors in the functions are of the order of the machine
!      precision.

!    wa is a work array of length m.

!  subprograms called

!    user-supplied ...... fcn

!    minpack-supplied ... dpmpar

!    fortran-supplied ... ABS,MAX,SQRT

!  argonne national laboratory. minpack project. march 1980.
!  burton s. garbow, kenneth e. hillstrom, jorge j. more

!  **********
INTEGER   :: j
REAL (dp) :: eps, epsmch, h, temp, wa(m)
REAL (dp), PARAMETER :: zero = 0.0_dp

!     epsmch is the machine precision.

epsmch = EPSILON(zero)

eps = SQRT(MAX(epsfcn, epsmch))
DO  j = 1, n
  temp = x(j)
  h = eps*ABS(temp)
  IF (h == zero) h = eps
  x(j) = temp + h
  CALL fcn(m, n, x, wa, iflag)
  IF (iflag < 0) EXIT
  x(j) = temp
  fjac(1:m,j) = (wa(1:m) - fvec(1:m))/h
END DO

RETURN

!     last card of subroutine fdjac2.

END SUBROUTINE fdjac2


END MODULE Levenberg_Marquardt


!********************
   module famouslib
!********************

!***********************************************************************************
! Modul FAMOUSLIB is the main fortan module of the FAMOUS software.                !
! Make sure that you have read the readme file before running the program          !             !
! on your favorite data. If you want to learn how FAMOUS works, it might           !
! be adivsable that you start with the simulation mode by using the driver         !
! famous_driver_simul.f90 instead of the standard famous_driver.f90.               !
!                                                                                  !
! This software is offered without warranty of any kind, either expressed          !
! or implied.  The author would appreciate, however, any reports of bugs           !
! or other difficulties that may be encountered.                                   !
!***********************************************************************************
! 

!   This section initializes global parameters and arrays default values.
!   Note that this Fortran-90 version completely dispenses with common blocks.
!   Global variables and parameters in this module can be accessed in any user
!   program with a USE FAMOUSLIB statement. 


   integer,       parameter :: dp        = selected_real_kind(12, 60)
   real(kind=dp), parameter :: pi        = 3.141592653589793238462643d0
   real(kind=dp), parameter :: deupi     = 6.283185307179586476925286d0
   real(kind=dp), parameter :: degrad    = pi/180d0                       !  1.74532925199433d-2   :: radians to degree
   real(kind=dp), parameter :: raddeg    = 180d0/pi                       !  57.2957795130823d0    :: degree to radian
!
!  global variables
!

   integer                 :: npts, numfreq
   integer                 :: maxdeg
   real(dp), allocatable   :: xx(:), yy(:), zz(:)  ! data  yy = values at xx, zz: xx rescaled and centred.
   integer,  allocatable   :: idegf(:)             ! degree of the time polynomial for each line found
   real(dp)                :: threshold            ! threshold of the s/n of a line below wich the line is rejected as non significant (typical ~ 3)
   real(dp)                :: toffset              ! time shift applied to centre the original data when no request are sent by the user in the setting
   real(dp)                :: freqres              ! frequency resolution achievable in the frequency search
   real(dp), allocatable   :: sig_rel_f(:)         ! sig(f)/f in the solution
   logical                 :: flnormal             ! flag for the period search : true : more energy in the fundamental that in any harmonics.
contains
!*********************************************************************************
      subroutine read_signal(iunit,npts,ncolx,ncoly,x,y)
!*********************************************************************************
!
!     Read on an external unit, column number ncolx stored in x,
!     and column number ncoly stored in y.
!     The external unit is assumed to be open for reading
!     
!*AUT     F. Mignard   
!*VER     Version 1, December 1999
!*VER     Modified Jan 2000 by G. Metris to extract xx and yy from any column
!         F90 version : Jan 2005
!         Modified October 2005 : time data in input file does not need to be sorted.
!                                 - already in increasing order :: no change
!                                 - if in decreasing order      :: time data  put in increasing order
!                                 - if not monotonous           :: data arrays sorted 
!
!
!*INPUT   
!           IUNIT   :  Specifies the external unit
!           NPTS    :  number of data points
!           NCOLX   :  Specifies the column containing vector X (time data)   
!           NCOLY   :  Specifies the column containing vector Y (signal data)
!     
!*OUTPUT
!           X[npts] : Array with the independant variable (nominally :time)
!           Y[npts] : Array with the data points y_i
!
!*EXTERNAL
!           no external called
!********************************************************************************
! 
      implicit  none

      integer,       intent(in)   :: iunit, npts, ncolx, ncoly
      real(kind=dp), intent(out)  :: x(*), y(*)
       
      real(kind=dp)               :: xxx, yyy
      real(kind=dp)               :: xxx_1, xxx_2
      integer                     :: k, i

      logical                     :: flsort =.false.

      integer                     :: ind(npts)


      read(iunit,*)   (xxx_1,i=1,ncolx)  ! to determine how the data are ordered
      read(iunit,*)   (xxx_2,i=1,ncolx)
      backspace(iunit)
      backspace(iunit)

!
!     the two blocks below assume that in practice the time variable read in ncolx is
!     likely to be very often either in increasing or decreasing order, rather than
!     less regular. As the array with the independant variable must be in increasing order
!     a sorting is applied only if the time data are found with at least one inversion.
!
      if(xxx_2 > xxx_1) then   ! sorted in increasing order of the independant variable

         read(iunit,*,end=100) (xxx,i=1,ncolx), (yyy,i=1,ncoly-ncolx)  ! read the first record
         x(1) = xxx 
         y(1) = yyy  
      
         do k = 2, npts
            read(iunit,*,end=100) (xxx,i=1,ncolx), (yyy,i=1,ncoly-ncolx)
            x(k) = xxx 
            y(k) = yyy  
            if(x(k) < x(k-1)) then
               flsort =.true.         ! two points found not in increasing order
            endif
         enddo 
 
     else                             ! sorted in decreasing order of the independant variable

         read(iunit,*,end=100) (xxx,i=1,ncolx), (yyy,i=1,ncoly-ncolx) ! read the first record 
         x(npts) = xxx 
         y(npts) = yyy  

         do k = 2, npts 
            read(iunit,*,end=100) (xxx,i=1,ncolx), (yyy,i=1,ncoly-ncolx)
            x(npts+1-k) = xxx         ! x and y are assigned from the bottom 
            y(npts+1-k) = yyy  
            if(x(npts+1-k) > x(npts+2-k)) then
               flsort =.true.         ! two points found not in decreasing order
            endif
         enddo 
      endif
!
!     sort the data if the time variable is neither in increasing nor  in decreasing order
!
      if(flsort) then
         call quicksort(npts,x,ind)    !sort the array x
         call permut(npts, ind, y)     !apply the reodering to y
      endif 

 100  continue
      if(k /= (npts+1)) then  ! less records than expected
         write(*,*) '************************************************'
         write(*,*) '    anomaly encounters while reading the input file '
         write(*,*)  npts , ' records were expected ; only ' , k-1, ' found'
         write(*,*) '    check the input file  structure '
         write(*,*) '        ***  PROGRAM STOPPED ***'
         write(*,*) '************************************************'
         stop
      endif
      return
      end  subroutine read_signal
!***********************************************************************************
      subroutine writepower(iunit,npts,x,y)
!***********************************************************************************
!
!     Write the data y(x(k)) on the unit IUNIT in ascii
!     The external unit is assumed to be open for reading
!     It is closed after all data are read.
!     
!*AUT     F. Mignard   
!*VER     Version 1, December 1999
!
!*INPUT   
!           IUNIT   :  Specifies the external unit
!           NPTS    : number of data points
!           X[npts] : Array with the independant variable (nominally : time)
!           Y[npts] : Array with the data points y_i
!
!*EXTERNAL
!           no external called
!***********************************************************************************
! 

      implicit  none

      integer,       intent(in)   :: iunit, npts
      real(kind=dp), intent(in)   :: x(*), y(*)
       
      integer                     :: k

      do k =1, npts
         write(iunit,100) x(k), y(k)
      enddo
      close(iunit)

100   format(e16.8,e16.8)

      return
      end  subroutine writepower
!***********************************************************************************
      subroutine waves(npts,x,y,flunif,fbeg,nfreq,stepf,xfreq,power)
!***********************************************************************************
!
!     Computation of the periodogram of the signal Y(k) sampled at t_k=X(k)
!     over NPTS times with frequency regularly sampled.
!     This routines is an optimisation of the previous versions of waves
!     which uses recurrence relations to compute the trigonometric lines
!     using the regular sampling in the frequency space. 
!     It has the same call list as the previous routines waves.
!     
!*AUT     F. Mignard   
!*VER     Version 1, March 2005
!         Optimisation fot the windows : July 2005 
!
!         CALLING SEQUENCE :
!         CALL WAVES(NPTS,X,Y,FLUNIF,FBEG,NFREQ,STEPF,XFREQ,POWER)
!
!*INPUT   
!           NPTS    : number of data points
!           X[npts] : Array with the independant variable (nominally : time)
!           Y[npts] : Array with the data points y_i
!           flunif  : .true. is regular sampling,  .false. otherwise
!           FBEG    : lower frequency for the periodograms 
!           NFREQ   : number of frequencies sampled
!           STEPF   : stepsize in the frequency domain
!*OUTPUT
!           XFREQ() : array (nfreq) of nfreq fequencies
!           POWER() : array (nfreq) of the sqrt(power) at XFREQ(k)
! 
!*EXTERNAL
!           getmaxmin, frequence, frequence_unif
! 
!***********************************************************************************
      implicit none

      integer,        intent(in)         :: npts, nfreq
      real(kind=dp),  intent(in)         :: fbeg, stepf
      real(kind=dp),  intent(in)         :: x(npts), y(npts)
      real(kind=dp),  intent(out)        :: xfreq(*), power(*)
 
      logical,        intent(in)         :: flunif
  
      real(kind=dp)                      :: xmax, xmin, period
      real(kind=dp)                      :: aa,bb,cc,qq,sumy,sumww
      
      real(kind=dp),  dimension(npts)    :: tc_a,ts_a, tc_b, ts_b, window
      real(kind=dp)                      :: cal, sal, cbl, sbl
      integer                            :: imax, imin, k,ista
      logical                            :: flwindow

      call getmaxmin(npts,x, xmax, xmin, imax, imin)


      if(flunif) then                                       ! regular time sampling
         tc_a(1)    = cos(deupi*fbeg*x(1))
         ts_a(1)    = sin(deupi*fbeg*x(1))
         cal        = cos(deupi*fbeg*(x(2)-x(1)))           ! cosines of the step
         sal        = sin(deupi*fbeg*(x(2)-x(1)))           ! sines of the step

         tc_b(1)    = cos(deupi*stepf*x(1))
         ts_b(1)    = sin(deupi*stepf*x(1))

         cbl        = cos(deupi*stepf*(x(2)-x(1)))          ! cosines of the step
         sbl        = sin(deupi*stepf*(x(2)-x(1)))          ! sines of the step

         window(1)  = 0d0
         flwindow = .true.
         do  k= 2, npts
            tc_a(k) = tc_a(k-1)*cal - ts_a(k-1)*sal         ! cos and sine by recurrence
            ts_a(k) = ts_a(k-1)*cal + tc_a(k-1)*sal
        
            tc_b(k) = tc_b(k-1)*cbl - ts_b(k-1)*sbl
            ts_b(k) = ts_b(k-1)*cbl + tc_b(k-1)*sbl
        
!            window(k)  =  0.5d0 - 0.5d0*cos(deupi/(xmax-xmin)*(x(k)-xmin))   !Tuckey window
            window(k)  =  1.0d0    !FM 05/11/05 PB with low frequencies 
        enddo

      else                                                  ! irregular time sampling
         flwindow = .false.     !no window 
         do  k= 1, npts
            tc_a(k) = cos(deupi*fbeg*x(k))
            ts_a(k) = sin(deupi*fbeg*x(k))
        
            tc_b(k) = cos(deupi*stepf*x(k))
            ts_b(k) = sin(deupi*stepf*x(k))
                   
            window(k)  =  1d0            ! change FM 04/07/05
         enddo
      endif
!
!     the following sums are used in FREQUENCE, but not recomputed later
!
      sumww = sum(window)                   ! = npts if no window
      sumy  = dot_product(window,y)

      do k = 1, nfreq                       !periodogram over nfreq frequencies
          xfreq(k) = fbeg+ (k-1)*stepf
          period = 1d0/xfreq(k)
          call frequence(npts,x,xmin,xmax,y,period,aa,bb,cc,qq,ista)
          power(k) = qq                    ! power = amplitude of a plain harmonic line
      enddo
      contains
!***********************************************************************************
      SUBROUTINE FREQUENCE(NOBS,X,XMIN,XMAX,Y,Period,AA,BB,CT,QQ,IERR)
!***********************************************************************************
!
!     Search with least-squares of a line a*cos(2pix/P) +b*sin(2pix/P) +c
!     in the data Y : (y1, y2, .., yn) sampled at (x1,x2, .., xn)
!     A  window may be used to dampen the sidelobes
!     The normal equations are solved exactly from analytical expressions
!
!     Results are strictly identical to a slightly different algorithm
!     given by S. Ferraz-Mello Ast.Jal 86, p.619,1981

! 
!*AUT     F. Mignard   
!*VER     Version 1, December 1999
!         F90 style : Dec 04
!         Trig lines with recurrence     : April 2005
!         Improved computation of power  : July  2005
!         New optimisation of windows    : July  2005
!
!
!*INPUT   
!           NOBS    : number of data points
!           X[nobs] : Array with the independent variable
!           XMIN    : Smallest value of X
!           XMAX    : Largest  value of X
!           Y[nobs] : Array with the data points y_i
!           Period  : Test  period in the same unit as X
!
!*OUTPUT
!           AA      : Amplitude of the cosine term
!           BB      : Amplitude of the sine   term
!           CT      : Constant term   (with respect to <Y>)
!           QQ      : SQRT of the power in the line
!           IERR    : Error status  : 0 : nominal fit  100: singularity encountered.
!                                                           no periodic signature found.
!
! 
!*EXTERNAL
!            no externals called
!***********************************************************************************
! 

      implicit  none

      integer      ,  intent(in)       :: nobs
      real(kind=dp),  intent(in)       :: x(*), y(nobs)
      real(kind=dp),  intent(in)       :: xmin, xmax, period

      integer,        intent(out)      :: ierr 

      real(kind=dp),  intent(out)      :: aa,bb,ct,qq
 
      real(kind=dp)                    :: sumc, sums
      real(kind=dp)                    :: sumcc,sumss,sumcs 
      real(kind=dp)                    :: sumcy,sumsy 
      real(kind=dp)                    :: yyy
      real(kind=dp)                    :: cc, ss, ccw, ssw, delta, ww
      real(kind=dp)                    :: tumcc,tumss,tumcs 
      real(kind=dp)                    :: tumcy,tumsy ,sd
      real(kind=dp)                    :: temp(nobs)
      integer                          :: l 

!
!     Various sums
!
      sumc =0
      sums =0
     
      sumcc=0
      sumcs=0

      sumcy=0
      sumsy=0



      ierr = 0     
      if(flwindow) then      !a window is applied to the data
         do  l  = 1, nobs

            yyy = y(l)

!            ww  = window(l)             ! computed in waves                 

            cc  =  tc_a(l)              !    "          "
            ss  =  ts_a(l)              !    "          "
         
!            ccw =  cc*ww               ! FM 05/11/05
!            ssw =  ss*ww

            ccw =  cc
            ssw =  ss
      
            sumc  = sumc  + ccw
            sums  = sums  + ssw

            sumcc = sumcc +  cc*ccw
            sumcs = sumcs +  cc*ssw

            sumcy = sumcy +  ccw*yyy
            sumsy = sumsy +  ssw*yyy

!
!  recurrence for the trig lines
!

            tc_a(l) = cc*tc_b(l) - ss*ts_b(l)
            ts_a(l) = ss*tc_b(l) + cc*ts_b(l)

         enddo
      else                     ! no window

         do  l  = 1, nobs

            yyy = y(l)

            cc  =  tc_a(l)              !  computed in waves and updated below
            ss  =  ts_a(l)              !    "          "            "     "
             
            sumc  = sumc  + cc
            sums  = sums  + ss

            sumcc = sumcc +  cc*cc
            sumcs = sumcs +  cc*ss

            sumcy = sumcy +  cc*yyy
            sumsy = sumsy +  ss*yyy

!
!  recurrence for the trig lines
!

            tc_a(l) = cc*tc_b(l) - ss*ts_b(l)
            ts_a(l) = ss*tc_b(l) + cc*ts_b(l)

         enddo

      endif
      sumss = sumww - sumcc             !from cos^2 + sin^2 =1
!
!      subnormal matrix for AA and BB
!      
      tumcc = sumcc - sumc*sumc/sumww
      tumss = sumss - sums*sums/sumww
      tumcs = sumcs - sumc*sums/sumww
      tumcy = sumcy - sumy*sumc/sumww
      tumsy = sumsy - sumy*sums/sumww

!
!     inverse of the determinant of the sub-normal matrix
!            
      delta = 1d0/(tumcc*tumss-tumcs*tumcs)
!
!     Coefficients aa and bb of the line
!
      aa = (tumss*tumcy-tumcs*tumsy)*delta
      bb = (tumcc*tumsy-tumcs*tumcy)*delta
      ct =  sumy/sumww-(sumc*aa + sums*bb)/sumww

!
!     Mean quadratic power and RMS of the data
!     X_t*(A_t*Y) in standard LSQR notations
!
      qq = aa*sumcy + bb*sumsy + ct*sumy
      if(qq > 0) then   !the  two expressions below are numerically identical
!         qq  = sqrt(2d0*((sumy**2/sumww) +aa*aa*tumcc +bb*bb*tumss+2.d0*aa*bb*tumcs)/sumww)
         qq =  sqrt(2d0*(abs(aa*sumcy + bb*sumsy + ct*sumy))/sumww)  !factor 2 to get the amplitude
      else
         ierr = 100
         qq   = 0.0d0
      endif

      return
      end  subroutine frequence

      end  subroutine waves
!***********************************************************************************
      subroutine getparam(npts,xx,iout,iprint,flauto,frbeg,frend,& 
                          flunif,xmin,xmax,width,nfreq,stepf,fbeg,fend)
!***********************************************************************************
!
!************************************************************************* 
!PURPOSE
!   Determination of the basic properties of the time sampling xx(:)
!   for the frequency analysis. Computation of the parameters for 
!   the frequency sampling.
!
!
!   F. Mignard OCA
!   Version 1 : October 2003
!
!
!*************************************************************************
!INPUT
!      npts     : number of data points
!      xx[npts] : Array with the independant variable (nominally : time)
!      iout     : output unit
!      iprint   : printing code for restricted (0) to extented (1)
!      flauto   : .true. min and max freq determined by the program  .false. : min and max freq provided as frbeg and frend)
!      frbeg    : lower frequency provided by the user if flauto = .false.
!      frend    : upper frequency provided by the user if flauto = .false.
!
!OUTPUT
!      flunif   : .true. : regular sampling found .false. : otherwise
!      xmin     : min(x(:))
!      xmax     : max(x(:))
!      width    : line width in the frequency domain (unit 1/(unit of x))
!      nfreq    : number of frequencies sampled in the frequency domain
!      stepf    : step of the frequency sampling (unit 1/(unit of x))
!      fbeg     : actual lower frequency found (= frbeg is flauto = .true.)
!      fend     : actual upper frequency found (= frend is flauto = .true.)
!
!************************************************************************* 
      implicit none

      real(kind=dp), intent(in)        :: xx(*)
      real(kind=dp), intent(in)        :: frbeg, frend
      integer      , intent(in)        :: npts, iout, iprint
      logical      , intent(in)        :: flauto

      real(kind=dp), intent(out)       :: xmin, xmax,width,stepf,fbeg,fend
      integer      , intent(out)       :: nfreq
      logical      , intent(out)       :: flunif
     
      real(kind=dp)  nyquist, xmeans,xdmin,xdmax,fmax,fmin

      integer   imin, imax

!
!     regularity of the sampling : (x_k = x_1 + (k-1)*step) or not
!
      call sampling(npts, xx, flunif)     ! determine whether the sampling is regular

      if(iprint >= 0) then                ! printouts
         write(iout,*)
         write(iout,41)
         write(iout,42)
         if(flunif) then
            write(iout,43) 
         else
            write(iout,44)
         endif
         write(iout,*)
      endif

!
!     basic parameters of the time sampling
!
      call getmaxmin(npts,xx,xmax,xmin,imax,imin)
      call sampling_histo(npts,xx,fmax,xdmin,xdmax)

      xmeans  = (xmax-xmin)/(npts-1)
      nyquist = 0.5d0/xmeans

      if(iprint >= 0) then
          if(flunif) then
             write(iout,60) xmeans,toffset,xmin,xmax,xdmin,nyquist
          else
             write(iout,61) xmeans,toffset,xmin,xmax,xdmin,nyquist
          endif
      endif
!!!!      write(*,60) xmeans,toffset,xmin,xmax,xdmin,nyquist
!
!     Determination of the resolution in the frequency domain
!
      call getwidth(npts,xx,flunif,flauto, frend,width) 
      if(iprint >= 0) then
        write(iout,*)
        write(iout,*)
        write(iout,51)
        write(iout,52)
        write(iout,53) width 
        write(iout,*)
      endif
!
!     sampling in the frequency domain
!

      if      (npts < 40 ) then   ! adapted frequency sampling for weakly sampled signal
         stepf  = width/8d0       !  FM 10/11/03  
      else if ((npts >40).and.(npts <100)) then
         stepf  = width/6d0       !  FM 10/11/03 
      else
         stepf  = width/5d0 
      endif 
!      freqres   = 0.5*width                 ! freqres (frequency resolution) is defined as a global variable of the module.
      freqres   = 1.0*width                  ! freqres (frequency resolution) is defined as a global variable of the module.
      fmin      = 5*stepf
      if(flauto) then                        ! automatic determination of the upper and lower frequencies
         fbeg  = fmin
         fend  = fmax                        ! from sampling_histo
      else
         fbeg  = max(frbeg, 2d0*stepf)       ! fbeg should not be too small
         fend  = frend
      endif
      nfreq = nint((fend-fbeg)/stepf)        ! could be very large ( several 10^4)
      fend  = fbeg +nfreq*stepf              ! it is recomputed to allow for the nint function

      if(iprint >= 0) then
         if(flunif) then      
            write(iout,70) stepf,fmin,fmax,fbeg,fend,nfreq
         else
            write(iout,71) stepf,fmin,fmax,fbeg,fend,nfreq
         endif
      endif
      write(*,70)  stepf,fmin,fmax,fbeg,fend,nfreq



!***************************************************************************
!
!     Formats
!
!***************************************************************************
41    format(//,'         TIME SAMPLING IN THE DATA')
42    format(   '         -------------------------',/)
43    format(' The sampling was found in  arithmetic progression')
44    format(' The sampling is not in  arithmetic progression')
60    format(&
            ' Stepsize in the time domain         :', E14.5, //,&
            ' Origin of time after time offset    :', E14.5, //,&
            ' Lowest  value of the time variable  :', E14.5, //,&
            ' Largest value of the time variable  :', E14.5, //,&
            ' Smallest  two-point  interval       :', E14.5, //,&
            ' Nyquist frequency                   :', E14.5,//)
61    format(&
            ' Mean stepsize in the time domain    :', E14.5, //,&
            ' Origin of time after time offset    :', E14.5, //,&
            ' Lowest  value of the time variable  :', E14.5, //,&
            ' Largest value of the time variable  :', E14.5, //,&
            ' Smallest  two-point  interval       :', E14.5, //,&
            ' Nyquist freq. for uniform sampling  :', E14.5,//)
!
51    format('        REPORT OF THE FREQUENCY SEARCH')
52    format('        ------------------------------',/)
53    format(' Line width in the frequency domain  :',E14.5)
70    format(&
            ' Stepsize in the frequency domain    :', E14.5, //,&
            ' Lowest  frequency recoverable       :', E14.5, //,&
            ' Highest frequency recoverable       :', E14.5, //,&
            ' First (lowest) frequency analysed   :', E14.5, //,&
            ' Last (highest) frequency analysed   :', E14.5, //,&
            ' Number of frequencies sampled       :', I9,///)
71    format(&
            ' Stepsize in the frequency domain    :', E14.5, //,&
            ' Lowest  frequency recoverable       :', E14.5, //,&
            ' Typical highest freq. recoverable   :', E14.5, //,&
            ' First (lowest) frequency analysed   :', E14.5, //,&
            ' Last (highest) frequency analysed   :', E14.5, //,&
            ' Number of frequencies sampled       :', I9,///)

      return
      end  subroutine getparam
!***********************************************************************************
      SUBROUTINE FOLDING(NOBS, X,  Period, Phase)
!***********************************************************************************
!
!
!     Folding of a time series over a trial period 
! 
! 
!*AUT       F. Mignard   
!*VER       Version 1, December 1999
!
!*INPUT   
!           NOBS    : number of data points
!           X[nobs] : Array with the time variable
!           Y[nobs] : Array with the data points y_i
!           Period  : Trial period in the same unit as X
!
!*OUTPUT
!           Phase   : Array with the dates within 0..period
! *EXTERNAL
!           no external called
! 
!***********************************************************************************

      implicit none
       
      real(kind=dp),   intent(in)    :: x(*)
      real(kind=dp),   intent(in)    :: period
      integer      ,   intent(in)    :: nobs

      real(kind=dp),   intent(out)   :: phase(*)

      integer                        :: k
 
      
      Do k = 1, nobs
         phase(k) = period*fp(x(k)/period)
      enddo

      return
      end  subroutine folding
!***********************************************************************************
      subroutine getmaxmin(nobs,array,xmax,xmin,imax,imin)
!***********************************************************************************
!
!
!     The programs returns the largest and less value in an array of real
! 
!
!*AUT     F. Mignard OCA/CERGA
!*VER     Version 1, December 1999
!
!*INPUT
!
!         NOBS  : Number of elements in the array to be searched
!         ARRAY : Array[1..n], n >= nobs with the data
!
!*OUTPUT
!
!         XMAX  : Largest  value in Array
!         XMIN  : Smallest value in Array
!         Imax  : XMAX = Array(imax)
!         Imin  : XMIN = Array(imin)
! 
!*EXTERNAL
!           no external called
!***********************************************************************************
      implicit  none

      integer      ,    intent(in)    :: nobs
      real(kind=dp),    intent(in)    :: array(nobs)

      real(kind=dp),    intent(out)   :: xmax, xmin
      integer      ,    intent(out)   :: imax, imin
 
      integer                         :: k

      xmax = array(1)
      xmin = array(1)
      imax = 1
      imin = 1
    
      Do k = 2 , nobs
         if(array(k).gt.xmax) then
            xmax = array(k)
            imax = k
         endif
         if(array(k).lt.xmin) then
            xmin = array(k)
            imin = k
         endif
      enddo

      return
      end subroutine getmaxmin 
!***********************************************************************************
      subroutine get_top_bot(nobs,array,xmax,xmin,imax,imin)
!***********************************************************************************
!
!
!     The programs returns the largest and less parabolic max or min in an array of real
!     with a local max or local min (like a parabola max or min)
!     Unlike the routine getmaxmin this one searches only for max or min 
!     such that the two nearest points are less or larger.
! 
!
!*AUT     F. Mignard OCA/CASSIOPEE
!*VER     Version 1, March 2005
!
!*INPUT
!
!         NOBS  : Number of elements in the array to be searched
!         ARRAY : Array[1..n], n >= nobs with the data
!
!*OUTPUT
!
!         XMAX  : Largest  value in Array with a 3-point parabola-like max
!         XMIN  : Smallest value in Array with a 3-point parabola-like min
!         Imax  : XMAX = Array(imax)
!         Imin  : XMIN = Array(imin)
! 
!*EXTERNAL
!           no external called
!***********************************************************************************
      implicit  none

      integer      ,    intent(in)    :: nobs
      real(kind=dp),    intent(in)    :: array(nobs)

      real(kind=dp),    intent(out)   :: xmax, xmin
      integer      ,    intent(out)   :: imax, imin
 
      integer                         :: k , jmax, jmin
      real(kind=dp)                   :: ymax, ymin 
      integer                         :: nmax 
      integer                         :: nmin  

      nmax = 0
      nmin = 0

      Do k = 2 , nobs-1
         if((array(k).gt.array(k-1)).and.(array(k).gt.array(k+1)) ) then
            nmax = nmax +1
            if(nmax == 1) then             ! first parabolic maximum
               xmax = array(k)
               imax = k
            else                           ! other parabolica maximums
               if(array(k).gt.xmax) then   ! larger parabolic maximum
                  xmax = array(k)
                  imax = k
               endif
            endif
         endif

         if((array(k).lt.array(k-1)).and.(array(k).lt.array(k+1)) ) then
            nmin = nmin +1
            if(nmin == 1) then             ! first parabolic minimum
               xmin = array(k)
               imin = k
            else                           ! other parabolica minimums
               if(array(k).lt.xmin) then   ! smaller parabolic minimum
                  xmin = array(k)
                  imin = k
               endif
            endif
         endif

      enddo

      if(nmax == 0) then                 !  no parabolic maximum found :: overall maximum
         call getmaxmin(nobs,array,ymax,ymin,jmax,jmin) 
         xmax = ymax
         imax = jmax
      endif
      if(nmin == 0) then                 ! no parabolic minimum found  :: overall minimum 
         call getmaxmin(nobs,array,ymax,ymin,jmax,jmin) 
         xmin = ymin
         imin = jmin
      endif

      return
      end subroutine get_top_bot 
!***********************************************************************************
      subroutine get_tops(nobs,array,lmax,xmax,imax)
!***********************************************************************************
!
!
!     The programs returns the kmax largest  max  in an array of real
!     with a local max  (like a parabola max or min)
!     Unlike the routine getmaxmin this one searches only for max  
!     such that the two nearest points are  larger.
! 
!
!*AUT     F. Mignard OCA/CASSIOPEE
!*VER     Version 1, June 2005
!
!*INPUT
!
!         NOBS  : Number of elements in the array to be searched
!         ARRAY : Array[1..n], n >= nobs with the data
!         lmax  : max number of maximums searched
!
!*OUTPUT
!
!         XMAX  : array with the Largest  values in Array with a 3-point parabola-like max
!         Imax  : array with the indices of the larges values XMAX = Array(imax)
! 
!*EXTERNAL
!           no external called
!***********************************************************************************
      implicit  none

      integer      ,    parameter     :: kmax = 5  ! number of maximums selected
      integer      ,    intent(in)    :: nobs
      real(kind=dp),    intent(in)    :: array(nobs)

      real(kind=dp),    intent(out)   :: xmax(kmax) 
      integer      ,    intent(out)   :: imax(kmax), lmax 
 
      integer                         :: k , jmax ,kk, jmin
      real(kind=dp)                   :: ymax, ymin, tabmax(nobs/2)
      integer                         :: nmax, itmax(nobs/2) ,ind(nobs/2)

      nmax = 0

      Do k = 2 , nobs-1
         if((array(k).gt.array(k-1)).and.(array(k).gt.array(k+1)) ) then
            nmax = nmax +1
            tabmax(nmax) = array(k)
            itmax(nmax)  = k
         endif
      enddo
     
      if(nmax > 0) then
         call quicksort(nmax,tabmax,ind)
      endif

      lmax  = min(kmax,nmax)  ! protection if there are a number of maximum les than kmax

      do kk = 1, lmax         ! no more than kmax maximums selected
         xmax(kk) = tabmax(nmax+1-kk)
         imax(kk) = itmax(ind(nmax+1-kk)) 
      enddo

      if(nmax == 0) then      !  no parabolic maximum found :: overall maximum
         call getmaxmin(nobs,array,ymax,ymin,jmax,jmin) 
         lmax    =1
         xmax(1) = ymax
         imax(1) = jmax
      endif

      return
      end subroutine get_tops 
!***********************************************************************************
      subroutine valmax(x0,x1,x2,y0,y1,y2,xmax,ymax)
!***********************************************************************************
!
!
!     The program returns the abscissa of the max (or min) of y(x)
!     and the value of max (or min) of y(x) 
!     from a three point parabolic interpolation
!     The three abscissae need not be regularly spaced or ordered
!     
! 
!
!*AUT     F. Mignard OCA/CERGA
!*VER     Version 2, December 1999
!         F90 Style : Dec 04
!
!*INPUT
!
!         x0,x1,x2   : The three abscissae  (order irrelevant)
!         y0,y1,y2   : The corresponding values of y(x)
!
!*OUTPUT
!
!         xmax  : Abscissa of the max (or min) of y(x) from parabolic interpolation
!         ymax  : The max (or min) of y(x) from parabolic interpolation
! 
!*EXTERNAL
!           no external called
!***********************************************************************************! 
      implicit none

      real(kind=dp),  intent(in)    :: x0, x1, x2
      real(kind=dp),  intent(in)    :: y0, y1, y2

      real(kind=dp),  intent(out)   :: xmax, ymax

      real(kind=dp)                 :: xx0, xx2
      real(kind=dp)                 :: yy0, yy2
!
!     Shift of the origin of abscissae and ordinates
!      
      xx0 = x0-x1
      xx2 = x2-x1

      yy0 = y0-y1
      yy2 = y2-y1

      xmax = x1+0.5d0*(xx2**2*yy0-xx0**2*yy2)/(xx2*yy0-xx0*yy2)
      ymax = y1+0.5d0*(xx2**2*yy0-xx0**2*yy2)/(xx2**2*xx0-xx0**2*xx2)*(xmax-x1)
      return
      end subroutine valmax
!***********************************************************************************
      subroutine arraymax(npts,xx,yy,xmax,ymax)
!***********************************************************************************
!
!     Search of the maximum of functions sampled at xx[npts] with values in array yy[npts]
!     One locates the maximum in the array and then searches by parabolic
!     interpolation the maximum of a continuous function between the three points
!     around the maximum of the array. xmax and y(xmax) are returned.
!     x(.) assumed sorted in increasing order.
! 
!*AUT     F. Mignard OCA/CERGA
!*VER     Version 1, December 1999
!*        Version 2. February 2002 (protection against imax = 1 or imax = npts)
!         Version 3. March    2005 (protection  for the max  within the data range)
!         F90 Style : Dec 04
!
!*INPUT   
!           npts    : size of the array to be searched in
!           xx      : array of abscissae
!           yy      : array of data points          
!           
!*OUTPUT
!           xmax    : abscissa of the max in units of the array  xx
!           ymax    : maximum of  yy (= yy(xmax)) from parabolic interpolation
! 
!*EXTERNAL
!           getmaxmin,valmax
!***********************************************************************************
!
      implicit none

      integer      ,  intent(in)   :: npts
      real(kind=dp),  intent(in)   :: xx(*), yy(*)

      real(kind=dp),  intent(out)  :: xmax, ymax

      real(kind=dp)                :: x0, x1, x2
      real(kind=dp)                :: y0, y1, y2

      real(kind=dp)                :: ymin
      integer                      :: imax, imin 



!
!     Index of the maximum value of the array yy[]
!
!      call getmaxmin(npts,yy,ymax,ymin,imax,imin)

      call get_top_bot(npts,yy,ymax,ymin,imax,imin) ! parabolic max or min

!
!     Parabolic interpolation with three points around the max
!
      if((imax.gt.1).and.(imax.lt.npts)) then
         x0 = xx(imax-1)
         x1 = xx(imax)
         x2 = xx(imax+1)

         y0 = yy(imax-1)
         y1 = yy(imax)
         y2 = yy(imax+1)

         call valmax(x0,x1,x2,y0,y1,y2,xmax,ymax)

         if((xmax <x0).or.(xmax> x2)) then        ! max between x0 and x2
            xmax = x1
            ymax = y1
         endif

      else if (imax.eq.1)   then
         x0 = xx(imax)
         x1 = xx(imax+1)
         x2 = xx(imax+2)

         y0 = yy(imax)
         y1 = yy(imax+1)
         y2 = yy(imax+2)

         call valmax(x0,x1,x2,y0,y1,y2,xmax,ymax)

         if(xmax < x0) then                        ! max within the data range
            xmax = x0
            ymax = y0
         endif

      else if (imax.eq.npts) then
         x0 = xx(imax-2)
         x1 = xx(imax-1)
         x2 = xx(imax)

         y0 = yy(imax-2)
         y1 = yy(imax-1)
         y2 = yy(imax)

         call valmax(x0,x1,x2,y0,y1,y2,xmax,ymax)

         if(xmax > x2) then                        ! max within the data range
            xmax = x2
            ymax = y2
         endif

      endif

      return
      end    subroutine arraymax
!***********************************************************************************
      subroutine powermax(npts,xx,yy,xmax,ymax)
!***********************************************************************************
!
!     Search of the maximum of functions sampled at xx[npts] with values in array yy[npts]
!     One locates the ~ 5 maximums from direct search in the array and then searches by parabolic
!     interpolation the maximum of a continuous function between the three points
!     around the maximums. Then the largest maximum is found and xmax and y(xmax) are returned.
!     x(.) assumed sorted in increasing order.
!
! 
!*AUT     F. Mignard OCA/CERGA
!*VER     Version 1, July 2005
!
!*INPUT   
!           npts    : size of the array to be searched in
!           xx      : array of abscissae
!           yy      : array of data points          
!           
!*OUTPUT
!           xmax    : abscissa of the max in units of the array  xx
!           ymax    : maximum of  yy (= yy(xmax)) from parabolic interpolation
! 
!*EXTERNAL
!           get_tops,valmax, getmaxmin
!***********************************************************************************
!
      implicit none

      integer      ,  intent(in)   :: npts
      real(kind=dp),  intent(in)   :: xx(*), yy(*)

      real(kind=dp),  intent(out)  :: xmax, ymax

      real(kind=dp)                :: x0, x1, x2
      real(kind=dp)                :: y0, y1, y2

      real(kind=dp)                :: ymin
      integer                      :: imax, imin 

      integer                      :: lmax, kk

      real(kind=dp)                :: ytop(10), fmax(10), pmax(10) ! 10: should be > =  kmax in routine get_tops
      integer                      :: itop(10) 

!
!     Index of the maximum value of the array yy[]
!

       call get_tops(npts,yy,lmax,ytop,itop)         ! FM 06/05


      do kk= 1, lmax                                 ! lmax : number of local parabolic maximums 
!
!     Parabolic interpolation with three points around the max
!
         imax = itop(kk)
         if((imax.gt.1).and.(imax.lt.npts)) then
            x0 = xx(imax-1)
            x1 = xx(imax)
            x2 = xx(imax+1)

            y0 = yy(imax-1)
            y1 = yy(imax)
            y2 = yy(imax+1)

            call valmax(x0,x1,x2,y0,y1,y2,xmax,ymax)

            if((xmax <x0).or.(xmax> x2)) then        ! max between x0 and x2
               xmax = x1
               ymax = y1
            endif

         else if (imax.eq.1)   then
            x0 = xx(imax)
            x1 = xx(imax+1)
            x2 = xx(imax+2)

            y0 = yy(imax)
            y1 = yy(imax+1)
            y2 = yy(imax+2)

            call valmax(x0,x1,x2,y0,y1,y2,xmax,ymax)

            if(xmax < x0) then                        ! max within the data range
               xmax = x0
               ymax = y0
            endif

         else if (imax.eq.npts) then
            x0 = xx(imax-2)
            x1 = xx(imax-1)
            x2 = xx(imax)

            y0 = yy(imax-2)
            y1 = yy(imax-1)
            y2 = yy(imax)

            call valmax(x0,x1,x2,y0,y1,y2,xmax,ymax)

            if(xmax > x2) then                        ! max within the data range
               xmax = x2
               ymax = y2
            endif

         endif
         fmax(kk) = xmax
         pmax(kk) = ymax
      enddo

         call getmaxmin(lmax,pmax,ymax,ymin,imax,imin)  ! max among the lmax tested
         xmax = fmax(imax)                              ! frequency of the max

      return
      end    subroutine powermax
!***********************************************************************************
      subroutine sampling(npts,xx,flunif)
!***********************************************************************************
!
!     This program determines whether a time sampling x(k) , k=1..npts
!     is regular with x(k+1)-x(k) = cte = (x(npts)-x(1)/(npts-1)
!     The sequence could be in increasing or decreasin order, but it must
!     be sorted. 
!     If the sequence is not sorted, although it would be in arithmetic progression if sorted,
!     the program does not find the regular sampling.
!     Tests are performed in floating point with an accepted relative error equal to tiny = 1d-5.
!    
!*AUT     F. Mignard OCA/CERGA
!*VER     Version 1, September 2003

!
!*INPUT   
!           npts    : number of data points
!           xx      : array of abscissae (time sampling)
!           
!*OUTPUT
!           flunif  : .true. = regular sampling , .false. = otherwise
!
!*EXTERNAL
!           no external called
!***********************************************************************************
      implicit none


      integer,     intent(in)    :: npts
      real(dp),    intent(in)    :: xx(*) 
      logical,     intent(out)   :: flunif

      real(dp),    parameter     :: tiny = 1d-5      ! this allows for numerical round-off in the sampling

      real(dp)                   :: step , diff
      integer                    :: k

      logical                    :: fltest
      
      step = (xx(npts)- xx(1))/(npts-1)               ! could be positive or negative

      fltest = .true.
      k = 2
      do while ((fltest).and.(k <=npts))
         diff = xx(k)-xx(k-1)                         ! negative or positive
         if(abs(diff - step)/abs(step) > tiny) then   ! tests equality within tiny in relative error.
            fltest = .false.                          ! exit the loop next time
         endif
         k = k+ 1
      enddo
      flunif = fltest
      return
      end   subroutine sampling
!***********************************************************************************
      subroutine getwidth(npts,xx,flunif,flauto,frend,width)
!***********************************************************************************
!
!     This program determines the width of line in the frequency domain for 
!     a particular time sampling given in the array xx.
!     Few high resolution lines are computed with a DFT to determine the
!     optimal frequency sampling in the computation of a periodogram of a signal
!     yy(k) sampled at xx(k). 
!     The sampling should be a fraction (say 1/3 or 1/5) of the width so that the
!     maximum of the line is not missed in the periodogram. 
!     Plain cosine signals are generated and analysed with a DFT.
! 
!*AUT     F. Mignard OCA/CERGA
!*VER     Version 1, December 1999
!         Version 2, April 2003 : the maximum power is not assumed to be equal to 1.
!                                 Max of power is searched and used to scale the height of the line
!         version 3. Sept  2003   different processing for regular (arithmetic progression) or irregular sampling
!         version 4. Feb   2005   allowing for mode flauto =.true. and protection against flow < 0
!         version 5. June  2005   width determines initially at 0.7 of the maximum and then a factor is applied to have the WHM
!                                 This is done for lines of non standard shape not returning to 0 after the maximum.
!
!*INPUT   
!           npts    : number of data points
!           xx      : array of abscissae (time sampling)
!           flunif  : .true. is regular sampling,  .false. otherwise
!           flauto  : .true. :frequency range determined by the program; .false. : lower and upper frequencies given in the setting
!           frend   : maximum frequency when flauto = .false.
!           
!*OUTPUT
!           width   : width of  line (at half maximum) in the frequency domain for this time sampling
! 
!*EXTERNAL
!           sampling_histo, getmaxmin,frequence
!***********************************************************************************
! 

!
      implicit none
 
      integer,        intent(in)        :: npts
      real(kind=dp),  intent(in)        :: xx(*),  frend
      logical,        intent(in)        :: flunif, flauto

      real(kind=dp),  intent(out)       :: width

      real(kind=dp),  parameter         :: zoom =  20  ! zoom factor for the sampled lines
      integer      ,  parameter         :: nfreq= 200  ! number of frequencies

      real(kind=dp),  dimension(nfreq)  :: xfreq, power
      real(kind=dp),  dimension(npts)   :: y

      real(kind=dp)                     :: fmax, xdmin, xdmax
      real(kind=dp)                     :: xmax, xmin
      real(kind=dp)                     :: xxmax, xxmin
      real(kind=dp)                     :: step, stepz, fend, frange
      real(kind=dp)                     :: freq, flow, freqinf, freqsup
      integer                           :: imax,  imin
      integer                           :: iimax, iimin
      integer                           :: ntest, nw, kf, k

     
      call sampling_histo(npts,xx,fmax,xdmin,xdmax) ! to get fmax if flauto = .true.

      call getmaxmin(npts,xx,xmax,xmin,imax,imin) ! max and min of x(k)
      step   = 1d0/(xmax-xmin)               ! typical step in the frequency domain
      if(flunif) then                        ! regular sampling
         ntest  = 1                          ! number of lines analysed (with uniform sampling one test is enough)
         if(flauto) then
            fend   = 0.05d0*npts*step        ! typical freqency
         else
            fend   = min(frend, 0.1d0*npts*step)                  ! highest freqency 
         endif
         stepz  = step/zoom                  ! high resolution frequency stepsize
         frange = nfreq/2d0*stepz            ! larger than half line width 
      else                                   ! irregular sampling
         ntest  = 15                         ! number of lines analysed
         if(flauto) then
            fend   = 0.5*fmax                ! highest freqency computed in sampling_histo above
         else
            fend   = frend                   ! highest freqency 
         endif
         stepz  = step/zoom                  ! high resolution frequency stepsize
         frange = nfreq/2d0*stepz            ! larger than half line width 
      endif
      nw     = 0
      width  = 0d0
 
      do kf =1 , ntest 
         freq = kf*fend/ntest                  ! select ntest lines at frequencies uniformly distributed
 
         do k = 1 , npts
            y(k) = cos(deupi*freq*xx(k))      !plain harmonic signal sampled at xx(k)
         enddo

         flow  = max(freq - frange , stepz)    ! lower frequecy to start the sample of the line      
         call waves(npts,xx,y,flunif,flow,nfreq,stepz,xfreq,power) 

         call getmaxmin(nfreq,power,xxmax,xxmin,iimax,iimin)

         freqinf = 0d0
         freqsup = 0d0
            
         do k = 2, nfreq                      ! determines the  width (WHM) of the current line

            if( (power(k-1).lt.0.7d0*xxmax) .and. (power(k).gt.0.7d0*xxmax) ) then  ! 0.7 to explore the top of the line
               freqinf = (xfreq(k-1) + xfreq(k))*0.5d0
            endif

            if( (power(k-1).gt.0.7d0*xxmax) .and. (power(k).lt.0.7d0*xxmax) ) then
               freqsup = (xfreq(k-1) + xfreq(k))*0.5d0
            endif     

         enddo

         if((freqinf.gt.0d0).and.(freqsup.gt.0d0).and.(freqsup.gt.freqinf)) then
            width = width +  freqsup-freqinf 
            nw = nw +1    
         endif

      enddo
!
!     value of the width
!
      if(nw.gt.0) then
         width = 1.4*width/nw  ! 1.4 to get WHM  FM 04/07/05 (goes with 0.7 above instead of 0.5)
      else
         width = step/3d0      !default value in case of structurless lines
      endif

      return
      end  subroutine getwidth
      
!***********************************************************************************
      subroutine freqsearch(npts,xx,yy,numfreq,maxdeg,flplot,flauto,iprint,iout,frbeg,frend, fltime, tzero, freq,snr,ampc,amps)
!***********************************************************************************
!
!     Search of freqencies in a time series
!     The data y(t) is read in a textfile as xx(k), yy(k)
!     The independant variable xx(k) (call it the time) is not necessarily regularly sampled
!     However the result is much more reliable with observations  more or less uniformly
!     distributed over the time. With large gaps and strongly varying observation densities
!     spurious frequencies may be found.
! 
!     One searches the most significant frequencies in yy(x) with a peridogram .
!     The minimum, maximum and stepsize frequencies are determined automatically
!     from the the overall properties of xx(k) : range, mean density, clumping ...
!     The stepsize is such that no line  will be missed in the periodogram.
! 
!     Once a line has been located a vernier is applied to determine its precise location
!     and the power in the  line. The vernier follows from an high resolution periodogram of
!     limited range around the center of the line. 
!     The max is eventually located with a three point parabolic interpolation
! 
!     For each location of a new frequency a model based on all the previous lines is
!     fitted to the data by non linear least squares as
!     S(t) =  a_0 + Sum (a_i*cos(2pi nu_i t) + b_i*sin (2pi nu_i t) ) 
!     or to a more complex model with the amplitude being polynomials of time.
!     Then a new signal orthogonal to the model is  computed as z(t) = y(t)- s(t)
!     and a new frequency is searched in z(t).
!     The loop is carried out  numfreq times
! 
!     By default the unit of time is taken from the sampling in xx(k) as  the increase of
!     xx of one. Then the unit of frequency is just the inverse.
!      
! 
!*AUT     F. Mignard OCA/CERGA
!*VER     Version 1, December 1999
!*VER     Version 2, February 2002
!                    Use of a non linear fit a each new frequency found over amplitudes and frequencies.
!         Version 3, September 2003
!                    A minor bug has been fixed in the linear leastsquares solution : the normal matrix
!                    was updated at each new lines, keeping the previous row and columns already computed
!                    This assumed (as in version 1) that the frequencies were not changed during the run.
!                    This was no longer true with version 2 and should have been changed at that time.
!                    This could produce non positive definite matrices.
!                    So the design matrix is now completely recomputed
!                    from scratch in the main loop. (new subroutine : desmat).
!                    A leastsquares solver based on SVD is also available.
!         Version 4, September 2003
!                    Introduction of newfreq_lsq, faster than the Leveberg_Marquart. A best solution
!                    is now computed at each new frequency found. The frequency is adjusted along
!                    with the k-1 previous frequencies available. Convergence is tested at every step. 
!         Version 5, February 2004
!                    Complex model with Poisson series representation
!         Version 6, March 2005
!                    No change in the content, but routine rewritten and completely restructured
!                    The main loop in more sequential than in the previous versions
!
!     Calling sequence :
!
!     call freqsearch(npts,xx,yy,numfreq,idegf,maxdeg,flplot,flauto,iprint,iout,frbeg,frend,freq,snr,ampc,amps)
!
!*INPUT   
!           npts    : size of the array to be searched in
!           xx      : array of abscissae (nominally time sampling)
!           yy      : array of data points 
!           numfreq : number of lines searched   
!           idegf   : array(0:numfreq) with the degree of the polynomial in power of time for each line.
!           maxdeg  : highest degree = maxval(idegf)
!           flplot  : logical flag for the periodogram plot (true = plot, false = no plot)   
!           flauto  : logical flag for preset or automatic search of lower and upper frequencies(true : automatic, false : manual)
!           iprint  :  control of the output 
!                       0  : minimum printouts generated
!                       1  : output of the parameters of the run
!                       2  : 1 + output of the solution before exit
!           iout    : logical output unit  
!                     In many fortan implementation the UNIT =6 is the default for the screen
!                     if the unit is not open to a file
!                     Thus to get the output on the screen : set IOUT =6, without OPEN(6 ..) in the main.
!           frbeg   : preset lower frequency in the periodograms (unused when flauto = true)
!           frend   : preset upper frequency in the periodograms (unused when flauto = true)
!           fltime  : logical flag : .true. : offset computed to center the independant variable about its mean ; .false. : time offset given by the user in tzero. 
!           tzero   : offset read in the setting when fltime = .false.
!           
!*OUTPUT
!           freq    : array of frequencies found
!           snr     : array of signal to noise found for each frequency
!           ampc    : array with the amplitudes of cosine terms (ampc(0) = cte term)
!           amps    : array with the amplitudes of sine terms
!
!*EXTERNALS
!           getwidth,update,newfreq,newsol,del_lines,waves,arraymax,writepower
! 
!***********************************************************************************
!
!*****************************************
      implicit none
!*****************************************

      integer,       intent(in)    :: npts, numfreq,  maxdeg
      logical,       intent(in)    :: flplot, flauto, fltime
      integer,       intent(in)    :: iprint, iout
      real(kind=dp), intent(inout) :: xx(npts)                   ! the array is centered in the routine
      real(kind=dp), intent(in)    :: yy(npts)
      real(kind=dp), intent(in)    :: frbeg, frend, tzero

      real(kind=dp), intent(out)   :: freq(numfreq)
      real(kind=dp), intent(out)   :: ampc(0:maxdeg,0:numfreq)
      real(kind=dp), intent(out)   :: amps(0:maxdeg,0:numfreq)
      real(kind=dp), intent(out)   :: snr(numfreq)

      real(kind=dp), parameter     :: tol1    = 1d-8              ! various tolerances for the non-linear leasquares
      real(kind=dp), parameter     :: tol2    = 1d-8
      
      integer,       parameter     :: ipower  = 99                ! unit of external file
 
      real(kind=dp)                :: freq_0(numfreq)
      real(kind=dp)                :: ampc_0(0:maxdeg,0:numfreq)
      real(kind=dp)                :: amps_0(0:maxdeg,0:numfreq)
      real(kind=dp)                :: zzz(npts)
      real(kind=dp)                :: xmed, hrange, zmean, width, tmean
      real(kind=dp)                :: xmin, xmax, stepf, fbeg, fend
      real(kind=dp)                :: freqmax, xmedp

      real(kind=dp)                :: ampli, pampli
       
      integer                      :: nfreq, k, ierr
      real(kind=dp)                :: xvaln


      character*2  filenum
      logical                      :: flunif
 
      real(kind=dp),  allocatable  :: xfreq(:), power(:)          ! frequency domain
!
!    centering the time sampling for better stability
!

      call timebase(npts, xx, tmean, xmed, hrange,zmean, zz)      !moments of the time sampling
 
      if(fltime) then
         toffset = tmean                                          ! center the independant variable
      else
         toffset = tzero                                          ! offset as requested in the settings
      endif
      xx = xx-toffset                                             ! offset the independant variable

!
!     general parameters of the run
!
      call getparam(npts, xx,iout,iprint,flauto,frbeg, frend,& 
                 flunif, xmin, xmax, width, nfreq, stepf, fbeg, fend )

!      flunif = .false.   !testing 

      allocate(xfreq(nfreq), power(nfreq))
!
!     Main loop on the lines searched in the data
!
      freq = 0
      ampc = 0
      amps = 0
!
!     Mean, linear or polynomial trend computed
!
      k = 0
      call newamp_lsq(npts,xx,yy,iprint,iout,k,freq,ampc,amps)
      call model(npts,xx,yy,k,freq,ampc,amps,zzz)                                 ! remove the model on k lines  12/04/04
      xvaln = sqrt(func(k,freq,ampc,amps))                                        ! full model 12/04/04

      write(iout, 200)
      write(iout, 205)
      write(iout, 200)
      write(iout,*)
      write(iout, 210) xvaln
      write(iout,*)
      
      if(flplot) then
         open(unit = ipower, file = 'resid_00.txt',status='unknown')
         call writepower(ipower,npts,xx,zzz)                                      ! data file centred and without trend
      endif  

      do k = 1 , numfreq                                                          ! loop on the frequencies

         write(*,65)k, numfreq

!
!     search of the strongest spectral line in zzz
! 
         call  one_line(npts,xx,zzz,flunif,fbeg,width,nfreq,stepf,xfreq,power,xmedp,freqmax,ampli)
 
         freq(k)  = freqmax                                                      ! storage of the new frequency
         if(k > 1) then                                                          ! significance of the line found
            snr(k-1)  = pampli/xmedp                                             ! max of the line/(mean value of the PS) qmax : defined later but statement protected with k > 1
         endif
         if(k == numfreq) then                                                   ! significance of the line found no qmax available for the last line
            snr(k)    = ampli/xmedp                                              ! max of the line/(mean value of the PS) 
         endif
 
         pampli = ampli                 ! stores the current amplitude needed for the computation of S/N 
         
         if(iprint.eq.2) then
            write(iout,*)
            write(iout,*)
            write(iout,*)
            write(iout,230) freqmax
         endif
 
         call newamp_lsq(npts,xx,yy,iprint,iout,k,freq,ampc,amps)

!
!     save input values of frequencies and amplitudes to restart in case of absence of convergence
!
         freq_0 = freq
         ampc_0 = ampc
         amps_0 = amps

         call newfreq_lsq(npts,xx,yy,iprint,iout,tol1,k,freq,ampc,amps,ierr)   ! nonlinear leastsquares on the k frequencies (added on 18/09/2003)
         if(iprint >=1) then
            write(iout,400) k, ierr
            write(iout,410)
         endif
         if(ierr==200) then                 ! convergence not achieved with newfreq_lsq . Try with a Levenberg-Marquardt optimisation
            freq = freq_0
            ampc = ampc_0
            amps = amps_0
            call newfreq_lmd(npts,iprint,iout,tol2,k,freq,ampc,amps) 
         else if (ierr==100) then           ! near convergence achieved. No reset of the initial values
            call newfreq_lmd(npts,iprint,iout,tol2,k,freq,ampc,amps) 
         endif
        
         call  model(npts,xx,yy,k,freq,ampc,amps,zzz)                           ! remove the model on k lines  12/04/04
!
!        optional output of the periodogram and current residuals
!
         write(filenum,'(i2.2)') k                                               ! to index the filename of power.txt
         if(flplot) then
            open(unit = ipower, file = 'resid_'//filenum//'.txt',status='unknown')
            call writepower(ipower,npts,xx,zzz)                                  ! file to plot of remaining signal

            open(unit = ipower, file = 'power_'//filenum//'.txt',status='unknown')
            call writepower(ipower,nfreq,xfreq,power)                            ! file to plot of periodogram 
         endif  

      enddo
      write(*,*) ' Frequency search is over successfully '
      if (iprint >=1) then
         write(iout, *)
         write(iout, *)
         write(iout, 241)
         write(iout, 240)
         write(iout, 241)
         call printsol_ext(iout,numfreq,freq,ampc,amps)
         write(iout, *)
         write(iout, *)
      endif

!     ************************************************************
! 
65    format(' Search of the frequency ', i4, ' out of ', i4)

200   format(' -------------------------------')
205   format(' REMOVAL OF THE AVERAGE or TREND      ')
210   format('   Data RMS after removal of the trend :', E14.6)

230   format(' New frequency found from the periodogram : ', E14.6,/)
240   format(' SOLUTION  BEFORE FINAL LEASTSQUARES FIT  ')
241   format(' ---------------------------------------  ')

400   format(//,'   Convergence code found for the line ', i3,' : ', i4)
410   format('   Code = 0   : good convergence, no more attempts', /,&
             '        = 100 : apply non-linear LSQR with good starting values', /,&
             '        = 200 : apply non-linear LSQR with poor starting values ',//)
      return
      end  subroutine freqsearch
!***********************************************************************************
      subroutine periodsearch(npts,xx,yy,numfreq,maxdeg,flplot,flauto,iprint,iout,frbeg,frend, fltime, tzero, freq,snr,ampc,amps)
!***********************************************************************************
!
!     Search of a periodic signal in a time series.
!     The routine is a specialisation of freqsearch to the case when a
!     periodic signal is searched in the data instead of a quasiperiodic or multiperiodic.
!     The data y(t) is read in a textfile as xx(k), yy(k)
!     The independant variable xx(k) (call it the time) is not necessarily regularly sampled
!     However the result is much more reliable with observations  more or less uniformly
!     distributed over the time. With large gaps and strongly varying observation densities
!     spurious frequencies may be found.
! 
!     One searches the most significant frequencies in yy(x) with a peridogram .
!     The minimum, maximum and stepsize frequencies are determined automatically
!     from the the overall properties of xx(k) : range, mean density, clumping ...
!     The stepsize is such that no line  will be missed in the periodogram.
! 
!     Once a line has been located a vernier is applied to determine its precise location
!     and the power in the  line. The vernier follows from an high resolution periodogram of
!     limited range around the center of the line. 
!     The max is eventually located with a three point parabolic interpolation
! 
!     Then  this line is fitted to the data with a non linear least squares as
!     S(t) =  a_0 + Sum (a_i*cos(2pi nu_i t) + b_i*sin (2pi nu_i t) ) 
!     or to a more complex model with the amplitude being polynomials of time.
!
!     One this fundamental frequency (nu_0) is secured there are two possibilities :
!     - this could be the perdiod of the signal, so other lines are harmonics 
!       with integral multiple of this frequency
!     - the frequency found is in fact a multiple of the fundamental frequency.
!       in case there is more power in an harmonic than in the fundamental. The
!       program attemps to find the fundamental.
!
!     To find the real period one compute periodograms in the vicinity of 
!     nu_0/2, nu_0/3    and 2nu_0, 3nu_0.
!     Tests are applied to the amplitudes to decide whether a frequency smaller than nu_0
!     fits the data with a reasonable power.
!
!     By default the unit of time is taken from the sampling in xx(k) as  the increase of
!     xx of one. Then the unit of frequency is just the inverse.
!      
! 
!*AUT     F. Mignard OCA/Cassiopee
!*VER     Version 1, March 2005
!
!     Calling sequence :
!
!     call freqsearch_p(npts,xx,yy,numfreq,idegf,maxdeg,flplot,flauto,iprint,iout,frbeg,frend,freq,snr,ampc,amps)
!
!*INPUT   
!           npts    : size of the array to be searched in
!           xx      : array of abscissae (nominally time sampling)
!           yy      : array of data points 
!           numfreq : number of lines searched  :: limited to 2 for a periodic signal  
!           idegf   : array(0:numfreq) with the degree of the polynomial in power of time for each line.
!           maxdeg  : highest degree = maxval(idegf)
!           flplot  : logical flag for the periodogram plot (true = plot, false = no plot)   
!           flauto  : logical flag for preset or automatic search of lower and upper frequencies(true : automatic, false : manual)
!           iprint  :  control of the output 
!                       0  : minimum printouts generated
!                       1  : output of the parameters of the run
!                       2  : 1 + output of the solution before exit
!           iout    : logical output unit  
!                     In many fortan implementation the UNIT =6 is the default for the screen
!                     if the unit is not open to a file
!                     Thus to get the output on the screen : set IOUT =6, without OPEN(6 ..) in the main.
!           frbeg   : preset lower frequency in the periodograms (unused when flauto = true)
!           frend   : preset upper frequency in the periodograms (unused when flauto = true)
!           fltime  : logical flag : .true. : offset computed to center the independant variable about its mean ; .false. : time offset given by the user in tzero. 
!           tzero   : offset read in the setting when fltime = .false.
!           
!*OUTPUT
!           freq    : array of frequencies found
!           snr     : array of signal to noise found for each frequency
!           ampc    : array with the amplitudes of cosine terms (ampc(0) = cte term)
!           amps    : array with the amplitudes of sine terms
!
!*EXTERNALS
!           getwidth,update,newfreq,newsol,del_lines,arraymax,writepower
! 
!***********************************************************************************
!
!*****************************************
      implicit none
!*****************************************

      integer,       intent(in)    ::  npts, numfreq,  maxdeg
      logical,       intent(in)    ::  flplot, flauto, fltime
      integer,       intent(in)    ::  iprint, iout
      real(kind=dp), intent(inout) ::  xx(npts)                   ! the array is centered in the routine
      real(kind=dp), intent(in)    ::  yy(npts)
      real(kind=dp), intent(in)    ::  frbeg, frend, tzero

      real(kind=dp), intent(out)   ::  freq(numfreq)
      real(kind=dp), intent(out)   ::  ampc(0:maxdeg,0:numfreq)
      real(kind=dp), intent(out)   ::  amps(0:maxdeg,0:numfreq)
      real(kind=dp), intent(out)   ::  snr(numfreq)

      real(kind=dp), parameter     :: tol1    = 1d-8              ! various tolerances for the non-linear leasquares
      real(kind=dp), parameter     :: tol2    = 1d-8
      real(kind=dp), parameter     :: xwidth  = 2d0               ! set the range of frequency search around over or undertones (in line width)  
      
      integer,       parameter     :: ipower  = 99                ! unit of external file
      integer,       parameter     :: ntone_m =  3                ! number of undertones searched for
      integer,       parameter     :: ntone_p =  2                ! number of overtones searched for
      integer,       parameter     :: nfreq_2 =  60               ! number of frequencies sampled around under or overtones
      integer,       parameter     :: nfreq_n =  200              ! number of frequencies sampled for the periodogram noise
 
      real(kind=dp)                :: freq_0(numfreq)
      real(kind=dp)                :: ampc_0(0:maxdeg,0:numfreq)
      real(kind=dp)                :: amps_0(0:maxdeg,0:numfreq)
      real(kind=dp)                :: zzz(npts)
      real(kind=dp)                :: xmed, hrange, zmean, width, tmean
      real(kind=dp)                :: stepf, fbeg, fend, stepf_n
      real(kind=dp)                :: stepf_2, fbeg_2
      real(kind=dp)                :: xmin, xmax, ymin, ymax
      real(kind=dp)                :: freqmax, xmedp

      real(kind=dp)                :: ampli, pampli, xmedp_m, xmedp_p
       
      integer                      :: nfreq, k, ierr, kk, imin, imax, jmin, jmax

      real(kind=dp)                :: xvaln

      real(kind=dp), dimension(ntone_m) :: ftone_m, atone_m
      real(kind=dp), dimension(ntone_p) :: ftone_p, atone_p
      real(kind=dp), dimension(nfreq_n) :: xfreq_n, power_n
      real(kind=dp), dimension(nfreq_2) :: yfreq  , qower
      
      character*2  filenum
      logical                      :: flunif
 
      real(kind=dp),  allocatable  :: xfreq(:), power(:)          ! frequency domain
!
!    centering the time sampling for better stability
!

      call timebase(npts, xx, tmean, xmed, hrange,zmean, zz)      !moments of the time sampling
 
      if(fltime) then
         toffset = tmean                                          ! center the independant variable
      else
         toffset = tzero                                          ! offset as requested in the settings
      endif
      xx = xx-toffset                                             ! offset the independant variable

!
!     general parameters of the run
!
      call getparam(npts, xx,iout,iprint,flauto,frbeg, frend,& 
                 flunif, xmin, xmax, width, nfreq, stepf, fbeg, fend )

      allocate(xfreq(nfreq), power(nfreq))
!
!     Main loop on the lines searched in the data
!
      freq = 0
      ampc = 0
      amps = 0
!
!     Mean, linear or polynomial trend computed
!
      k = 0
      call newamp_lsq(npts,xx,yy,iprint,iout,k,freq,ampc,amps)
      call model(npts,xx,yy,k,freq,ampc,amps,zzz)                            ! remove the model on k lines  12/04/04
      xvaln = sqrt(func(k,freq,ampc,amps))                                   ! full model 12/04/04

      write(iout, 200)
      write(iout, 205)
      write(iout, 200)
      write(iout,*)
      write(iout, 210) xvaln
      write(iout,*)


      if(flplot) then
         open(unit = ipower, file = 'resid_00.txt',status='unknown')
         call writepower(ipower,npts,xx,zzz)                                  ! data file centred and without trend
      endif  

!
!     search of the line with the largest power
!
      k = 1
      write(*,65)k, numfreq

      call  one_line(npts,xx,zzz,flunif,fbeg,width,nfreq,stepf,xfreq,power,xmedp,freqmax,ampli)
      freq(k)  = freqmax                                                    ! storage of the new frequency
      pampli   = ampli
      if(iprint.eq.2) then
         write(iout,*)
         write(iout,*)
         write(iout,*)
         write(iout,230) freqmax
      endif

      call newamp_lsq(npts,xx,yy,iprint,iout,k,freq,ampc,amps)              ! fit for the amplitudes

!
!     save input values of frequencies and amplitudes to restart in case of absence of convergence
!
      freq_0 = freq
      ampc_0 = ampc
      amps_0 = amps

      call newfreq_lsq(npts,xx,yy,iprint,iout,tol1,k,freq,ampc,amps,ierr)   ! nonlinear leastsquares on the k frequencies (added on 18/09/2003)
      if(iprint >=1) then
         write(iout,400) k, ierr
         write(iout,410)
      endif
      if(ierr==200) then                 ! convergence not achieved with newfreq_lsq . Try with a Levenberg-Marquardt optimisation
         freq = freq_0
         ampc = ampc_0
         amps = amps_0
         call newfreq_lmd(npts,iprint,iout,tol2,k,freq,ampc,amps) 
      else if (ierr==100) then           ! near convergence achieved. No reset of the initial values
         call newfreq_lmd(npts,iprint,iout,tol2,k,freq,ampc,amps) 
      endif
        
      call  model(npts,xx,yy,k,freq,ampc,amps,zzz)                           ! remove the model on k lines  12/04/04

!
!     special call at low frequency resolution to determine the noise in the periodogram
!
      stepf_n = (fend-fbeg)/float(nfreq_n)


      call  one_line(npts,xx,zzz,flunif,fbeg,width,nfreq_n,stepf_n,xfreq_n,power_n,xmedp,freqmax,ampli)
      snr(k)   = pampli/xmedp                                                ! max of the line/(mean value of the PS)= S/N 

!
!     optional output of the periodogram and current residuals
!
      write(filenum,'(i2.2)') k                                               ! to index the filename of power.txt
      if(flplot) then

         open(unit = ipower, file = 'resid_'//filenum//'.txt',status='unknown')
         call writepower(ipower,npts,xx,zzz)                                  ! file to plot of remaining signal

         open(unit = ipower, file = 'power_'//filenum//'.txt',status='unknown')
         call writepower(ipower,nfreq,xfreq,power)                            ! file to plot of periodogram
 
      endif  

!
!     Second step : from the fundamental frequency one searches for over or undertones.
!
!      write(iout, *) pampli, 1/freq(1)
      do kk = 1, ntone_m     ! exploration of undertone

         fbeg_2   = freq(1)/(kk+1) - xwidth*width
         stepf_2  = 2d0*xwidth*width/nfreq_2

         call  one_line(npts,xx,zzz,flunif,fbeg_2,width,nfreq_2,stepf_2,yfreq,qower,xmedp_m,freqmax,ampli)
 
         atone_m(kk) = ampli             ! amplitudes of the undertones
         ftone_m(kk) = freqmax           ! frequency found for the kk_th underdone
!         write(iout, *)  kk,  fbeg_2, 1/freqmax
      enddo
      call getmaxmin(ntone_m, atone_m, xmax, xmin, imax, imin)

!      write(iout, *)  imax, xmax, 1/ftone_m(imax)

      do kk = 1, ntone_p      ! search for overtone
         fbeg_2   = freq(1)*(kk+1) - xwidth*width
         stepf_2  = 2d0*xwidth*width/nfreq_2

         call  one_line(npts,xx,zzz,flunif,fbeg_2,width,nfreq_2,stepf_2,yfreq,qower,xmedp_p,freqmax,ampli)
 
         atone_p(kk) = ampli
         ftone_p(kk) = freqmax
      enddo
      call getmaxmin(ntone_p, atone_p, ymax, ymin, jmax, jmin)

!      write(iout, *)  jmax, ymax, 1/ftone_p(imax)


!
!     Tests to determine whether an undertone line does exist and should be used for the 
!     period of the signal instead of 1/freq(1)
!     One tests the significance of the amplitudes of the undertone lines, by increasing the
!     threshold from first to second undertone, second to third, .. etc
!     For small amplitudes, this is also compared to the amplitudes of the overtone lines
! 
      k = 2

      if((xmax > 0.8d0*ymax).and.(xmax/pampli >0.4)) then      ! significant signal found in undertone 

         freq(k) = ftone_m(imax)
         snr(k)  = xmax/xmedp
         call newamp_lsq(npts,xx,yy,iprint,iout,k,freq,ampc,amps)
         flnormal = .false.                       ! a smaller period than 1/freq(1) very likely
      else
         freq(k) = ftone_p(jmax)
         snr(k)  = ymax/xmedp
         call newamp_lsq(npts,xx,yy,iprint,iout,k,freq,ampc,amps)
         flnormal = .true.                        ! 1/freq(1) is the most likely period
      endif

      write(*,*) ' Frequency search is over successfully '
      if (iprint >=1) then
         write(iout, *)
         write(iout, *)
         write(iout, 241)
         write(iout, 240)
         write(iout, 241)
         call printsol_ext(iout,numfreq,freq,ampc,amps)
         write(iout, *)
         write(iout, *)
      endif

!     ************************************************************
! 


65    format(' Search of the frequency ', i4, ' out of ', i4)

200   format(' -------------------------------')
205   format(' REMOVAL OF THE AVERAGE or TREND      ')
210   format('   Data RMS after removal of the trend :', E14.6)

230   format(' New frequency found from the periodogram : ', E14.6,/)
240   format(' SOLUTION  BEFORE FINAL LEASTSQUARES FIT  ')
241   format(' ---------------------------------------  ')

400   format(//,'   Convergence code found for the line ', i3,' : ', i4)
410   format('   Code = 0   : good convergence, no more attempts', /, &
             '        = 100 : apply non-linear LSQR with good starting values', /,&
             '        = 200 : apply non-linear LSQR with poor starting values ',//)
      return
      end   subroutine periodsearch
!*****************************************************************
      subroutine one_line(npts,x,y,flunif,fbeg,width,nfreq,stepf,xfreq,power,xmedp,freqm,ampli)
!*****************************************************************
!     Periodogram of a time series and identification of the strongest line
!
!     F. Mignard  OCA/Cassiopee  
!     March 2005 & June 2005
!
!*INPUT   
!           npts    : number of data points
!           x[npts] : array with the independant variable (nominally : time)
!           y[npts] : array with the data points y_i
!           flunif  : .true. is regular sampling,  .false. otherwise
!           fbeg    : lower frequency for the periodograms 
!           width   : width in the frequency domain of a spectral line
!           nfreq   : number of frequencies sampled
!           stepf   : stepsize in the frequency domain
!*OUTPUT
!           xfreq   : frequencies of the periodogram
!           power   : periodogram over nfreq
!           xmedp   : median of the power in the periodogram
!           freqm   : frequency of the strongest line in y
!           ampli   : amplitude of the strongest line in y
!***********************************************************************
      implicit none
      integer,       intent(in)    :: npts, nfreq 
      real(kind=dp), intent(in)    :: x(npts), y(npts)
      real(kind=dp), intent(in)    :: fbeg, width, stepf
      logical,       intent(in)    :: flunif
      
      real(kind=dp), intent(out)   :: freqm,ampli,xmedp
      real(kind=dp), intent(out)   :: power(nfreq)
      real(kind=dp), intent(out)   :: xfreq(nfreq)
      integer,       parameter     :: nfreqhr = 100                       ! analysis of the line over nfreqhr closely spaced frequencies
      real(kind=dp), parameter     :: xmul    = 1.6                       ! analysis over the range xmul*width
      real(kind=dp)                :: yfreq(nfreqhr),qower(nfreqhr)
 
      real(kind=dp)                :: freqmax, pmax, stepfhr, fbeghr

      call waves(npts,x,y,flunif,fbeg,nfreq,stepf,xfreq,power) 
      call powermax(nfreq,xfreq,power,freqmax,pmax)                       ! locate the line with largest power
      xmedp    = median(nfreq,power)                                      ! robust mean value of the power spectrum after removal of the contribution of the first k lines
!           
!     high resolution spectra to get the center of the line
!
      stepfhr = xmul*width/nfreqhr                                        ! sampling in frequency
      fbeghr  = max(freqmax - 0.5d0*xmul*width, fbeg)                     ! protection to avoid very low frequencies outside the allowed range

      call waves(npts,x,y,flunif,fbeghr,nfreqhr,stepfhr,yfreq,qower)      ! high resolution periodogram
      call arraymax(nfreqhr,yfreq,qower,freqm,ampli)                      ! precise determination of the frequency

      end subroutine one_line

!***********************************************************************************
      subroutine obsmat (nobs,x,numf,nunk,xfreq,ampc,amps,amat)
!***********************************************************************************
!
!     Observation matrix for the  fitting in the frequency search
!     For each  lines found one determines the amplitude of the cosine and sine terms
!     and the final correction to the frequencies found with FREQSEARCH
! 
! 
!*AUT     F. Mignard OCA/CERGA
!*VER     Version 1, January 2000
!*VER     Version 2, February  2004 with Poisson terms
!
!*INPUT   
!           nobs    : size of the array to be searched in(= number of data points)
!           x       : array of abscissae (nominally time sampling)
!           numf    : number of lines searched   
!           nunk    : number of unknowns (frequencies, amplitudes)
!           xfreq   : array the numf frequencies
!           ampc    : array with the amplitudes of the mixed terms in cosine
!           amps    : array with the amplitudes of the mixed terms in sine
!
!*OUTPUT
!           amat    : observation matrix  amat(nunk,npts) (nunk defined in the program)
!
!*EXTERNALS         : none
!            
! model = Sum_i [a_i*cos(2pi*f_i*t)+b_i*sin(2pi*f_i*t) ]  with a_i : i = 0..numf, b_i : i= 1..numf
!         with a_i  = (alpha_0 +alpha_1*t +alpha_2*t**2  ...)_i with  t**max ==> max = idegf(i)
!         with b_i  = ( beta_0 + beta_1*t + beta_2*t**2  ...)_i with  t**max ==> max = idegf(i)
!
!        a_i dans ampc(l,m) and b_i dans amps(l,m) l: degree of time expansion, m: index of the frequency          
!
! Global variables  : ideg(maxdeg)
!***********************************************************************************
       
      implicit none

      integer,        intent(in)    :: nobs, numf, nunk  
      real(kind=dp),  intent(in)    :: x(*), xfreq(*)  
      real(kind=dp),  intent(in)    :: ampc(0:maxdeg,0:*)
      real(kind=dp),  intent(in)    :: amps(0:maxdeg,0:*)

      real(kind=dp),  intent(out)   :: amat(nunk,*)
            
      integer                       :: k, is, id, i
      real(kind=dp)                 :: cdat, sdat, sumc, sums, fval


      do k = 1, nobs                           ! loop on the data points
         is = 0
         do id = 0, idegf(0)                   ! constant term (zero frequency)
            is = is +1
            amat(is,k) = phi(id,x(k))
         enddo
         do i =1, numf                         ! loop on the lines
            cdat =  cos(deupi*xfreq(i)*x(k))
            sdat =  sin(deupi*xfreq(i)*x(k))
            do id = 0, idegf(i)                ! Poisson term for the cosines
               is = is +1
               amat(is,k)  = phi(id,x(k))*cdat
            enddo
            do id = 0, idegf(i)                ! Poisson term for the sines
               is = is +1
               amat(is,k)  = phi(id,x(k))*sdat
            enddo
            is = is +1
            sumc = 0d0
            sums = 0d0
            do id = 0, idegf(i)
               fval = phi(id,x(k))
               sumc = sumc + ampc(id,i)*fval
               sums = sums + amps(id,i)*fval
            enddo
            amat(is,k)  = deupi*xfreq(i)*x(k)*(-sumc*sdat +sums*cdat)
         enddo
      enddo
      
      return
      end    subroutine obsmat
!***********************************************************************************
       subroutine obsmat_j (nobs,x,numf,nunk,xfreq,ampc,amps,amat)

!***********************************************************************************
!
!     Jacobian matrix for the non-linear leasquares.
!      Routine almost identical to obsmat except the last statement 
!      without xfreq(i) here, as the unknown is freq and not d(freq)/freq
! 
! 
!*AUT     F. Mignard OCA/CERGA
!*VER     Version 1, January 2000
!*VER     Version 2, February  2004 with Poisson terms
!                    February  2005, with bug corrected for the Jacobian matrix
!
!*INPUT   
!           nobs    : size of the array to be searched in(= number of data points)
!           x       : array of abscissae (nominally time sampling)
!           numf    : number of lines searched   
!           nunk    : number of unknowns (frequencies, amplitudes)
!           xfreq   : array the numf frequencies
!           ampc    : array with the amplitudes of the mixed terms in cosine
!           amps    : array with the amplitudes of the mixed terms in sine
!
!*OUTPUT
!           amat    : jacobian matrix  amat(nunk,npts) (nunk defined in the program)
!
!*EXTERNALS         : none
!            
! model = Sum_i [a_i*cos(2pi*f_i*t)+b_i*sin(2pi*f_i*t) ]  with a_i : i = 0..numf, b_i : i= 1..numf
!         with a_i  = (alpha_0 +alpha_1*t +alpha_2*t**2  ...)_i with  t**max ==> max = idegf(i)
!         with b_i  = ( beta_0 + beta_1*t + beta_2*t**2  ...)_i with  t**max ==> max = idegf(i)
!
!        a_i dans ampc(l,m) and b_i dans amps(l,m) l: degree of time expansion, m: index of the frequency          
!
! Global array  : ideg(maxdeg)
!
!***********************************************************************************
       
      implicit none

      integer,        intent(in)    :: nobs, numf, nunk  
      real(kind=dp),  intent(in)    :: x(*), xfreq(*)  
      real(kind=dp),  intent(in)    :: ampc(0:maxdeg,0:*)
      real(kind=dp),  intent(in)    :: amps(0:maxdeg,0:*)

      real(kind=dp),  intent(out)   :: amat(nunk,*)
            
      integer                       :: k, is, id, i
      real(kind=dp)                 :: cdat, sdat, sumc, sums, fval

            
      do k = 1, nobs                           ! loop on the data points
         is = 0
         do id = 0, idegf(0)                   ! constant term (zero frequency)
            is = is +1
            amat(is,k) = phi(id,x(k))
         enddo
         do i =1, numf                         ! loop on the lines
            cdat =  cos(deupi*xfreq(i)*x(k))
            sdat =  sin(deupi*xfreq(i)*x(k))
            do id = 0, idegf(i)                ! Poisson term for the cosines
               is = is +1
               amat(is,k)  = phi(id,x(k))*cdat
            enddo
            do id = 0, idegf(i)                ! Poisson term for the sines
               is = is +1
               amat(is,k)  = phi(id,x(k))*sdat
            enddo
            is = is +1
            sumc = 0d0
            sums = 0d0
            do id = 0, idegf(i)
               fval = phi(id,x(k))
               sumc = sumc + ampc(id,i)*fval
               sums = sums + amps(id,i)*fval
            enddo
            amat(is,k)  = deupi*x(k)*(-sumc*sdat +sums*cdat)    
         enddo
      enddo
      return
      end    subroutine obsmat_j
!******************************************************************************
      subroutine desmat(nobs,x,numf,nunk,xfreq,amat,bmat)
!
!PURPOSE
!     Observation matrix for the initial fitting in the frequency search
!     For each  line  one determines the amplitude of the cosine and sine terms
!     Frequencies are not adjusted in this version.
!
!     The routine is essentially the same as obsmat without the derivatives over frequencies
!
!*AUT     F. Mignard OCA/CERGA
!*VER     Version 1, September 2003
!*VER     Version 2, February  2004 with Poisson terms
!*******************************************************************************
!*INPUT   
!           nobs    : size of the array to be searched in(= number of data points)
!           x       : array of abscissae (nominally time sampling)
!           numf    : number of lines searched   
!           nunk    : number of unknowns (frequencies, amplitudes)
!           xfreq   : array the numf frequencies!
!
!*OUTPUT
!           amat    : observation matrix for the model without frequency fitting
!           bmat    : transpose of amat (for lsqr_svd)
!
!*EXTERNALS         : none
!
! model = Sum_i [a_i*cos(2pi*f_i*t)+b_i*sin(2pi*f_i*t) ]  with a_i : i = 0..numf, b_i : i= 1..numf
!         with a_i  = (alpha_0 +alpha_1*t +alpha_2*t**2  ...)_i with  t**max ==> max = idegf(i)
!         with b_i  = ( beta_0 + beta_1*t + beta_2*t**2  ...)_i with  t**max ==> max = idegf(i)
!
!        a_i dans ampc(l,m) and b_i dans amps(l,m) l: degree of time expansion, m: index of the frequency          
!
! Global array  : ideg(maxdeg)
!
!*******************************************************************************
!      

      implicit none

      integer,        intent(in)    :: nobs, numf, nunk  
      real(kind=dp),  intent(in)    :: x(*), xfreq(*)  

      real(kind=dp),  intent(out)   :: amat(nunk,nobs), bmat(nobs,nunk)
            
      integer                       :: k, is, id, i
      real(kind=dp)                 :: cdat, sdat
      
 
      do k = 1, nobs                     ! loop on the data points
         is = 0
         do id = 0, idegf(0)             ! constant term (zero frequency)
           is = is +1
           amat(is,k) = phi(id,x(k))     ! phi is  a function in the module
         enddo
         do i =1, numf               ! loop on the lines
           cdat =  cos(deupi*xfreq(i)*x(k))
           sdat =  sin(deupi*xfreq(i)*x(k))
           do id = 0, idegf(i)           ! Poisson term for the cosines
              is = is +1
              amat(is,k)  = phi(id,x(k))*cdat
           enddo
          do id = 0, idegf(i)            ! Poisson term for the sines
              is = is +1
              amat(is,k)  = phi(id,x(k))*sdat
          enddo
         enddo
      enddo
      bmat = transpose(amat)
      return
      end   subroutine desmat
!***********************************************************************************
      function func(numf,xfreq,ampc,amps)
!***********************************************************************************
!
!     Function to be minimized by a non linear leastsquares
! 
! 
!*AUT     F. Mignard OCA/CERGA
!*VER     Version 1, January 2000
!         Version 2, April   2004
!
!*INPUT   
!           numf    : number of frequencies used
!           xfreq   : array with the numf frequencies
!           ampc    : array (*,*) with the amplitudes of mixed terms  in cosine for numf frequencies + constant 
!           amps    : array (*,*) with the amplitudes of mixed terms  in sine   for numf frequencies   
!*OUTPUT
!           func    : sum (O-C)^2
!
!*EXTERNALS         : none
!*USE               : module donnees  with the time sampling xx(k) and the observations yy(k)
!            
! model = Sum_i [a_i*cos(2pi*f_i*t)+b_i*sin(2pi*f_i*t) ]  with a_i : i = 0..numf, b_i : i= 1..numf
!         with a_i  = (alpha_0 +alpha_1*t +alpha_2*t**2  ...)_i with  t**max ==> max = idegf(i)
!         with b_i  = ( beta_0 + beta_1*t + beta_2*t**2  ...)_i with  t**max ==> max = idegf(i)
!
!        a_i dans ampc(l,m) and b_i dans amps(l,m) l: degree of time expansion, m: index of the frequency          
!
!******************************************************************************** 

      implicit  none

      integer,        intent(in)    :: numf  
      real(kind=dp),  intent(in)    :: xfreq(*)  

      real(kind=dp),  intent(in)    :: ampc(0:maxdeg,0:*)
      real(kind=dp),  intent(in)    :: amps(0:maxdeg,0:*)

      real(kind=dp)                 :: func
           
      integer                       :: nunk
      real(kind=dp)                 :: resid(npts) ,sum   ! npts : global variable
    
      call model(npts,xx,yy,numf,xfreq,ampc,amps,resid)   ! 12/04/04 xx,yy : global arrays

      sum  = dot_product(resid, resid)
      nunk = isize(numf,idegf)             ! number of unknowns from numf lines with Poisson terms.
      func = sum/(npts - nunk)             !Just to be the same as RMS in leastsquares    

      return
      end function func
!***********************************************************************************
      subroutine printsetting &
      (iout,flsimul,file_in,ncolx,ncoly,file_out,npts,numfreq,flmulti,flauto,frbeg,frend,fltime,threshold)
!***********************************************************************************
!
!     Output of the program settings .
!     if (iout =0)  ==> on the screen
!     if (iout <>0) ==> on the external unit iout open in the main program
! 
! 
!*AUT     F. Mignard OCA/CERGA
!*VER     Version 1, January  2000
!         Version 2, April    2002
!         Version 2, December 2004
!
!*INPUT   
!           iout      : logical unit of the output file (opened before the call)
!           flsimul   : .true. : simulation mode, .false. : data processing
!           file_in   : name of the input file (for flsimul = .false.) 
!           ncolx     : index of column in file_in with the x data (time in general)   
!           ncoly     : index of column in file_in with the y data (your data)   
!           file_out  : name of the output file (for flsimul = .false.) 
!           npts      : number of data points
!           numfreq   : number of frequencies searched (less can be eventually found)
!           flmulti   : flag to search for multiperiodic signal (.T.) or periodic signal (.F.)
!           flauto    : flag for the frequency boundaries (true : determined by the program, false : provided by the user)
!           frbeg     : with flauto = .false. : smallest frequency
!           frend     : with flauto = .false. : highest  frequency
!           fltime    : flag for the offset of the origin of time (true : automatically centered, false : offset with tzero)
!           threshold : thershold in S/N to filter non significant lines
!
!*OUTPUT
!           Printing the setting in the output file
!
!*EXTERNALS         : none
!**********************************************************************************
      implicit none
  
      integer,        intent(in)      :: iout, ncolx, ncoly, npts, numfreq
      real(kind=dp),  intent(in)      :: frbeg, frend, threshold
      logical,        intent(in)      :: flsimul, flauto, fltime, flmulti
      integer,        dimension(8)    :: ivalues

      character*30                    :: file_in,file_out


      call date_and_time(values = ivalues)

      if(iout.eq.0) then
         if(flsimul) then
            write(*,44) 
         else
            write(*,49) file_in,ncolx,ncoly
         endif
         write(*,54) npts
         write(*,*)
         write(*,50) file_out
         write(*,*)
         write(*,57) flmulti
         write(*,*)
         write(*,51) numfreq
         write(*,*)
         write(*,56) fltime
         write(*,*)
         write(*,52) flauto
         write(*,*)
         if (.not. flauto) then
            write(*,521) frbeg
            write(*,522) frend
         endif
         write(*,55) threshold
      else
         write(iout,45)
         write(iout, 46)   ivalues(3),ivalues(2),ivalues(1), ivalues(5), ivalues(6),ivalues(7)
         write(iout,47)
         write(iout,48)
         if(flsimul) then
            write(iout,44) 
         else
            write(iout,49) file_in,ncolx,ncoly
         endif
         write(iout,54) npts
         write(iout,*)
         write(iout,50) file_out
         write(iout,*)
         write(iout,57) flmulti
         write(iout,*)
         write(iout,51) numfreq
         write(iout,*)
         write(iout,56) fltime
         write(iout,*)
         write(iout,52) flauto
         write(iout,*)
         if (.not. flauto) then
            write(iout,521) frbeg
            write(iout,522) frend
         endif
         write(iout,55) threshold
      endif
!$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ 
44    FORMAT(' Run on simulated data ',/)
45    FORMAT(/, ' ****************************************************')
46    FORMAT(   ' *                       FAMOUS                     *' &
               /' *                       ------                     *' &
               /' *  Frequency Analysis Mapping On Unusual Sampling  *' &
               /' *  -         -        -       -  -       -         *' &
               /' *         Program designed and written  by         *' &
               /' *             F. Mignard   OCA/Cassiopee           *' &
               /' *           Version 4.6 - December  2005           *' &
               /' ****************************************************' &
               /' *    Run  made  on  ' , i2.2,'-',I2.2,'-',i4, '  at  ', i2.2,':',i2.2,':',i2.2,    '       *' &
               /' **************************************************** ')

 


47    FORMAT(//,'        SETTINGS OF THE PROGRAM       ')
48    FORMAT('        -----------------------',/)
49    format(' Data are read in the file          : ',A, '   in columns', i3, ' and', i3/)
50    format(' Results are written in the file    : ',A)
57    format(' Multiperiodic (.T.) Periodic (.F.) : '  L3)
51    format(' The number of lines searched is    : ', I3)
52    format(' Freq. auto (.T.) or not (.F.)      : ', L3)
56    format(' Time offset: auto(.T.) or not(.T.) : ', L3)
53    format(' plot (.T.) or not (.T.)            : ', L3)
54    format(' Number of data points found        : ', I5)
521   format(' Preset lower frequency             : ', E10.4)
522   format(' Preset upper frequency             : ', E10.4)
55    format(' S/N threshold for acceptance       : ', F5.1)
!$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ 

      return
      end  subroutine printsetting
!***********************************************************************************
      subroutine printsetting_phot &
      (iout,file_in,ncolx,ncoly, idstar, file_out,npts,numfreq,flmulti,flauto,frbeg,frend,fltime,threshold)
!***********************************************************************************
!
!     Output of the program settings for the variability analysis .
!     if (iout =0)  ==> on the screen
!     if (iout <>0) ==> on the external unit iout open in the main program
! 
!*AUT     F. Mignard OCA/CASIOPEE
!*VER     Version 1, January  2005
!
!*INPUT   
!           iout      : logical unit of the output file (opened before the call)
!           file_in   : name of the input file (for flsimul = .false.) 
!           ncolx     : index of column in file_in with the x data (time in general)   
!           ncoly     : index of column in file_in with the y data (your data)   
!           idstar    : star indentifier
!           file_out  : name of the output file (for flsimul = .false.) 
!           npts      : number of data points
!           numfreq   : number of frequencies searched (less can be eventually found)
!           flmulti   : flag to search for multiperiodic signal (.T.) or periodic signal (.F.)
!           flauto    : flag for the frequency boundaries (true : determined by the program, false : provided by the user)
!           frbeg     : with flauto = .false. : smallest frequency
!           frend     : with flauto = .false. : highest  frequency
!           fltime    : flag for the offset of the origin of time (true : automatically centered, false : offset with tzero)
!           threshold : thershold in S/N to filter non significant lines
!
!*OUTPUT
!           Printing the setting in the output file
!
!*EXTERNALS         : none
!**********************************************************************************
      implicit none
  
      integer,        intent(in)      :: iout, idstar, ncolx, ncoly, npts, numfreq
      real(kind=dp),  intent(in)      :: frbeg, frend, threshold
      logical,        intent(in)      :: flauto, fltime, flmulti
      integer,        dimension(8)    :: ivalues

      character*30                    :: file_in,file_out

      call date_and_time(values = ivalues)

      if(iout.eq.0) then
         write(*,49)  file_in,ncolx,ncoly
         write(*,490) idstar
         write(*,54)  npts
         write(*,*)
         write(*,50)  file_out
         write(*,*)
         write(*,57) flmulti
         write(*,*)
         write(*,51)  numfreq
         write(*,*)
         write(*,56)  fltime
         write(*,*)
         write(*,52)  flauto
         write(*,*)
         if (.not. flauto) then
            write(*,521) frbeg
            write(*,522) frend
         endif
      else
         write(iout,45)
         write(iout, 46)   ivalues(3),ivalues(2),ivalues(1), ivalues(5), ivalues(6),ivalues(7)
         write(iout,47)
         write(iout,48)
         write(iout,49)  file_in,ncolx,ncoly
         write(iout,490) idstar
         write(iout,54)  npts
         write(iout,*)
         write(iout,50)  file_out
         write(iout,*)
         write(iout,57) flmulti
         write(iout,*)
         write(iout,51)  numfreq
         write(iout,*)
         write(iout,56)  fltime
         write(iout,*)
         write(iout,52)  flauto
         write(iout,*)
         if (.not. flauto) then
            write(iout,521) frbeg
            write(iout,522) frend
         endif
         write(iout,55) threshold
      endif
!$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ 
45    FORMAT(/, ' ****************************************************')
46    FORMAT(   ' *                       FAMOUS                     *' &
               /' *                       ------                     *' &
               /' *  Frequency Analysis Mapping On Unusual Sampling  *' &
               /' *  -         -        -       -  -       -         *' &
               /' *         Program designed and written  by         *' &
               /' *             F. Mignard   OCA/Cassiopee           *' &
               /' *           Version 4.6 - December 2005            *' &
               /' ****************************************************' &
               /' *    Run  made  on  ' , i2.2,'-',I2.2,'-',i4, '  at  ', i2.2,':',i2.2,':',i2.2,    '       *' &
               /' **************************************************** ')

47    FORMAT(//,'        SETTINGS OF THE PROGRAM       ')
48    FORMAT('        -----------------------',/)
49    format(' Data are read in the file          : ',A, '   in columns', i3, ' and', i3/)
490   format(' The star ID is                     : ',I6/)
50    format(' Results are written in the file    : ',A)
57    format(' Multiperiodic (.T.) Periodic (.F.) : '  L3)
51    format(' The number of lines searched is    : ', I3)
52    format(' Freq. auto (.T.) or not (.F.)      : ', L3)
56    format(' Time offset: auto(.T.) or not(.F.) : ', L3)
53    format(' plot (.T.) or not (.F.)            : ', L3)
54    format(' Number of data points found        : ', I5)
521   format(' Preset lower frequency             : ', E10.4)
522   format(' Preset upper frequency             : ', E10.4)
55    format(' S/N threshold for acceptance       : ', F5.1)
!$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ 

      return
      end  subroutine printsetting_phot
!***********************************************************************************
      subroutine model(nobs,x,y,numf,xfreq,ampc,amps,resid)
!***********************************************************************************
!
!     Compute the vector of residuals O-C for nlregres
!
!*AUT     F. Mignard OCA/CERGA
!*VER     Version 1, January 2000
!         version 2, March 2004  from FAMOUS V4  onward
!
!*INPUT  
!          nobs     : number of data points
!          x(nobs)  : array with independant variable 
!          y(nobs)  : array of observations 
!          numf     : number of frequencies (at the time of the call)
!          xfreq    : array with the frequencies
!          ampc     : array(0:maxdeg,0:*) with the amplitude of the mixed terms of cosines
!          amps     : array(0:maxdeg,0:*) with the amplitude of the mixed terms of sines
!*OUTPUT
!
!          resid    : array(nobs) of observed - computed values when the model is applied
!
!*EXTERNALS         : none
!
!*USE               : module donnees  with the time sampling x(k) and the observations y(k)
!            
! model = Sum_i [a_i*cos(2pi*f_i*t)+b_i*sin(2pi*f_i*t) ]  with a_i : i = 0..numf, b_i : i= 1..numf
!         with a_i  = (alpha_0 +alpha_1*t +alpha_2*t**2  ...)_i with  t**max ==> max = idegf(i)
!         with b_i  = ( beta_0 + beta_1*t + beta_2*t**2  ...)_i with  t**max ==> max = idegf(i)
!
!        a_i dans ampc(l,m) and b_i dans amps(l,m) l: degree of time expansion, m: index of the frequency          
!
! Global array  : ideg(maxdeg)
!
!***********************************************************************************

      implicit   none

      integer,         intent(in)     :: nobs, numf
      real(kind=dp),   intent(in)     :: x(*), y(*)
      real(kind=dp),   intent(in)     :: ampc(0:maxdeg,0:*) 
      real(kind=dp),   intent(in)     :: amps(0:maxdeg,0:*)
      real(kind=dp),   intent(in)     :: xfreq(*) 

      real(kind=dp),   intent(out)    :: resid(nobs) 
 
      real(kind=dp)                   :: sum, xmod, cdat, sdat
      real(kind=dp)                   :: sumc, sums, val
      integer                         :: k, id, i
      
      do k = 1, nobs
         sum = 0d0
         do id =0, idegf(0)
             sum = sum + ampc(id,0)*phi(id,x(k))
         enddo
         xmod = y(k) -sum
         do i = 1, numf
            cdat =  cos(deupi*xfreq(i)*x(k))
            sdat =  sin(deupi*xfreq(i)*x(k))
            sumc = 0d0
            sums = 0d0
            do id = 0, idegf(i)
               val  = phi(id,x(k))
               sumc = sumc + ampc(id,i)*val
               sums = sums + amps(id,i)*val
            enddo
            xmod =  xmod - sumc*cdat - sums*sdat       
         enddo
         resid(k) = xmod
      enddo  
      return
      end   subroutine model
!***********************************************************************************
      subroutine jacob(nobs,x,numf,xfreq,ampc,amps,nunk,xjacob)
!***********************************************************************************
!
!     Compute the jacobian matrix of the model for nlregres
!
!*AUT     F. Mignard OCA/CERGA
!*VER     Version 1, January 2000
!         Version 2, April 2004 for FAMOUS V4 onward
!
!*INPUT  
!          nobs     : number of data points
!          x        : array with the independant variable (in general the time)
!          numf     : number of frequencies (at the time of the call)
!          xfreq    : array with the frequencies
!          ampc     : array(0:maxdeg,0:*) with the amplitude of the mixed terms of cosines
!          amps     : array(0:maxdeg,0:*) with the amplitude of the mixed terms of sines
!          nunk     : number of unknowns
!*OUTPUT
!
!      xjacob(nobs,nunk): jacobian matrix  d(model_i/dxunk_j)  
!
!*EXTERNALS         : none
!
!*USE               : module donnees  with the time sampling x(k) and the observations y(k)
!            
! model = Sum_i [a_i*cos(2pi*f_i*t)+b_i*sin(2pi*f_i*t) ]  with a_i : i = 0..numf, b_i : i= 1..numf
!         with a_i  = (alpha_0 +alpha_1*t +alpha_2*t**2  ...)_i with  t**max ==> max = idegf(i)
!         with b_i  = ( beta_0 + beta_1*t + beta_2*t**2  ...)_i with  t**max ==> max = idegf(i)
!
!        a_i dans ampc(l,m) and b_i dans amps(l,m) l: degree of time expansion, m: index of the frequency          
!
!***********************************************************************************

      implicit  none

      integer,        intent(in)      :: nobs, numf, nunk
      real(kind=dp),  intent(in)      :: x(*), xfreq(*)
      real(kind=dp),  intent(in)      :: ampc(0:maxdeg,0:*) 
      real(kind=dp),  intent(in)      :: amps(0:maxdeg,0:*)

      real(kind=dp),  intent(out)     :: xjacob(nobs,nunk)

      real(kind=dp)                   :: amat(nunk,nobs)

      
      call  obsmat_j(nobs,x,numf,nunk,xfreq,ampc,amps,amat)

      xjacob = -transpose(amat)               ! should be -transpose. Tests on (13/04/04)
      return
      end     subroutine jacob
!***********************************************************************************
      subroutine fcn(nobs,nunk,xunk,resid,xjacob,nobsm,iflag)
!***********************************************************************************
!
!     Compute the vector of residuals O-C and the jacobian matrix for nl_lsqr (= lmder1).
!     Verstion to be used with lmder1 in f77
!     kept in this module for further testing, but not used at the moment
!     The order of the variables is determined by the interface of the Levenberg-Marquardt module.
!
!*AUT     F. Mignard OCA/CERGA
!*VER     Version 1, Feburary 2002
!         version 2, April 2004 for FAMOUS V4 onward
!
!*INPUT  
!          nobs     : number of data points
!          nunk     : number of unknowns
!          xunk     : array with the values of the unknowns
!          nobsm    : size of the 2nd dimension of xjacob in  the calling program
!          iflag    : iflag = 1 ==> compute the residual, iflag =2 ==> compute the jacobian
!*OUTPUT
!
!          resid    : array of observed - computed values when the model is applied
!          xjacob   : jacobian matrix  d(model_i/dxunk_j)  
!
!*EXTERNALS         : none
!
!*USE               : module donnees  with the time sampling x(k) and the observations y(k)
!            
! model = Sum_i [a_i*cos(2pi*f_i*t)+b_i*sin(2pi*f_i*t) ]  with a_i : i = 0..numf, b_i : i= 1..numf
!         with a_i  = (alpha_0 +alpha_1*t +alpha_2*t**2  ...)_i with  t**max ==> max = idegf(i)
!         with b_i  = ( beta_0 + beta_1*t + beta_2*t**2  ...)_i with  t**max ==> max = idegf(i)
!
!        a_i dans ampc(l,m) and b_i dans amps(l,m) l: degree of time expansion, m: index of the frequency          
!
! Global array  : ideg(maxdeg)
!
!***********************************************************************************

      implicit none

      integer,       intent(in)     :: nobs, nunk, nobsm
      real(kind=dp), intent(in)     :: xunk(*)
      integer,       intent(in)     :: iflag

      real(kind=dp), intent(out)    :: resid(nobs), xjacob(nobsm,nunk)


      real(kind=dp), allocatable    :: xfreq(:), ampc(:,:), amps(:,:)
      integer                       :: numf      

      numf = inumf(nunk,idegf)        ! number of actual frequencies for nunk fitted parameters
      
      allocate(ampc(0:maxdeg,0:numf),amps(0:maxdeg,0:numf),xfreq(numf))

      call sol2amp(numf,xunk,xfreq,ampc,amps)
      if(iflag==1) then
         call  model(nobs,xx,yy,numf,xfreq,ampc,amps,resid)      ! xx, yy global arrays
      elseif (iflag==2) then
         call  jacob(nobs,xx,numf,xfreq,ampc,amps,nunk,xjacob)
      endif
      return
      end subroutine fcn
!***********************************************************************************
      subroutine gcn(nobs,nunk,xunk,resid,xjacob,iflag)
!***********************************************************************************
!
!     Compute the vector of residuals O-C and the jacobian matrix for nl_lsqr (= lmder1).
!     Verstion to be used with lmder1 in f90
!
!     The order and the list of the variables are determined by the interface of the Levenberg-Marquardt module.
!
!*AUT     F. Mignard OCA/CASSIOPEE

!*VER     Version 1, Feburary 2002
!         version 2, April 2004 for FAMOUS V4 onward
!
!*INPUT  
!          nobs     : number of data points
!          nunk     : number of unknowns
!          xunk     : array with the values of the unknowns
!          iflag    : iflag = 1 ==> compute the residual, iflag =2 ==> compute the jacobian
!*OUTPUT
!
!          resid    : array of observed - computed values when the model is applied
!          xjacob   : jacobian matrix  d(model_i/dxunk_j)  
!
!*EXTERNALS         : none
!
!            
! model = Sum_i [a_i*cos(2pi*f_i*t)+b_i*sin(2pi*f_i*t) ]  with a_i : i = 0..numf, b_i : i= 1..numf
!         with a_i  = (alpha_0 +alpha_1*t +alpha_2*t**2  ...)_i with  t**max ==> max = idegf(i)
!         with b_i  = ( beta_0 + beta_1*t + beta_2*t**2  ...)_i with  t**max ==> max = idegf(i)
!
!        a_i dans ampc(l,m) and b_i dans amps(l,m) l: degree of time expansion, m: index of the frequency          
!
! Global array  : ideg(maxdeg)
!! 
!***********************************************************************************

      implicit none

      integer,  intent(in)       :: nobs, nunk
      real(dp), intent(in)       :: xunk(nunk)   
      real(dp), intent(inout)    :: resid(nobs) 
      real(dp), intent(out)      :: xjacob(nobs,nunk) 
      integer,  intent(inout)    :: iflag

      real(kind=dp), allocatable :: xfreq(:), ampc(:,:), amps(:,:)
      integer                    :: numf   
      numf = inumf(nunk,idegf)        ! number of actual frequencies for nunk fitted parameters
      
      allocate(ampc(0:maxdeg,0:numf),amps(0:maxdeg,0:numf),xfreq(numf))

      call sol2amp(numf,xunk,xfreq,ampc,amps)

      if(iflag==1) then
         call  model(nobs,xx,yy,numf,xfreq,ampc,amps,resid)
      elseif (iflag==2) then
         call  jacob(nobs,xx,numf,xfreq,ampc,amps,nunk,xjacob)
      endif
      return
      end subroutine gcn
!***********************************************************************************
      subroutine freqsol(nobs,x,y,iprint,iresid,iout,numf,freq,snr,ampc,amps,rms)
!***********************************************************************************
!     Final treatment of the frequency search. The program performs the 
!     last non-linear fitting with max accuracy and determines the
!     formal standard deviations of the unknowns through an evaluation of the covariance matrix
!
!     Caution : the SDs are scaled with the rms of the residuals. So their magnitudes may
!     reflect the inadequacy of the model rather than the statistical noise.
!
!     The non significant or redundant lines are also filtered iteratively.
! 
! *********************************************************************************************
! 
!*AUT     F. Mignard OCA/CERGA
!*VER     Version 1, February 2002
!*VER     Version 2, September 2003
!         Version 3, April     2004 with Poisson terms
!                    Final Levenberg-Marquart fitting
!                    Estimate of the covariance matrix of the unknowns
!                    Estimate of the residuals 
!         Version 4  February 2005
!                    Automatic filtering of non significant lines
!                    Identification and removal of the ghost lines
!
!     Calling sequence :
!
!          call freqsol(nobs,x,y,iprint,iresid,iout,numf,freq,snr,ampc,amps,rms)
!
!*INPUT   
!           nobs    : size of the array to be searched in(= number of data points)
!           x      : array of abscissae (nominally time sampling)
!           y      : array of data points 
!           iprint  :  control of the output  from the final LS
!                       0  : only error messages and RMS of residuals during iteration
!                       1  : 0+ short output (solution, correlation) during iterations
!                       2  : 0+ extended output during iterations
!           iresid  :  control the computation and output of the residuals
!                       1  : residuals are printed
!                       0  : not printed
!           iout    : logical output unit  
!                     In many fortan implementation the UNIT =6 is the default for the screen
!                     if the unit is not open to a file
!                     Thus to get the output on the screen : set IOUT =6, without OPEN(6 ..) in the main.
!
!IN/OUT
!           numf    : number of lines searched (IN) and found(OUT) 
!                     could be less than the setting because of rejections of non significant lines   
!           freq    : array of frequencies found
!           snr     : array with the signal/noise of each line
!           ampc    : array with the amplitudes of cosine terms  (ampc(0) = cte term)
!           amps    : array with the amplitudes of sine terms
!                     initially  freq, ampc, amps  contain the starting values
!                     on exit they contain the final solution
!
!*OUTPUT
!           rms     : array with the rms of the unknowns
!
!
!*EXTERNALS         : newfreq_lmd, newfreq_lsq,printout, amp2sol 
!            
!***********************************************************************************
      implicit none

      integer,         intent(in)     :: nobs, iprint, iresid, iout
      real(kind=dp),   intent(in)     :: x(nobs), y(nobs)
     
      integer,         intent(inout)  :: numf
      real(kind=dp),   intent(inout)  :: freq(*), snr(*)
      real(kind=dp),   intent(inout)  :: ampc(0:maxdeg,0:*), amps(0:maxdeg,0:*)
      
      real(kind=dp),   intent(out)    :: rms(*)

      real(kind=dp),   parameter      :: tol  = 1d-12         ! tolerance for Levenberg LSQR
      integer,         parameter      :: ipower = 99          ! unit for the output of the residuals
 
      real(kind=dp)                   :: resid(nobs), z(nobs), rqm

      integer                         :: idrej(numf)
      logical                         :: flrej(numf)
      integer                         :: ipprint, ierr, nrej, kk


!
!     Final Levenberg-Marquardt with high accuracy (tol)
!
      call newfreq_lmd(nobs,ipprint,iout,tol,numf,freq,ampc,amps)    ! nonlinear leastsquares on the k frequencies (added on 3/02/2002)
!
!     Estimate of the RMS   + printouts
!

      write(iout,*)
      write(iout,*)
      write(iout, 335)
      write(iout, 336)

      ipprint = iprint/2
      call newfreq_final(nobs,x,y,ipprint,iout,numf,freq,ampc,amps,rms,rqm,ierr)       ! nonlinear leastsquares on the k frequencies (added on 3/02/2002)

      call printout (iout,numf,freq,ampc,amps,rms,snr,rqm,ierr)
!
!     filtering out non significant lines from the S/N or statistical significance
!     this is an iterative processing until all the lines are statistically significant
!
      do
         print *, 'filtering'
         call filtering(numf, snr, freq,ampc, amps, rms, flrej,idrej,nrej)             !nrej lines are rejected
         write(iout, *)

         if(nrej==0) then                 ! filtering 
            write(iout, 550)  
         else if (nrej==1) then
            write(iout,555) nrej
            write(iout,556) (idrej(kk), kk=1, nrej)
            write(iout,560)
            write(iout,561)
         else     
            write(iout,555) nrej
            write(iout,557) (idrej(kk), kk=1, nrej)
            write(iout,560)
            write(iout,561)
         endif

         if((nrej >0)) then
            call newval(numf,flrej,freq,ampc,amps,snr)                                 ! updated values after filtering
            numf = numf - nrej
            call newfreq_lmd(nobs,ipprint,iout,tol,numf,freq,ampc,amps)                ! nonlinear leastsquares on the k frequencies (added on 3/02/2002)
            call newfreq_final(nobs,x,y,iprint,iout,numf,freq,ampc,amps,rms,rqm,ierr)  ! nonlinear leastsquares on the k frequencies (added on 3/02/2002)
            call printout (iout,numf,freq,ampc,amps,rms,snr,rqm,ierr)
         endif
         if(nrej == 0) exit
      enddo

!
!     filtering out redundant lines (two lines with nu_2-nu_1 < spectral line width)
!     this is an iterative processing until lines in the final representation are well separated
!

      do
         call ghostlines(numf,freq, snr, flrej,idrej,nrej)      !nrej lines are rejected
         write(iout, *)
         if(nrej==0) then                 ! filtering 
            write(iout, 650)  
         else if (nrej==1) then
            write(iout,655) nrej
            write(iout,556) (idrej(kk), kk=1, nrej)
            write(iout,560)
            write(iout,561)
         else     
            write(iout,655) nrej
            write(iout,557) (idrej(kk), kk=1, nrej)
            write(iout,560)
            write(iout,561)
         endif
         if(nrej >0) then
            call newval(numf,flrej,freq,ampc,amps,snr)                                 ! updated values after filtering
            numf = numf - nrej
            call newfreq_lmd(nobs,ipprint,iout,tol,numf,freq,ampc,amps)                ! nonlinear leastsquares on the k frequencies (added on 3/02/2002)
            call newfreq_final(nobs,x,y,iprint,iout,numf,freq,ampc,amps,rms,rqm,ierr)  ! nonlinear leastsquares on the k frequencies (added on 3/02/2002)
            call printout (iout,numf,freq,ampc,amps,rms,snr,rqm,ierr)
         endif
         if(nrej == 0) exit
      enddo
!
!     output of residuals
!
      if(iresid == 1) then
         call model(nobs,x,y,numf,freq,ampc,amps,resid)                              !  12/04/04
         open(unit = ipower, file = 'resid_final.txt',status='unknown')
         z = x + toffset                                                             ! shift to the origin of time tmean : global variable
         call writepower(ipower,npts,z,resid)                                        ! file to plot of remaining signal
      endif


! 
!     ******************* FORMATS *****************************************
! 
200   format( ' RMS of residuals wrt. complete model : ',  E20.12,//)
205   format( ' RMS of residuals wrt. linearized model after iteration ', i3,' :',  E25.15)
210   format( ' RMS of residuals wrt. complete   model after iteration ', i3,' :',  E25.15,//)
335   format('           FINAL SOLUTION  AFTER NON LINEAR FIT  ')
336   format('           ------------------------------------  ',/)


450   format('        FINAL RESIDUALS AFTER LS FIT')
451   format('        ----------------------------  ',/)
550   format(' No line has been rejected from the significance test ')
555   format(' Number of lines rejected  from the significance test :', I4,//)
650   format(' No line has been rejected from the spectral resolution test ')
655   format(' Number of lines rejected  from the spectral resolution test :', I4,//)
556   format(' Line  rejected  is # :', I4,//)
557   format(' Lines rejected are # ', 20(', ',I4),//)
560   format(//,'        FINAL SOLUTION AFTER REJECTION')
561   format('        ------------------------------',/)

      return
      end   subroutine freqsol
!***********************************************************************************
      function isize(numf,ideg)
!***********************************************************************************
!     PURPOSE
!     Number of unknowns in the representation of a quasi periodic signal with mixed terms of various degrees.
!     Version 1 February 2004  
!     F. Mignard OCA/Cassiopee
!
!     INPUT
!           numf    : number of frequencies  
!           ideg    : array(0:numf) of the maximum power of the time variable for each frequency 
!     OUPTUT
!           isize   : integer  :: number of unknowns with numf frequencies and degree ideg(k) for each of them
!****************************************************************************
      implicit none
      integer,   intent(in)   ::  numf
      integer,   intent(in)   ::  ideg(0:numf) 

      integer                 ::  isize, is, id
            
      is = ideg(0) +1                   ! terms of zero frequency
      do id =1, numf           
         is = is + 2*(ideg(id) +1)+1    ! sine + cosine amplitudes  + frequencies
      enddo
            
      isize = is
      return
      end function isize  
!***********************************************************************************
      function inumf(nunk,ideg)
!***********************************************************************************
!     PURPOSE
!     Number of frequencies in the representation of a quasi periodic signal with mixed terms of various degrees.
!     One starts from the number of free parameters, the degree of each time polynomial in each frequency to derive the
!     number of lines.
!     inumf is the inverse function of isize
!
!     Version 1 February 2004  
!     F. Mignard OCA/Cassiopee
!
!     INPUT
!           nunk    : number of free parameters 
!           ideg    : array(0:numf) of the maximum power of the time variable for each frequency 
!     OUPTUT
!           inumf   : integer (number of line, without the zero frequency line)
!****************************************************************************
      implicit none

      integer,   intent(in)   :: nunk;
      integer,   intent(in)   :: ideg(0:*) 

      integer                 :: numf
      integer                 :: inumf, isum
      
      numf = -1
      isum = -1
      do while (isum <nunk)  
         numf = numf +1      
         isum = isize(numf,ideg)
      enddo       
      if(isum > nunk) then
         print *, ' error in function inumf, isum too large'
         print *, ' nunk =', nunk, 'numf =', numf
         print *, ' program stopped'
         stop
      else
         inumf = numf
      endif
      return
      end  function inumf

!***********************************************************************************
      subroutine amp2sol(numf,freq,ampc,amps,sol)
!****************************************************************************
!     PURPOSE
!     transformation from the represention in frequencies and amplitudes to the unique array SOL
!     for all the unknowns, including frequencies.
!     Version 1 September 2003  no mixed terms
!     Version 2 February  2004   with mixed terms (t^p cos  t^p sin)
!     F. Mignard OCA/Cassiopee
!
!     INPUT
!           numf    : number of frequencies  
!           freq    : array(numf) of frequencies found
!           ampc    : array(0:maxdeg,0:numf) with the amplitudes of cosine terms  (ampc(0) = cte term)
!           amps    : array(0:maxdeg,0:numf) with the amplitudes of sine terms
!     OUPTUT
!           sol     : array(2(sum (ideg +1))+ numf)
!                     sol(0:ideg(0))     for ampc(0:ideg(0),0)
!                     sol(3*k-1) for ampc(k)
!                     sol(3*k)   for amps(k)
!                     sol(3*k+1) for freq(k)
!****************************************************************************
    
      implicit none
      integer,       intent(in)   :: numf
      real(kind=dp), intent(in)   :: freq(*) 
      real(kind=dp), intent(in)   :: ampc(0:maxdeg,0:*), amps(0:maxdeg,0:*)
 
      real(kind=dp), intent(out)  :: sol(*)
      
      integer                     :: is, id, k
      
      is = 0          ! counter for the number of unknowns
      do id = 0, idegf(0)
         is = is +1
         sol(is) = ampc(id,0)
      enddo
      do k=1, numf
         do id = 0, idegf(k)
            is = is +1
            sol(is) =  ampc(id,k)  
         enddo
         do id = 0, idegf(k)
            is = is +1
            sol(is) =  amps(id,k)  
         enddo
         is = is +1
         sol(is) =   freq(k)  
      enddo
      return
      end   subroutine amp2sol
!***********************************************************************************
      subroutine sol2amp(numf,sol,freq,ampc,amps)
!***********************************************************************************
!
!****************************************************************************
!     PURPOSE
!     transformation from the represention in array SOL of all the unknowns to the representation
!     in frequencies and amplitudes.
!     Version 1 September 2003
!     Version 2 February  2004   with mixed terms (t^p cos  t^p sin)
!     F. Mignard OCA/Cassiopee
!****************************************************************************
!     INPUT
!           numf    : number of frequencies  
!           sol     : array(2(sum (ideg +1))+ numf)
!                     sol(0:ideg(0))     for ampc(0:ideg(0),0)
!                     sol(3*k-1) for ampc(k)
!                     sol(3*k)   for amps(k)
!     OUPTUT
!           ampc    : array(0:maxdeg,0:numf) with the amplitudes of cosine terms  (ampc(0) = cte term)
!           amps    : array(0:maxdeg,0:numf) with the amplitudes of sine terms 
!           freq    : array(numf) of frequencies found
!****************************************************************************
      
      implicit none
      integer,         intent(in)   ::  numf
      real(kind=dp),   intent(in)   ::  sol(*)

      real(kind=dp),   intent(out)  :: freq(*) 
      real(kind=dp),   intent(out)  :: ampc(0:maxdeg,0:*), amps(0:maxdeg,0:*)


      integer                       :: is, id, k
      
      is = 0          ! counter for the number of unknowns
 
      do id = 0, idegf(0)
         is = is + 1
         ampc(id,0) = sol(is)  
         amps(id,0) = 0d0  
      enddo
      do k=1, numf
         do id = 0, idegf(k)
            is = is +1
            ampc(id,k) = sol(is)    
         enddo
         do id = 0, idegf(k)
            is = is +1
            amps(id,k)  = sol(is)   
         enddo
         is = is +1
         freq(k) = sol(is)  
      enddo

      return
      end   subroutine sol2amp
!***********************************************************************************
      subroutine xsol2amp(numf,xsol,freq,ampc,amps)
!***********************************************************************************
!
!****************************************************************************
!     PURPOSE
!     Application of the correction supplied by the  linear least square solution
!     to the amplitudes and frequencies of the model.
!     The unknwonws are the variation of the amplitudes and the relative shift in frequency.
!     This is determined by the construction of amat in the subroutine Obsmat.
!     Version 1 February  2004   with mixed terms (t^p cos  t^p sin)
!     F. Mignard OCA/Cassiopee
!****************************************************************************
!     INPUT
!           numf    : number of frequencies  
!           xsol    : array with all the corrections to be applied
!                     
!     INPUT/OUPTUT  : intial and final amplitudes and frequencies
!           ampc    : array(0:maxdeg,0:numf) with the amplitudes of cosine terms  (ampc(0) = cte term)
!           amps    : array(0:maxdeg,0:numf) with the amplitudes of sine terms 
!           freq    : array(numf) of frequencies found
!****************************************************************************
      
 
      implicit none
      integer,         intent(in)     :: numf
      real(kind=dp),   intent(in)     :: xsol(*)

      real(kind=dp),   intent(inout)  :: freq(*) 
      real(kind=dp),   intent(inout)  :: ampc(0:maxdeg,0:*), amps(0:maxdeg,0:*)


      integer                         :: is, id, k
     
      is = 0          ! counter for the number of unknowns
 
      do id = 0, idegf(0)
         is = is + 1
         ampc(id,0) = ampc(id,0)+ xsol(is)       ! update of the zero frequency terms
         amps(id,0) = 0d0  
      enddo
      do k=1, numf
         do id = 0, idegf(k)
            is = is +1
            ampc(id,k) = ampc(id,k) + xsol(is)   ! ampc update 
         enddo
         do id = 0, idegf(k)
            is = is +1
            amps(id,k) = amps(id,k) + xsol(is)   ! amps update  
         enddo
         is = is +1
         freq(k) = freq(k)*(1d0+ xsol(is))  !frequency update (variable = delta f/f)
      enddo

      return
      end  subroutine xsol2amp

!***********************************************************************************
      subroutine solshort2amp(numf,sol,ampc,amps)
!***********************************************************************************
!
!****************************************************************************
!     PURPOSE
!     transformation from the represention in array SOL of all the unknowns to the representation
!     in frequencies and amplitudes.
!     Version 1 September 2003
!     Version 2 February  2004   with mixed terms (t^p cos  t^p sin)
!     F. Mignard OCA/Cassiopee
!****************************************************************************
!     INPUT
!           numf    : number of frequencies  
!           sol     : array(2(sum (ideg +1))+ numf)
!                     sol(0:ideg(0))     for ampc(0:ideg(0),0)
!                     sol(3*k-1) for ampc(k)
!                     sol(3*k)   for amps(k)
!     OUPTUT
!           ampc    : array(0:maxdeg,0:numf) with the amplitudes of cosine terms  (ampc(0) = cte term)
!           amps    : array(0:maxdeg,0:numf) with the amplitudes of sine terms 
!****************************************************************************
 
      implicit none
      integer,         intent(in)   ::  numf
      real(kind=dp),   intent(in)   ::  sol(*)

      real(kind=dp),   intent(out)  :: ampc(0:maxdeg,0:*), amps(0:maxdeg,0:*)

      integer                       :: is, id, k
     
      is = 0          ! counter for the number of unknowns
 
      do id = 0, idegf(0)
         is = is + 1
         ampc(id,0) = sol(is) 
         amps(id,0) = 0d0 
      enddo
      do k=1, numf
         do id = 0, idegf(k)
            is = is +1
            ampc(id,k) = sol(is)    
         enddo
         do id = 0, idegf(k)
            is = is +1
            amps(id,k)  = sol(is)   
         enddo
      enddo

      return
      end  subroutine solshort2amp

!****************************************************************************
      subroutine filtering(numf,snr,freq, ampc, amps, rms, flrej,idrej,nrej)
!****************************************************************************
!
!     PURPOSE
!     In the frequency fitting one removes the lines with statistically 
!     non significant power
!
!     Version 1. September 2003
!     Version 2. January   2004
!     Version 3. November  2005   with filter on negative frequencies and rms
!
!     F. Mignard OCA/CASSIOPEE
!****************************************************************************
!     INPUT
!           numf    : number of lines searched   
!           snr     : array with the S/N of each line
!           freq    : array with the frequencies found
!           ampc    : array with amplitude of poisson terms in cosine
!           amps    : array with amplitude of poisson terms in sine
!           rms     : array with the RMS of all the unknowns fitted
!     OUTPUT
!          
!           flrej   : logical array with for each line :.false. : no rejection, .true. : line rejected
!           idrej   : indices of rejected lines among the initial numf lines
!           nrej    : number  of rejected lines
!****************************************************************************
      implicit none

      integer,       intent(in)    :: numf
      real(kind=dp), intent(in)    :: snr(*), freq(*), rms(*)
      real(kind=dp), intent(in)    :: ampc(0:maxdeg,0:numf), amps(0:maxdeg,0:numf)

      integer,       intent(out)   :: idrej(*), nrej
      logical,       intent(out)   :: flrej(*)

      real(kind=dp)                :: ratio_sn, sig, amp, ratio_sig
      integer                      :: k

      real(kind=dp)                :: sigf(numf)

      real(kind=dp)                :: sigc(0:maxdeg,0:numf), sigs(0:maxdeg,0:numf)
      
      call sol2amp(numf,rms,sigf,sigc,sigs)
  
      nrej = 0
      do k = 1, numf
         sig  = sqrt(sigc(0,k)**2 + sigs(0,k)**2)
         amp  = sqrt(ampc(0,k)**2 + amps(0,k)**2)
         ratio_sig = amp/sig            ! significance of the signal in sdandard deviations
         ratio_sn = snr(k)              ! level of detection of the line

         if((freq(k) >0).and.(ratio_sn > threshold).and.(ratio_sig> 1.5d0)) then     ! threshold is a global variable of the module obtained from the settings
            flrej(k) = .false.          ! not rejected 
         else
            nrej     = nrej +1
            flrej(k) =  .true.          ! this line must be rejected
            idrej(nrej) = k 
         endif 
      enddo
      return
      end  subroutine filtering
!****************************************************************************
      subroutine ghostlines(numf,freq,snr,flrej,idrej,nrej)
!****************************************************************************
!
!     PURPOSE
!     In the frequency fitting one removes the ghost lines resulting
!     from the incomplete orthogonality of the subspace obtained after
!     the removal of lines already found. This generates ghost lines at
!     a frequency nearly identical to previous lines.
!     One goes through the list of frequencies and searches for pairs
!     of nearly identical frequencies. The fainter is removed in the subsequent
!     fit.
!     Version 1. February 2005
!     Version 2. November 2005 corrected for the case where the same line is found twice
!
!     F. Mignard OCA/CASSIOPEE
!****************************************************************************
!     INPUT
!           numf    : number of lines searched   
!           freq    : array of frequencies found
!           snr     : array with the S/N of each line
!     OUTPUT
!          
!           flrej   :  logical array with for each line :.false. : no rejection, .true. : line rejected
!           idrej   : indices of rejected lines among the initial numf lines
!           nrej    : number of rejected lines
!****************************************************************************
     implicit none

      integer,       intent(in)    :: numf
      real(kind=dp), intent(in)    :: freq(numf), snr(numf)

      integer,       intent(out)   :: idrej(*), nrej
      logical,       intent(out)   :: flrej(numf)

      real(kind=dp)                :: dfreq, sfreq(numf)
      integer                      :: ind(numf), k
 

      nrej = 0
      flrej = .false.                                  ! no line assumed to be rejected
      sfreq = freq                                     ! to save the initial array from quicksort
      call quicksort(numf,sfreq,ind)
      do k = 2 , numf
         dfreq = (sfreq(k)- sfreq(k-1))/freqres        ! freqres : max frequency resolution (global variable)
         if(dfreq < 1.50d0) then                        ! ghost line found => 2 lines with delta_freq < half line_width 
             if(snr(ind(k-1)) < snr(ind(k))) then      ! removes the line of less signifance
                flrej(ind(k-1)) = .true.
             else
                flrej(ind(k))   = .true.
             endif
         endif
      enddo

      nrej = 0                                         !FM 05/11/05  for this block
      do k = 1, numf           
         if(flrej(k)) then
            nrej        = nrej +1
            idrej(nrej) = k
         endif
      enddo
      return
      end  subroutine ghostlines

!****************************************************************************
      subroutine newval(numf,flrej,freq,ampc,amps,snr)
!****************************************************************************
!     Purpose :
!     update the values in the solution after filtering the non significant lines
!     or the gohst lines.
!     Lines are removed and the related arrays with the frequencies are
!     amplitudes are reshuffled accordingly (i.e. moved upward)
!     Version 1. February 2005
!
!     F. Mignard OCA/CASSIOPEE
!****************************************************************************
!     INPUT
!           numf    : number of lines in the solution before filtering   
!           flrej   : logical array indicating what lines have been rejected
!
!     INPUT/OUTPUT
!          
!           freq    : array of frequencies found           before and after lines removal
!           snr     : array with the S/N of each line          "              "
!           ampc    : array with the amplitude of the cosines  "              "
!           amps    : array with the amplitudes of the sines   "              "
!****************************************************************************
!

      implicit none

      integer,        intent(in)        :: numf
      logical,        intent(in)        :: flrej(*)

      real(kind=dp),  intent(inout)     :: freq(*), snr(*) 
      real(kind=dp),  intent(inout)     :: ampc(0:maxdeg,0:*), amps(0:maxdeg,0:*)

      integer                           :: nl, k 
 
      nl = 0
      do k = 1,numf
         if(.not.flrej(k)) then
            nl = nl+1                        ! nl always <= k
            freq(nl)          = freq(k)
            ampc(0:maxdeg,nl) = ampc(0:maxdeg,k)
            amps(0:maxdeg,nl) = amps(0:maxdeg,k)
            snr(nl)           = snr(k)
         endif
      enddo
      end subroutine newval 
!
!****************************************************************************
      subroutine printout(iout,numf, freq,ampc, amps, rms,snr,rqm,irms)
!****************************************************************************
!
!     PURPOSE
!     Final printout when all the frequencies have been found and fitted to the data
!     Version 1 September 2003
!     Version 2 April     2004
!     F. Mignard OCA
!****************************************************************************
!     INPUT
!           iout    : logical output unit  
!                     In many fortan implementation the UNIT =6 is the default for the screen
!                     if the unit is not open to a file
!                     Thus to get the output on the screen : set IOUT =6, without OPEN(6 ..) in the main.
!           numf    : number of lines searched   
!           freq    : array of frequencies found
!           ampc    : array with the amplitudes of cosine terms  (ampc(0) = cte term)
!           amps    : array with the amplitudes of sine terms
!           rms     : standard errors on freq, ampc, amps
!           snr     : array with the S/N of each line
!           rqm     : mean quadratic residual (this is the square)
!           irms    : 0 : rms can be trusted ; 100 : solution not linearly stable rms doubtful
!     OUTPUT
!****************************************************************************
      implicit none

      integer,         intent(in)    :: iout, numf, irms
      real(kind=dp),   intent(in)    :: freq(*)
      real(kind=dp),   intent(in)    :: ampc(0:maxdeg,0:*), amps(0:maxdeg,0:*)
      real(kind=dp),   intent(in)    :: rms(*), snr(*)
      real(kind=dp),   intent(in)    :: rqm

      real(kind=dp),   parameter     :: zero    = 0d0
      real(kind=dp),   parameter     :: small   = 5d-3

      real(kind=dp)                  :: sigf(numf)
      real(kind=dp)                  :: sigc(0:maxdeg,0:numf), sigs(0:maxdeg,0:numf)
      real(kind=dp)                  :: xvaln, xresn
      integer                        :: k, id


      xvaln = sqrt(func(numf,freq,ampc,amps))    ! full model 12/04/04

      xresn = sqrt(rqm)                          ! linear model
      
      call sol2amp(numf,rms,sigf,sigc,sigs)
      
      sig_rel_f(1:numf)   = sigf(1:numf)         ! sig_rel_f  : global array  size numfreq >= numf       

      write(iout, *)
      if(abs(xvaln-xresn)/xvaln >small) then     !test the final convergence
         write(iout,420)
         write(iout,400)
         write(iout,405) xvaln
         write(iout,406) xresn
         write(iout,420)
      else
         write(iout,420)
         write(iout,410)
         write(iout,405) xvaln
         write(iout,406) xresn
         write(iout,420)
      endif
      write(iout, *)

      if(irms ==100 ) then                      !test the linear stability of the solution
         write(iout,520)
         write(iout,500)
         write(iout,520)
      else
         write(iout,520)
         write(iout,510)
         write(iout,520)
      endif

      write(iout, *)
      write(iout, *)
      write(iout, 342)    
      write(iout, 343)
      write(iout, 344)
      write(iout, 345)
      write(iout, 346)
      write(iout, 347) toffset
      write(iout, 350)
      do k=0, numf
         if(k.eq.0) then
            do id =0, idegf(0)
                write(iout,299) k, id,  zero, ampc(id,k), sigc(id,k), ampc(id,k)
            enddo
         else
            do id = 0, idegf(k)
               if(id==0) then
                  write(iout,300) k,id, freq(k),1d0/freq(k),ampc(id,k), amps(id,k),& 
                  sigf(k), sigc(id,k), sigs(id,k), &
                  sqrt(ampc(id,k)**2+amps(id,k)**2), raddeg*modulo(atan2(-amps(id,k),ampc(id,k)),deupi),&
                  snr(k)
               else
                  write(iout,310)   id , ampc(id,k), amps(id,k),& 
                  sigc(id,k), sigs(id,k), &
                  sqrt(ampc(id,k)**2+amps(id,k)**2), raddeg*modulo(atan2(-amps(id,k),ampc(id,k)),deupi)     ! convention :: cos(wt+phi)
               endif
            enddo
         endif
      enddo
      write(iout,*)

!
!     FORMATS
!
300   format(i4, '  t^',i1,es16.8,es16.8,2es16.8,3es11.3,es13.6,F13.7,es10.2)
310   format(4x,'  t^',i1,32x,2es16.8,11x, 2es11.3,es13.6,F13.7)

299   format(i4,'  t^',i1,es16.8,16x,es16.8,27x,es11.3,11x,es13.6)
340   format('        SOLUTION  AFTER FINAL LS FIT')
341   format('        ----------------------------  ',/)
342   format(' - Solution given as ( A*cos(omega*t) + B*sin(omega*t)  or  amp*cos(omega*t+phi)  ')
343   format('   for each term  A= a0 or a1*t or a2*t^2 (resp. for B ) ',//)
344   format(' - Frequencies in cycles/unit of time of the input data',//)
345   format(' - Periods in the same unit of time as the input data',//)
346   format(' - Amplitudes in the same unit as Y(t) in the input data',//)
347   format('   ***  Origin of time in the following solution : ',E17.9,//)

350   format(9x, '      Frequency  ', '     Period  ',  '      cos term   ', '     sine term   ',&
                 ' sigma(f)/f', ' sigma(cos) ', 'sigma(sin)', '  amplitude  '  ,  '  phase(deg)',&
                 '      S/N ', /)
405   format('  *  rms full     model :', e15.6,14x,            '  *')
406   format('  *  rms linear   model :', e15.6,14x,            '  *')
420   format('  ******************************************************* ')
400   format('  * CAUTION : the linearisation is ill-conditioned      * ' ,/,&
             '  *           results are sensitive to settings         * ')

410   format('  * The linearized solution has properly converged      * ',/,&
             '  * You can trust the following solution                * ')                       

520   format('  ******************************************************* ')
500   format('  * CAUTION : the linearization solution is unstable    * ' ,/,&
             '  *           the sigmas may be meaningless             * ')

510   format('  * The linearized solution  is stable                  * ',/,&
             '  * You can trust the evaluation of the sigmas          * ')                       


      return
      end  subroutine printout
!****************************************************************************
      subroutine printsol(iout,numf, freq,ampc, amps)
!****************************************************************************
!
!     PURPOSE
!     Final printout when all the frequencies have been found and fitted to the data
!     Version 1 September 2003
!     Version 2 April     2004
!     F. Mignard OCA
!****************************************************************************
!     INPUT
!           iout    : logical output unit  
!                     In many fortan implementation the UNIT =6 is the default for the screen
!                     if the unit is not open to a file
!                     Thus to get the output on the screen : set IOUT =6, without OPEN(6 ..) in the main.
!           numf    : number of lines searched   
!           freq    : array of frequencies found
!           ampc    : array with the amplitudes of cosine terms  (ampc(0) = cte term)
!           amps    : array with the amplitudes of sine terms
!     OUTPUT
!****************************************************************************
     implicit none

      integer,         intent(in)    :: iout, numf
      real(kind=dp),   intent(in)    :: freq(*)
      real(kind=dp),   intent(in)    :: ampc(0:maxdeg,0:*), amps(0:maxdeg,0:*)

      real(kind=dp),   parameter     :: zero    = 0d0
      integer                        :: k, id


      write(iout, *)
      do k=0, numf
         if(k.eq.0) then
            do id =0, idegf(0)
                write(iout,299) k, id,  zero, ampc(id,k)
            enddo
         else
            do id = 0, idegf(k)
               if(id==0) then
                  write(iout,300) k,id, freq(k),1d0/freq(k),ampc(id,k), amps(id,k),& 
                  sqrt(ampc(id,k)**2+amps(id,k)**2)
               else
                  write(iout,310)   id , ampc(id,k), amps(id,k)
               endif
            enddo
         endif
      enddo
      write(iout,*)

!
!     ******************* FORMATS *****************************************
!
299   format(i4,i4,E14.6,12x,E14.6,38x,e11.3)
300   format(i4,i4,E14.6,E12.4,2e14.6,E13.6,3e11.3)
310   format(4x,i4,26x,2e14.6)

      return
      end  subroutine printsol
!****************************************************************************
      subroutine printsol_ext(iout,numf, freq,ampc, amps)
!****************************************************************************
!
!     PURPOSE
!     Final printout when all the frequencies have been found and fitted to the data
!     Version 1 September 2003
!     Version 2 April     2004
!     Version 3 September 2004  with extended formats
!     F. Mignard OCA
!****************************************************************************
!     INPUT
!           iout    : logical output unit  
!                     In many fortan implementation the UNIT =6 is the default for the screen
!                     if the unit is not open to a file
!                     Thus to get the output on the screen : set IOUT =6, without OPEN(6 ..) in the main.
!           numf    : number of lines searched   
!           freq    : array of frequencies found
!           ampc    : array with the amplitudes of cosine terms  (ampc(0) = cte term)
!           amps    : array with the amplitudes of sine terms
!     OUTPUT
!****************************************************************************
     implicit none

      integer,         intent(in)    :: iout, numf
      real(kind=dp),   intent(in)    :: freq(*)
      real(kind=dp),   intent(in)    :: ampc(0:maxdeg,0:*), amps(0:maxdeg,0:*)

      real(kind=dp),   parameter     :: zero    = 0d0
      integer                        :: k, id


      write(iout, *)
      write(iout, 250)
      do k=0, numf
         if(k.eq.0) then
            do id =0, idegf(0)
                write(iout,299) k, id,  zero, ampc(id,k)
            enddo
         else
            do id = 0, idegf(k)
               if(id==0) then
                  write(iout,300) k,id, freq(k),1d0/freq(k),ampc(id,k), amps(id,k),& 
                  sqrt(ampc(id,k)**2+amps(id,k)**2)
               else
                  write(iout,310)   id , ampc(id,k), amps(id,k)
               endif
            enddo
         endif
      enddo
      write(iout,*)

!
!     ******************* FORMATS *****************************************
!
250   format(8x, '     Frequency  ', '      Period  ',  '      cos term   ', '      sine term   ', '    power   ',/)
299   format(i4,i4,es16.8,16x,es16.8)
300   format(i4,i4,es16.8,es16.8,2es16.8,es14.6)
310   format(4x,i4,32x,2es16.8)

      return
      end   subroutine printsol_ext
!**********************************************************************************************
      SUBROUTINE newfreq_lmd(nobs,iprint,iout,tol,numf,freq,ampc,amps)
!*********************************************************************************************
!
!     Leastsquares fit of a quasi-periodic signal with numf frequencies
!     to the times series YY(t_k) with t_k = XX(k)
!
!     The number of frequencies is fixed to numf and the approximate frequencies
!     are known.
!     A least squares fit is carried out on the data with the model :
!     S(t) = Sum (a_i*cos(2pi nu_i t) + b_i*sin (2pi nu_i t) 
!     where the adjusted parameters are the ammlitudes (with time polynomials) and
!     the frequenceis 
! 
!     From initial amplitudes and frequencieus the program returns updated values.
! 
! 
!     --- ALGORITHM ---
! 
!     A Levenberg-Marquardt oprimization searches systematically around the starting point.
!     
! 
! *********************************************************************************************
! 
!*AUT     F. Mignard OCA/CERGA
!*VER     Version 1, February 2002
!*VER     Version 2, November 2004
!
!     Calling sequence :
!
!           call newfreq_lmd(nobs,iprint,iout,tol,numf,freq,ampc,amps)
!
!*INPUT   
!           nobs    : size of the array to be searched in(= number of data points)
!           iprint  :  control of the output  from the non-linear LS
!                       0  : no printout produced after execution
!                       1  : summary output of the execution
!                       2  : 1 + solutions found
!
!           iout    : logical output unit  
!                     In many fortan implementation the UNIT =6 is the default for the screen
!                     if the unit is not open to a file
!                     Thus to get the output on the screen : set IOUT =6, without OPEN(6 ..) in the main.
!           tol     : tolerence for the convergence (~ dimensionless relative error; typical =1E-7 to 1E-14)
!           numf    : number of lines searched   
!
!IN/OUT
!           freq    : array of frequencies found
!           ampc    : array with the amplitudes of cosine terms  (ampc(0) = cte term)
!           amps    : array with the amplitudes of sine terms
!                     initially  freq, ampc, amps  contain the starting values
!                     on exit they contain the final solution
!
!
!*EXTERNALS         : LMDER1
!
!*********************************************************************************************

      use Levenberg_Marquardt

      implicit none

      integer,         intent(in)    :: nobs, iprint, iout, numf
      real(kind=dp),   intent(in)    :: tol
      real(kind=dp),   intent(inout) :: freq(*), ampc(0:maxdeg,0:*), amps(0:maxdeg,0:*)

      real(kind=dp),   parameter     :: zero    = 0d0
      integer                        :: nunk, lwa, info
      
      real(kind=dp),   allocatable   :: sol(:), xjacob(:,:), wwa(:)
      integer,         allocatable   :: ipvt(:)

      real(kind=dp)                  :: resid(nobs), xvaln
          
!     
!     Additional settings
!
      nunk    = isize(numf,idegf)         ! number of unknowns from numf lines with Poisson terms.

      lwa     = 5*nunk+nobs
      
      allocate(sol(nunk),xjacob(nobs,nunk),ipvt(nunk),wwa(lwa))

!
!     Initial vector of unknowns
!
      call amp2sol(numf,freq,ampc,amps,sol)
       
!
!     Non  linear least-squares   + printouts
!

!      call lmder1(fcn,nobs,nunk,sol,resid,xjacob,nobs,&     ! f77 version using fcn
!                    tol,info,ipvt,wwa,lwa)

      call lmder1(gcn,nobs,nunk,sol,resid,xjacob,&           ! F90 versio using gcn 15/04/04
                    tol,info,ipvt)
!
!     update of the solution
!                   
      call sol2amp(numf,sol,freq,ampc,amps)                  ! 12/04/04  
      xvaln = sqrt(func(numf,freq,ampc,amps))                ! 12/04/04
!

      if (iprint.gt.0) then
         write(iout, *)
         write(iout, 240)
         write(iout, 241)
         write(iout, 250)
         call printsol(iout,numf,freq,ampc,amps)
         write(iout, 200) xvaln
      endif
! 
!     ******************* FORMATS *****************************************
! 
200   format( '   RMS of residuals  wrt. full  model  :',  E14.6,/)
240   format('        SOLUTION  AFTER LEVENBERG-MARQUARDT FIT  ')
241   format('        ---------------------------------------  ',/)
250   format(4x, '    Frequency  ', '   Period  ',  '    cos term   ', '   sine term   ', '    power   ',/)

      return
      end SUBROUTINE newfreq_lmd
!**********************************************************************************************
      SUBROUTINE newamp_lsq(nobs,x,y,iprint,iout,numf,freq,ampc,amps)
! *********************************************************************************************
!
!     Iterative Leastsquares fit of a quasi-periodic signal with numf frequencies
!     to the times series YY(t_k) with t_k = XX(k)
!     The frequencies are fixed and the amplitudes (with time polynomials) are fitted.
!     The numf-1 approximated amplitudes are also known.
!
!     Linear least squares solution on k lines 
!     This allows to determine the amplitudes to be used as starting values
!     for the non linear fitting where the frequencies are finetuned.
!
!
!     From initial amplitudes the program returns updated values.
! 
! 
!     --- ALGORITHM ---
! 
!     Newton-Raphson method with control of convergence.
!     
! 
! *********************************************************************************************
! 
!*AUT     F. Mignard OCA/CERGA
!*VER     Version 1, September 2003
!
!     Calling sequence :
!
!           call newamp_lsq(nobs,x,y,iprint,iout,numf,freq,ampc,amps)
!
!*INPUT   
!           nobs    : size of the array to be searched in(= number of data points)
!           x       : array of abscissae (nominally time sampling)
!           y       : array of data points 
!           iprint  :  control of the output  from the non-linear LS
!                       0  : no printout produced after execution
!                       1  : summary output of the execution
!                       2  : 1 + solutions found
!
!           iout    : logical output unit  
!                     In many fortan implementation the UNIT =6 is the default for the screen
!                     if the unit is not open to a file
!                     Thus to get the output on the screen : set IOUT =6, without OPEN(6 ..) in the main.
!           numf    : number of lines searched  
!
!IN/OUT
!           freq    : array of frequencies found
!           ampc    : array with the amplitudes of cosine terms  (ampc(0) = cte term)
!           amps    : array with the amplitudes of sine terms
!                     initially  freq, ampc, amps  contain the starting values
!                     on exit they contain the final solution
!
!
!*EXTERNALS         : DESMAT,LSQR,AMP2SOL,MODEL
!*********************************************************************************************
      implicit none

      integer,         intent(in)    :: nobs, iprint, iout, numf
      real(kind=dp),   intent(in)    :: x(*), y(*)
      real(kind=dp),   intent(inout) :: freq(*), ampc(0:maxdeg,0:*), amps(0:maxdeg,0:*)

      integer                        :: nunk, ipprint, irank
      
      real(kind=dp),   allocatable   :: amat(:,:),bmat(:,:), cor(:,:)
      real(kind=dp),   allocatable   :: ampli(:), rms(:),    wsvd(:)
      real(kind=dp)                  :: resid(nobs), poids(nobs), rqm

      integer,         parameter     :: ipoid   = 0    ! unweighted equations option
 

      nunk  =  isize(numf,idegf)-numf                                 ! number of unknowns with k given frequencies not fitted here.

      allocate (amat(nunk,npts),bmat(npts,nunk),cor(nunk,nunk), rms(nunk), ampli(nunk), wsvd(nunk)) ! dynamical allocation
          
!
!     Linear least squares solution on k lines 
!     This allows to determine the amplitudes to be used as starting values
!     for the non linear fitting where the frequencies are finetuned.
!

      poids = 1d0
      ipprint = iprint/2     ! to override the iprint of the call list

      call desmat(npts,x,numf,nunk,freq,amat,bmat)                 ! design matrix for the linear least squares on k lines

      call  LSQR_SVD(nobs,nunk,iout, bmat,y,poids,iprint,&         !   lsqr solver
                     ampli,cor,rms,resid,rqm,irank,wsvd)      

      call solshort2amp(numf,ampli,ampc,amps)                      ! assignement from ampli to ampc, amps

      return
      end SUBROUTINE newamp_lsq

!**********************************************************************************************
      SUBROUTINE newfreq_lsq(nobs,x,y,iprint,iout,tol,numf,freq,ampc,amps,ierr)
! *********************************************************************************************
!
!     Iterative Leastsquares fit of a quasi-periodic signal with numf frequencies
!     to the times series YY(t_k) with t_k = XX(k)
!
!     The number of frequencies is fixed to numf and the approximate frequencies
!     and amplitudes are known.
!     An iterative least squares fit is carried out on the data with the model :
!     S(t) = Sum (a_i*cos(2pi nu_i t) + b_i*sin (2pi nu_i t) 
!     where the adjusted parameters are the 3*numf+1 unknowns : 
!     a_0,  a_i, b_i, nu_i  i = 1 .. numf
! 
!     From initial amplitudes and phases the program returns updated values.
! 
! 
!     --- ALGORITHM ---
! 
!     Newton-Raphson method with control of convergence.
!     
! 
! *********************************************************************************************
! 
!*AUT     F. Mignard OCA/CERGA
!*VER     Version 1, September 2003
!
!     Calling sequence :
!
!           call newfreq_lsq(nobs,x,y,iprint,iout,tol,numf,freq,ampc,amps,ierr)
!
!*INPUT   
!           npts    : size of the array to be searched in(= number of data points)
!           x       : array of abscissae (nominally time sampling)
!           y       : array of data points 
!           iprint  :  control of the output  from the non-linear LS
!                       0  : no printout produced after execution
!                       1  : summary output of the execution
!                       2  : 1 + solutions found
!
!           iout    : logical output unit  
!                     In many fortan implementation the UNIT =6 is the default for the screen
!                     if the unit is not open to a file
!                     Thus to get the output on the screen : set IOUT =6, without OPEN(6 ..) in the main.
!           tol     : tolerence for the convergence (~ dimensionless relative error; typical =1E-7 to 1E-14)
!           numf    : number of lines searched  
!
!IN/OUT
!           freq    : array of frequencies found
!           ampc    : array with the amplitudes of cosine terms  (ampc(0) = cte term)
!           amps    : array with the amplitudes of sine terms
!                     initially  freq, ampc, amps  contain the starting values
!                     on exit they contain the final solution
!
!*OUTPUT
!           ierr    : error code for convergence (0 : convergence OK, 100 : poor convergence, 200 : no convergence,  )
!
!*EXTERNALS         : DESMAT,LSQR,AMP2SOL,MODEL
!
!*********************************************************************************************
      implicit none

      integer,         intent(in)    :: nobs, iprint, iout, numf
      real(kind=dp),   intent(in)    :: x(*), y(*), tol
      real(kind=dp),   intent(inout) :: freq(*), ampc(0:maxdeg,0:*), amps(0:maxdeg,0:*)
      integer,         intent(out)   :: ierr

      integer                        :: nunk, ipprint, iter, irank
      
      real(kind=dp)                  :: resid(nobs), poids(nobs), zzz(nobs)     
      real(kind=dp)                  :: xresn, xvaln, xval, xres, sc
      
      real(kind=dp),   allocatable   :: sol(:), rms(:), amat(:,:), bmat(:,:)
      real(kind=dp),   allocatable   :: cor(:,:), xsol(:),wsvd(:)
 
      logical                        :: stop0,stop1, stop2,stop3,stop4

      real(kind=dp),   parameter     :: zero    = 0d0
      integer,         parameter     :: itermax = 5    ! max number of iterations allowed
      integer,         parameter     :: ipoid   = 0    ! unweighed equations option
      
!     
!     Additional settings
!
      nunk    = isize(numf,idegf)         ! number of unknowns from numf lines with Poisson terms.

      allocate(sol(nunk),rms(nunk),amat(nunk,nobs),bmat(nobs,nunk),cor(nunk,nunk),xsol(nunk),wsvd(nunk))

!
!     Non  linear least-squares   + printouts
!

      write(*,*) ' Start of non linear regression on frequencies  '
      poids = 1d0
      ipprint = iprint/2     ! to override the iprint of the call list
      iter  = 0
      xresn = 0d0
      xvaln = 0d0
10       continue     ! iteration loop
            iter = iter +1
            xval = xvaln
            xres = xresn
            call  obsmat(nobs,x,numf,nunk,freq,ampc,amps,amat) 
            bmat = transpose(amat)                                        ! structure of amat designed for LSQR and not LSQR_LVD

            call  model(nobs,x,y,numf,freq,ampc,amps,zzz)                 ! 12/04/04
            xvaln = sqrt(func(numf,freq,ampc,amps))                       ! full model 12/04/04  


            call  LSQR_SVD(nobs,nunk,iout, bmat,zzz,poids,ipprint,&       ! SVD lsqr solver  10/09/04
                    xsol,cor,rms,resid,sc,irank,wsvd)


            call xsol2amp(numf,xsol,freq,ampc,amps)                       ! 12/04/04

            xvaln = sqrt(func(numf,freq,ampc,amps))                       ! full model 12/04/04   
            xresn = sqrt(sc)

            stop1 = iter.gt.1
            stop2 = abs((xvaln-xval)/xvaln).lt.tol      ! convergence
            stop3 = abs((xresn-xres)/xresn).lt.tol      ! convergence
            stop4 = abs((xresn-xvaln)/xvaln).lt.0.05d0  ! agreement between linear and non-linear solution
            stop0 = (stop1.and.stop2.and.stop3.and.stop4)

         if(iter <itermax.and..not.stop0) go to 10  ! termination or continuation
         write(*,*) ' End of non linear regression on frequencies  '
         if((iter ==itermax).and.(.not.stop4)) then
            ierr  = 200             ! non convergence
         else if((iter==itermax).and.(stop4)) then
            ierr  = 100             ! near convergence
         else
            ierr = 0                ! good convergence
         endif
!
!      Output
!
      if (iprint.gt.0) then 
         write(iout, *)
         if(numf==1) then 
            write(iout, 231)   
            write(iout, 230) numf 
            write(iout, 231)   
         else
            write(iout, 236)   
            write(iout, 235) numf
            write(iout, 236)   
         endif
            
         write(iout, *)
         write(iout, 240)
         write(iout, 241)
         write(iout, 250)
         
         call printsol(iout,numf,freq,ampc,amps)

         write(iout, 200) xresn
      endif
! 
!     ******************* FORMATS *****************************************
! 
230   format( ' SOLUTION WITH  ', I4, ' FREQUENCY' )
231   format( ' -----------------------------' )
235   format( ' SOLUTION WITH  ', I4, ' FREQUENCIES' )
236   format( ' -------------------------------' )
200   format( '   RMS of residuals  wrt. lin.  model  :',  E14.6,/)
240   format('        SOLUTION  AFTER NON LINEAR LEASTSQUARES FIT  ')
241   format('        -------------------------------------------  ',/)
250   format(4x, '    Frequency  ', '   Period  ',  '    cos term   ', '   sine term   ', '    power   ',/)


      return
      end  SUBROUTINE newfreq_lsq
!**********************************************************************************************
      SUBROUTINE newfreq_final(nobs,x,y,iprint,iout,numf,freq,ampc,amps,rms,rqm,ierr)
! *********************************************************************************************
!
!     Estimate of the RMS of the solution from a linear leastsquare methods
!
!     The solution is not changed in this routine. The LSVD solver is just run
!     to obtain a proper estimate of the RMS.
!     They are scaled on the rms of the residuals, meaning that the formal
!     error may primarily reflect an unsufficient modelling.
! 
! 
!     --- ALGORITHM ---
! 
!     SVD leastsquares .
!     
! 
! *********************************************************************************************
! 
!*AUT     F. Mignard OCA/CERGA
!*VER     Version 1, September 2003
!*VER     Version 2, February  2005
!
!     Calling sequence :
!
!           call newfreq_final(nobs,x,y,iprint,iout,numf,freq,ampc,amps,rms,rqm,ierr)
!
!*INPUT   
!           nobs    : size of the array to be searched in(= number of data points)
!           x       : array of abscissae (nominally time sampling)
!           y       : array of data points 
!           iprint  :  control of the output  from the non-linear LS
!                       0  : no printout produced after execution
!                       1  : summary output of the execution
!                       2  : 1 + solutions found
!
!           iout    : logical output unit  
!                     In many fortan implementation the UNIT =6 is the default for the screen
!                     if the unit is not open to a file
!                     Thus to get the output on the screen : set IOUT =6, without OPEN(6 ..) in the main.
!           numf    : number of lines searched  
!
!IN
!           freq    : array of frequencies found
!           ampc    : array with the amplitudes of cosine terms  (ampc(0) = cte term)
!           amps    : array with the amplitudes of sine terms
!                     initially  freq, ampc, amps  contain the starting values
!                     on exit they contain the final solution
!
!*OUTPUT
!           rms     : standard deviations of freq,amps, amps
!           rqm     : man quadratic residual of the linear model ( sum(res_k^2)/(nobs-neq))
!           ierr    : error code for convergence (0 : convergence OK, 100 : ill conditioned system)
!
!*EXTERNALS         : DESMAT,LSQR,AMP2SOL,MODEL
!
!*********************************************************************************************
      implicit none

      integer,         intent(in)    :: nobs, iprint, iout, numf
      real(kind=dp),   intent(in)    :: x(*), y(*)
      real(kind=dp),   intent(inout) :: freq(*), ampc(0:maxdeg,0:*), amps(0:maxdeg,0:*)
      real(kind=dp),   intent(out)   :: rms(*), rqm
      integer,         intent(out)   :: ierr

      integer                        :: nunk, ipprint, irank
      
      real(kind=dp)                  :: resid(nobs), poids(nobs), zzz(nobs)     
      real(kind=dp)                  :: xresn, xvaln
      
      real(kind=dp),   allocatable   :: amat(:,:), bmat(:,:)
      real(kind=dp),   allocatable   :: cor(:,:), xsol(:),wsvd(:)
 

      real(kind=dp),   parameter     :: zero    = 0d0
      integer,         parameter     :: ipoid   = 0    ! unweighted equations option
     
!     
!     Additional settings
!
      nunk    = isize(numf,idegf)       ! number of unknowns from numf lines with Poisson terms.
 
      allocate(amat(nunk,nobs),bmat(nobs,nunk),cor(nunk,nunk),xsol(nunk),wsvd(nunk))

      write(*,*) ' Start of the linearity testing  '

      poids = 1d0
      ipprint = iprint/2     ! to override the iprint of the call list

      call  obsmat(nobs,x,numf,nunk,freq,ampc,amps,amat) 

      bmat = transpose(amat)                                        

      call model(nobs,x,y,numf,freq,ampc,amps,zzz)                  ! zzz is the rhs of the linear model 12/04/04
      xvaln = sqrt(func(numf,freq,ampc,amps))                       ! full model residual 12/04/04  

      call  LSQR_SVD(nobs,nunk,iout, bmat,zzz,poids,iprint,&        ! SVD lsqr solver to get the rms
            xsol,cor,rms,resid,rqm,irank,wsvd)
 
      xresn = sqrt(rqm)                                             ! residual linear model     
 
      write(*,*) ' End of rms evaluation in frequencies in newfreq_final '

      if(irank < 0.95*nunk) then                                    ! margin when there are many  unknowns
         ierr  = 100                                                ! ill conditioned system
      else
         ierr = 0                  
      endif

!      Output
!
      if(iprint.gt.0) then
         if(numf==1) then
            write(iout, 210) numf
         else
            write(iout, 211) numf
         endif
         write(iout, 200) xvaln
      endif

      if (iprint.gt.0) then     
         write(iout, *)
         write(iout, 240)
         write(iout, 241)
         write(iout, 250)
         
         call printsol(iout,numf,freq,ampc,amps)
      endif
! 
!     ******************* FORMATS *****************************************
! 
200   format( '   RMS of residuals  wrt. lin.  model  :',  E14.6,/)
210   format( ' Non  linear  leastsquares over :', i3,  ' frequency')
211   format( ' Non  linear  leastsquares over :', i3,  ' frequencies')
240   format('        SOLUTION ooo AFTER NON LINEAR LEASTSQUARES FIT  ')
241   format('        -------------------------------------------  ',/)
250   format(4x, '    Frequency  ', '   Period  ',  '    cos term   ', '   sine term   ', '    power   ',/)

      return
      end  subroutine newfreq_final
!******************************************************
      function fp(x)
!******************************************************
!
!     fp    : function fractional part of x
!     0 <= fp(x)  <1   with x > 0 or  < 0
!
!     F. Mignard  december 1998
!
!     fp( 3.14)  = 0.14
!     fp(-3.14)  = 0.86
!     fp( 2.71)  = 0.71
!     fp(-2.71)  = 0.29
!******************************************************
      implicit none

      real(kind=dp)              :: fp
      real(kind=dp), intent(in)  :: x
!
      if((x-int(x)).eq.0) then
         fp =   0.
      else
         fp = x - floor(x)
      endif      
      return
      end function fp


!***********************************************************************************
      subroutine numobs(luin, nrec)
!***********************************************************************************
!
!     read a text file on the unit luin to determine the number of records
!
!     luin   :  logical unit of the file
!     nrec   :  number of records found
!
!***********************************************************************************
      implicit none
      integer  luin, k , nrec
      real     aa

      k = 0
5     continue
         read(luin, *,end=500)  aa   ! useful to read a number to avoid counting empty lines with cr at the end of the file
         k = k+1
      go to 5
500   continue
      nrec = k
      rewind(luin)
      end subroutine numobs
!*************************************************************************
      subroutine timebase(npts, xx, xmean, xmed, hrange, xm1, zz)
!************************************************************************* 
!PURPOSE
!   Othonormal polynomial (discrete Legendre polynomials) for the time series
!   given in the array xx(npts)
!   Only the t^0, t^1 and t^2 are made orthormal.
!   For higher degrees one used  a representation of xx(.) in -1, +1 instead.
!   with mean(xx)= 0
!   With x in -1 to 1 if
!   p_0 = A_0
!   p_1 = a_1 + b_1 z
!   p_2 = a_2 + b_2 z + c_2 z^2
!   then p_0, p_1, p_2 are orthonormal with the discrete distribution x_i  when
!   a_0 =1
!   a_1 = 0   b_1 = 1/sig^2
!   a_2 =
!   b_2 =
!   c_2 =
!   In this version not every computed  variable appears in the call list.
!   This will be used when orthogonal polynomials will replace the simle time
!   time polynomial in further versions of Famoulib.
!
!   F. Mignard OCA 
!   Version 1 : September 2003
!
!
!*************************************************************************
!INPUT
!      npts   : number of data points
!      xx     : array xx(npts) of the time sampling (increasing or decreasing order)
!
!OUTPUT
!      xmean  : mean of xx(.)
!      xmed   : middle of xx(:)
!      hrange : half range ::  0.5(tmax - tmin)
!      xm1    : mean of zz(:)
!      zz     : same as xx but shifted and scaled to be in -1, +1 
!
!************************************************************************* 
      implicit none

      integer,       intent(in)  :: npts
      real(kind=dp), intent(in)  :: xx(npts)

      real(kind=dp), intent(out) :: xmean, xmed, hrange, xm1
      real(kind=dp), intent(out) :: zz(npts)

      real(kind=dp)              :: xmax, xmin
      real(kind=dp)              :: xm2, xm3, xm4
      real(kind=dp)              :: beta_1, alpha_2, beta_2, gamma_2

      integer                    :: imax, imin

      call getmaxmin(npts, xx, xmax, xmin, imax, imin)

      hrange  = 0.5d0*(xmax - xmin)
      xmed    = 0.5d0*(xmax + xmin)

      xmean   = sum(xx)/npts
      zz      = (xx-xmed)/hrange           ! z(.) in -1, 1

      xm1     = sum(zz)/npts
      xm2     = sum(zz*zz)/npts
      xm3     = sum(zz*zz*zz)/npts
      xm4     = sum(zz*zz*zz*zz)/npts

      beta_1  = 1d0/xm2
      gamma_2 = 1d0/sqrt(xm4-xm2*xm2-xm3*xm3/xm2)
      alpha_2 = -gamma_2*xm2
      beta_2  = -gamma_2*xm3/xm2


      return
      end subroutine timebase
!**************************************************************************
      function seconds(x)
!**************************************************************************
!     This function returns the elapsed time since the time x
!     x : number of seconds since 0h in the system clock
!     seconds(0.0d0) : number of seconds elapsed since 0h of the system clock
!     accuracy : 0.001 s
!
!     F. Mignard  OCA/Cassiopee
!     20 March 2005
!
!     INPUT
!        x     : time offset since 0h in seconds
!
!     OUTPUT
!     seconds  : elapsed time since x in seconds
!
!***************************************************************************
      implicit none

      integer,   dimension(8)   :: ivalues
      real(kind=dp)             :: seconds, x

      call date_and_time(values=ivalues)

      seconds = 3600d0*ivalues(5)+60d0*ivalues(6)+ivalues(7) +0.001d0*ivalues(8) - x

      return
      end function seconds
!*************************************************************************
      subroutine  value_poly(tau,kdeg,beta1,alpha2,beta2,gamma2,valpoly)
!************************************************************************* 
!PURPOSE
!   Value of the  othonormal polynomial (discrete Legendre polynomials) 
!   built on a time series. (they are orthonormal up to degree 2)
! 
!   p_0 = 1
!   p_1 = beta1*tau
!   p_2 = alpha2 + beta2*tau +gamma2*tau^2
!   p_k = tau^k
!   In the routine the polynomials are given by the coefficients.
!   tau is the independant variable in -1, 1
!   Not used in this version of Famouslib
!
!   F. Mignard OCA
!   Version 1 : September 2003
!
!
!*************************************************************************
!INPUT
!      tau    : reduced time ( in -1, 1)
!      kdeg   : maxim degree of the evaluation  (could be zero)
!      beta1  : coefficient degree  one of P1  (alpha1 = 0 with centered variable)
!      alpha2 : coefficient degree zero of P2
!      beta2  : coefficient degree  one of P2
!      gamma2 : coefficient degree  two of P2
!
!OUTPUT
!      valpoly: valpoly(0:kdeg) values of the polynomials
!
!************************************************************************* 
      implicit none
 
      integer,       intent(in)   :: kdeg
      real(kind=dp), intent(in)   :: tau, beta1, alpha2, beta2, gamma2
      real(kind=dp), intent(out)  :: valpoly(0:*)

      integer                     :: k

      valpoly(0) = 1
      valpoly(1) = beta1*tau
      valpoly(2) = alpha2 + tau*(beta2 +gamma2*tau)
      do k = 3, kdeg
         valpoly(k) = tau**k
      enddo
      return
      end  subroutine  value_poly
!*************************************************************************
      function phi(kdeg,x)
!*************************************************************************
! 
!     preliminary function giving the power of the sampling time
!     will be replaced by orthogonal polynomials 
!  
!INPUT
!      kdeg   : maximum degree of the evaluation  (could be zero)
!      x      : value of the time
!
!OUTPUT
!      phi    : x^k
!
!************************************************************************* 
      implicit none
 
      integer,       intent(in)   :: kdeg
      real(kind=dp), intent(in)   :: x

      real(kind=dp)               :: phi

      select case (kdeg)
      case (0) 
        phi = 1d0
      case(1)
        phi = x
      case(2)
        phi = x*x
      case(3)
        phi = x*x*x
      case default
        phi = x**kdeg
      end select
      return
      end function phi
!*************************************************************************
      subroutine sampling_histo(npts,x,xfmax, xdmin, xdmax)
!*************************************************************************
!
!     The program determines the distribution of the intervals available in a time series
!     the time series is loaded in xx(:) with  xx(k) >= xx(k-1)
!     From that distribution one estimates the frequencies recoverable 
!     without aliasing from this time sampling
!   
!     For regular sampling this is perfectly defined by nu =1/(2*tau)
!     with tau : time interval in the sampling
!
!     For iregular sampling this is computed as the second decile of the
!     two-point interval.
!
!     F. Mignard  OCA
!     version 1.  March 2003
!
!     INPUT
!        npts   : number of data point in the time sampling
!        x      : array with the time values
!
!     OUTPUT
!        xfmax  : estimate of the highest frequency reovorable (this is loosely defined for an irregular sampling)
!        xdmin  : smallest two-point interval
!        xdmax  : largest  two-point interval
!************************************************************************* 
     implicit  none

      integer,         intent(in)   :: npts
      real(kind=dp),   intent(in)   :: x(*)
      real(kind=dp),   intent(out)  :: xfmax, xdmin, xdmax


      integer,         parameter    :: ityp=1, nbin=400, itape=6

      real(kind=dp)                 :: dif(npts)
      integer                       :: ind(npts), i

      do i = 1, npts-1
         dif(i) = x(i+1)-x(i)                 ! intervals between consecutive observations
      enddo

      call quicksort(npts-1,dif,ind)          ! sorts array dif(:)

      xfmax = 0.5d0/dif(nint(0.20*npts)+1)    ! typical maximum frequency achievable in the analysis.
                                              ! based on the second decile of the 2-point difference
      xdmin = dif(1)
      xdmax = dif(npts-1)

      return
      end  subroutine sampling_histo
!******************************************************
      subroutine phist(itape,ityp,xmin,xmax,nbin,nhist)
!******************************************************
!
!    PHIST write in the output file ITAPE the value of an histogram sampled
!    over nbin from xmin to xmax.
!    ityp  = 1  : xmin and xmax are the lower and upper boundaries of the extreme bins
!    ityp  = 2  : xmin = centre of the first bin : xmax = centre of the last bin
!    x < xmin ==> 1st bin
!    x > xmax ==> last bin
!    The histogram label in the printout is always the centre of the bin
!
! Author      : F. Mignard OCA/CERGA
!
!*** INPUT
!
!    itape    : logical unit of the output file
!    ityp     : 1  or 2 for the boudaries of the centres of the bins
!    xmin     : largest bin value
!    xmax     : smallest bin value ( > xmin)
!    nbin     : number of bins ( > 1 if ityp =2)
!    nhist    : values of the histogram for each of the nbin nhist(nbin)
!
!*** OUTPUT
!
!    no numerical output.
! 
!******************************************************
!
      implicit none
      real(kind=dp),     intent(in) ::  xmin, xmax
      integer,           intent(in) ::  itape, ityp,nbin

      integer                       ::  k, nhist(nbin)

      real(kind=dp)                 ::  step, xfirst,total,xval


      if(ityp == 1) then              ! boundaries at the edge of the first and last bins
         step   = (xmax - xmin)/nbin
         xfirst = xmin +0.5*step      ! center of the first bin
      else                            ! boundaries at the center of the first and last bins
         step   = (xmax - xmin)/(nbin -1) 
         xfirst = xmin  
      endif

      total = sum(nhist)

      do k = 1, nbin
         xval = xfirst + (k-1)*step    ! always center of the bins
         if(total > 0) then            ! test no data in nhist(:)
            write(itape,100) xval, nhist(k), 100*nhist(k)/total
         else
            write(itape,100) xval, nhist(k)
         endif
      enddo

100   format(f10.2, I8, f10.2)
      return
      end  subroutine phist
!******************************************************
      function ibin(ityp,x,xmin,xmax,nbin)
!******************************************************
!
!    IBIN determines the bin of x in an histogram with nbin from xmin to xmax
!    ityp  = 1  : xmin and xmax are the lower and upper boundaries of the extreme bins
!    ityp  = 2  : xmin = centre of the first bin : xmax = centre of the last bin
!    x < xmin ==> 1st bin
!    x > xmax ==> last bin
!
! Author      : F. Mignard OCA/CERGA
!
!*** INPUT
!
!    ityp     : 1  or 2 for the boundaries of the centres of the bins
!    x        : value to be binned
!    xmin     : valur of the first bin  
!    xmax     : value of the last bin  (could be < xmin)
!    nbin     : number of bins ( > 1 if ityp =2)
!
!*** OUTPUT
!
!    ibin     : value of the bin where x falls  (ibin = 1:nbin)
! 
!******************************************************
!
      implicit none


      integer,          intent(in)   :: ityp,nbin
      real(kind=dp),    intent(in)   :: x,xmin,xmax

      integer                        :: ibin

      integer                        :: ib
      real(kind=dp)                  :: step


      if(ityp == 1) then                   !boundaries at the edge of the first and last bins
         step = (xmax - xmin)/nbin
         ib   = (x - xmin)/step  + 1
      else                                 !boundaries at the center of the first and last bins
         step = (xmax - xmin)/(nbin -1)
         ib   =  nint((x - xmin )/step) +1
      endif
      ibin    =  max(min(ib,nbin),1)       ! x< xmin => ibin = 1, x>xmax => ibin = nbin
      return
      end function ibin
!***********************************************************
      recursive subroutine quicksort(n, list, order)
!***********************************************************
!
!     The routine sorts the real array x(n) in increasing order
!     with the quicksort algorithm in n*log(n) 
!
!*** INPUT    n     : size of data
!            list   : real array to be sorted
!
!
!*** OUTPUT   list  : sorted array
!            order  : permutation table of the sorting
!
!     list  is altered by the subroutine
!
!     Comment  :   order : sequence of indices 1,...,n
!                          permuted in the same way  as x
!                          would be.  Thus, the ordering on
!                          x is defined by y(i) = x(order(i)).
!************************************************************
! Quicksort routine from:
! Brainerd, W.S., Goldberg, C.H. & Adams, J.C. (1990) "programmer's guide to
! Fortran 90", mcgraw-hill  isbn 0-07-000248-7, pages 149-150.
! modified by Alan Miller to include an associated integer array which gives
! the positions of the elements in the original order.
!***********************************************************

      implicit none

      integer,                     intent(in)     ::  n
      real(kind=dp), dimension(n), intent(inout)  ::  list
      integer,       dimension(n), intent(out)    ::  order

      integer                                     :: i

      do i = 1, n
         order(i) = i
      end do

      call quick_sort_1(1, size(list))

      contains

      recursive subroutine quick_sort_1(left_end, right_end)

      integer, intent(in) :: left_end, right_end

      integer             :: i, j, itemp
      real(kind=dp)       :: reference, temp

      integer, parameter  :: max_simple_sort_size = 6

      if (right_end < left_end + max_simple_sort_size) then    ! use interchange sort for small lists

         call interchange_sort(left_end, right_end)

      else                                                     ! use partition ("quick") sort
         reference = list((left_end + right_end)/2)
         i = left_end - 1
         j = right_end + 1

         do                                                    ! scan list from left end until element >= reference is found
            do
               i = i + 1
               if (list(i) >= reference) exit
            enddo                                              ! scan list from right end until element <= reference is found
            do
               j = j - 1
               if (list(j) <= reference) exit
            enddo
            if (i < j) then                                    ! swap two out-of-order elements
               temp = list(i);   list(i)  = list(j) ; list(j)  = temp
               itemp = order(i); order(i) = order(j); order(j) = itemp
            else if (i == j) then
               i = i + 1
               exit
            else
               exit
            endif
         enddo

         if (left_end < j)  call quick_sort_1(left_end, j)
         if (i < right_end) call quick_sort_1(i, right_end)
      endif

      end subroutine quick_sort_1

      subroutine interchange_sort(left_end, right_end)

      integer, intent(in)    :: left_end, right_end
 
      integer                :: i, j, itemp
      real(kind=dp)          :: temp

      do i = left_end, right_end - 1
         do j = i+1, right_end
            if (list(i) > list(j)) then
               temp = list(i); list(i) = list(j); list(j) = temp
               itemp = order(i); order(i) = order(j); order(j) = itemp
            endif
         enddo
      enddo

      end subroutine interchange_sort

      end subroutine quicksort
!***********************************************************
      subroutine permut (n,ip,a )
!***********************************************************
!
!***********************************************************
!                                               Robert Renka
!                                       Oak Rridge Natl. Lab.
!                                             (615) 576-5139
!
! This routine applies a set of permutations to a vector.
!
! input parameters -  n - length of a and ip.
!
!                    ip - vector containing the sequence of
!                         integers 1,...,n permuted in the
!                         same fashion that a is to be per-
!                         muted.
!
!                     a - vector to be permuted.
!
! n and ip are not altered by this routine.
!
! output parameter -  a - reordered vector reflecting the
!                         permutations defined by ip.
!
! modules referenced by permut - none
!
! Method : decomposition of the permutation into cycles
!          then successive swaps until the cycle is exhausted
!          The array a is arranged in itself, without additional copy
!
!
!***********************************************************
      implicit none

      integer,                     intent(in)    ::   n
      integer,       dimension(n), intent(inout) ::   ip
      real(kind=dp), dimension(n), intent(inout) ::   a 

      integer                                    ::   nn, k, j, ipj
      real(kind=dp)                              ::   temp
!
! local parameters -
!
! nn =   local copy of n
! k =    index for ip and for the first element of a in a
!          permutation
! j =    index for ip and a, j .ge. k
! ipj =  ip(j)
! temp = temporary storage for a(k)
!

      nn = n
      if (nn .lt. 2) return
      k = 1

!
! loop on permutations
!
    1 j = k
      temp = a(k)

!
! apply permutation to a.  ip(j) is marked (made negative)
! as being included in the permutation.
!
    2 ipj = ip(j)
      ip(j) = -ipj
      if (ipj .eq. k) go to 3
      a(j) = a(ipj)
      j = ipj
      go to 2
    3 a(j) = temp

!
! search for an unmarked element of ip
!
    4 k = k + 1
      if (k .gt. nn) go to 5
      if (ip(k) .gt. 0) go to 1
      go to 4
!
! all permutations have been applied.  unmark ip.
!

    5 do 6 k = 1,nn
    6   ip(k) = -ip(k)
      return
      end   subroutine permut
!*************************************************************************
      subroutine lsqr_svd(ndata, nunk,iout, amat,y,weight,ipr,&
                          x,cor,rms,resid,rqm,irank,w)
!*************************************************************************
!PURPOSE
!   Solution of a leastsquares problem with the singular value decompostion
!   Minimum of |amat*x-y|^2 each equation being weighed with weight.
!   F. Mignard OCA/CASSIOPEE
!   Version 1 : September 2003
!
!   Built out of a preliminary driver written by C. Martin in 1996.
!   General algorithms from Numerical Recipes 
!
!*************************************************************************
!INPUT
!      ndata   : number of observation equations in the design matrix
!      nunk    : number of fitted parameters
!      iout    : logical unit for the printouts
!                rem: in most fortran implementation iout = 6 is the screen.
!                so use iout = 6 without open statement to have the output on screen.
!      amat    : amat(ndata,nunk) : design matrix
!                caution : this is the transpose of the design matrix V in my routine
!                which solves the same problem with on normal equations
!      y       : y(ndata) right hand side of the observations equations, i.e. the observations.
!      weight  : weight(ndata) : weight of each observation (nominally 1/sigma_i^2)
!      ipr     : index of the level of output from the program
!                0 : no output managed by the subroutine (so this is managed by the user)
!                1 : simple output of the results + formal erros +correlations
!                2 : extended output with matrix, singular values ..
!OUTPUT
!      x       : x(nunk) vector with the least squares estimates.
!      cor     : correlation matrix
!      rms     : rms(nunk) : formal standard deviations (sqrt(variances))
!      resid   : resid(ndata) : residuals O-C
!      rqm     : mean quadratic rediduals (weight =1) or unit weight variances.
!                rqm is ~ the weighted variance of the residuals, not the standard deviation
!      irank   : rank of the design matrix from the singular value decompostion
!      w       : singular values
!*************************************************************************

!*********************
      implicit none
!*********************
      integer,        intent(in)     :: ndata, nunk, iout, ipr
      real(kind=dp),  intent(in)     :: amat(ndata,nunk), y(ndata), weight(ndata)
      real(kind=dp),  intent(out)    :: x(nunk),cor(nunk,nunk),rms(nunk),resid(ndata),w(nunk)

      integer,        intent(out)    :: irank

      real(kind=dp),  parameter      :: tol = 0d0  ! tolerance for the singular values

      real(kind=dp)                  :: u(ndata,nunk),v(nunk,nunk),aa(ndata,nunk) ,ss(ndata)
      real(kind=dp)                  :: b(ndata),tmp(ndata)
      integer                        :: i,j,ndata_eff
      real(kind=dp)                  :: wmax,thresh,chisq,rqm
!
!     weighing the equations and observations
!
      tmp = sqrt(weight)              ! weights are like 1/sigma_i^2 for each observation
      do  j=1,nunk
         aa(:,j) = amat(:,j)*tmp      !weighed design matrix
      enddo
      b = y*tmp                       !weighed RHS
!
!     svd of the design matrix   aa = u*w*tr(v)
!
      call svd_decomp(ndata,nunk,aa,u,w,v)
!
!     diagnose singulars values
!
      wmax = maxval(w)                  ! largest singular value
      thresh=tol*wmax
      irank=nunk
      do j=1,nunk
         if(w(j).lt.thresh) then
            w(j)=0.
            irank=irank-1
         endif
      enddo
!
!     solve for the unknowns
!
      call svd_solver(ndata,nunk,u,w,v,b,x)
!
!     residuals and unit weight variance
!
      ss    = matmul(amat,x)                 !computed values
      resid = y-ss                           !O - C
      chisq = sum(weight*resid**2)           !weighed sum of the quadratic residuals
      ndata_eff =count(weight.gt.0d0)        !count only the observations with positive weight. The other are assumed to be rejected
      rqm=chisq/(ndata_eff-irank)            !mean quadratic residual or UWV (unit weight variance)
!
!     standard errors and correlations
!
      call svd_var(nunk,w,v,rqm,rms,cor)
!
!     output
!
      if(ipr.lt.0) then
         write(iout,*)  ' rang = ',irank,'  rqm = ',rqm
         write(iout,*)
         write(iout,200) (x(j),j=1,nunk)
         write(iout,*)
         write(iout,250) (rms(j),j=1,nunk)
         write(iout,*)
      endif
      if(ipr.gt.1) then
         write(iout,*)
         write(iout,*) '*****************************************************'
         write(iout,*) '*                   matrix  v                       *'
         write(iout,*) '*****************************************************'
         do  i=1,nunk
            write(iout,100) (v(i,j),j=1,nunk)
         enddo
         write(iout,*)
         write(iout,*) '*****************************************************'
         write(iout,*) '*              correlation matrix                   *'
         write(iout,*) '*****************************************************'
         do  i=1,nunk
            write(iout, 100) (cor(i,j),j=1,nunk)
         enddo
         write(iout,*)
         write(iout,*) '*****************************************************'
         write(iout,*) '*                singular values                    *'
         write(iout,*) '*****************************************************'

         write(iout,300) (w(j),j=1,nunk)
         write(iout,*)
      endif
100   format(7f10.3)
200   format(' Solutions : ',//, (8E12.4))
250   format(' Sigmas    : ',//, (8E12.4))
300   format(  8E12.3)

      return
      end subroutine lsqr_svd
!*******************************************************************
      subroutine svd_solver(ndata,nunk,u,w,v,b,x)
!*******************************************************************
!
!PURPOSE
!    solve the system  Ax = B where A =U*W*trans(V) from the 
!    singular value decomposition of A
!
!    F. Mignard OCA/CASSIOPEE
!    Version 1 : September 2003
!    Algorithm from Numerical Recipes under the name svbksb.
!
!********************************************************************
!INPUT
!     ndata  : number of equations (number of lines of the matrix A)
!     nunk   : number of unknowns (rows of A, lines of B)
!     u      : u(ndata,nunk)  first matrix of the svd
!     w      : w(nunk)        singular values (diagonal of the second matrix of svd)
!     v      : v(nunk,nunk)   third matrix of the svd 
!     b      : Right hand side of the system
!
!OUTPUT
!     x      : x(nunk) : solution of the system
!*******************************************************************    
!
!*********************
      implicit none
!*********************

      integer,         intent(in)     :: ndata, nunk
      real(kind=dp),   intent(in)     :: u(ndata,nunk),w(nunk),v(nunk,nunk),b(ndata)
      real(kind=dp),   intent(out)    :: x(nunk)
 
      real(kind=dp)                   :: tmp(nunk)
      integer                         :: j
!
!     computation of tr(U)*b/w
!
      do  j=1,nunk
         if(w(j).ne.0.) then
            tmp(j) = sum(u(:,j)*b)/w(j)
         else
            tmp(j)=0d0
         endif
      enddo
!
!     Left product of the above result by V
!
      x = matmul(v,tmp)

      return
      end subroutine svd_solver
!*************************************************************************
      subroutine svd_var(nunk,w,v,rqm,rms,correl)
!*************************************************************************
!PURPOSE
!    Covariance matrix in a least squares problem solved with SVD
!
!    F. Mignard OCA/CASSIOPEE
!    Version 1 : September 2003
!    Algorithm from Numerical Recipes under the name svdvar.
!
!********************************************************************
!INPUT
!     nunk   : number of unknowns (rows of A, lines of B)
!     w      : w(nunk)        singular values (diagonal of the second matrix of svd)
!     v      : v(nunk,nunk)   third matrix of the svd 
!     rqm    : mean (weighted) quadratic residuals (or UWV)
!
!OUTPUT
!     rms    : rms(nunk)  formal standard deviations of the esimates
!     correl : correl(nunk,nunk) : correlation matrix
!*******************************************************************    
!
!*********************
      implicit none
!*********************

      integer,        intent(in)  :: nunk
      real(kind=dp),  intent(in)  :: v(nunk,nunk), w(nunk), rqm
      real(kind=dp),  intent(out) :: correl(nunk,nunk), rms(nunk)

      real(kind=dp)               :: covar(nunk,nunk),wti(nunk),ss
      integer                     :: i, j

      do   i=1,nunk
         if(w(i).ne.0d0) then
            wti(i)=1d0/(w(i)*w(i))
         else
            wti(i)= 0d0
         endif
      enddo
!
!     computation of the inverse of the normal matrix
!
      do  i=1,nunk
         do  j=1,i
            ss = sum(v(i,:)*v(j,:)*wti)
            covar(i,j)=ss
            covar(j,i)=ss
         enddo
         rms(i)=sqrt(covar(i,i))
      enddo
!
!     correlations from the covariances
!
      do  i=1,nunk
         do  j=1,nunk
            if(rms(i).gt.0d0.and.rms(j).gt.0d0) then
               correl(i,j)=covar(i,j)/(abs(rms(i)*rms(j)))
            else
               correl(i,j)=9.99
            endif
         enddo
      enddo       
!
!     formal standard errors
!    
      rms = rms*sqrt(rqm)           

      return
      end subroutine svd_var
!*******************************************************************
      SUBROUTINE svd_decomp(m,n,a,u,w,v)
!
!PURPOSE
!    Computes the singular value decomposition of a matrix  A(m,n) and returns A =U*W*trans(V) 
!
!    Adapted  partially to F90 by F. Mignard from svbksb in Numerical Recipes.
!    Version 1 : September 2003
!
!********************************************************************
!INPUT
!     m      : number of equations (number of lines of the matrix a)
!     n      : number of unknowns (rows of a)
!INPUT/OUTPUT
!     a      : a(m,n) : matrix to be decomposed
!OUTPUT
!     u      : u(m,n) : first matrix of the svd
!     w      : w(n)   : singular values (diagonal of the second matrix of svd)
!     v      : v(n,n) : third matrix of the svd 
!*******************************************************************    

      implicit none

      integer,        intent(in)    :: m,n
      real(kind=dp),  intent(inout) :: a(m,n)
      real(kind=dp),  intent(out)   :: u(m,n),w(n),v(n,n)

      integer                       :: i,its,j,jj,k,l,nm
      real(kind=dp)                 :: c,f,h,s,x,y,z,rv1(n),aa(m,n)
      real(kind=dp)                 :: g    = 0.0D0
      real(kind=dp)                 :: scale= 0.0D0
      real(kind=dp)                 :: anorm= 0.0D0

      aa = a                         ! to save A at exit
      do  i=1,n
         l=i+1
         rv1(i)=scale*g
         g=0.0
         s=0.0
         scale=0.0
         if(i.le.m)then
            do  k=i,m
               scale=scale+abs(a(k,i))
            enddo
            if(scale.ne.0.0)then
               do  k=i,m
                  a(k,i)=a(k,i)/scale
                  s=s+a(k,i)*a(k,i)
               enddo
               f=a(i,i)
               g=-sign(sqrt(s),f)
               h=f*g-s
               a(i,i)=f-g
               do  j=l,n
                  s=0.0
                  do  k=i,m
                     s=s+a(k,i)*a(k,j)
                  enddo
                  f=s/h
                  do  k=i,m
                     a(k,j)=a(k,j)+f*a(k,i)
                  enddo
               enddo
               do  k=i,m
                  a(k,i)=scale*a(k,i)
               enddo
            endif
         endif
         w(i)=scale *g
         g=0.0
         s=0.0
         scale=0.0
         if((i.le.m).and.(i.ne.n))then
            do  k=l,n
               scale=scale+abs(a(i,k))
            enddo
            if(scale.ne.0.0)then
               do  k=l,n
                  a(i,k)=a(i,k)/scale
                  s=s+a(i,k)*a(i,k)
               enddo
               f=a(i,l)
               g=-sign(sqrt(s),f)
               h=f*g-s
               a(i,l)=f-g
               do  k=l,n
                  rv1(k)=a(i,k)/h
               enddo
               do  j=l,m
                  s=0.0
                  do  k=l,n
                     s=s+a(j,k)*a(i,k)
                  enddo
                  do  k=l,n
                     a(j,k)=a(j,k)+s*rv1(k)
                  enddo
               enddo
               do  k=l,n
                  a(i,k)=scale*a(i,k)
               enddo
            endif
         endif
         anorm=max(anorm,(abs(w(i))+abs(rv1(i))))
      enddo
      do  i=n,1,-1
         if(i.lt.n)then
            if(g.ne.0.0)then
               do  j=l,n
                  v(j,i)=(a(i,j)/a(i,l))/g
               enddo
               do  j=l,n
                  s=0.0
                  do  k=l,n
                     s=s+a(i,k)*v(k,j)
                  enddo
                  do  k=l,n
                     v(k,j)=v(k,j)+s*v(k,i)
                  enddo
               enddo
            endif
            do  j=l,n
               v(i,j)=0.0
               v(j,i)=0.0
            enddo
         endif
         v(i,i)=1.0
         g=rv1(i)
         l=i
      enddo
      do  i=min(m,n),1,-1
         l=i+1
         g=w(i)
         do  j=l,n
            a(i,j)=0.0
         enddo
         if(g.ne.0.0)then
            g=1.0/g
            do  j=l,n
               s=0.0
               do  k=l,m
                  s=s+a(k,i)*a(k,j)
               enddo
               f=(s/a(i,i))*g
               do  k=i,m
                  a(k,j)=a(k,j)+f*a(k,i)
               enddo
            enddo
            do  j=i,m
               a(j,i)=a(j,i)*g
            enddo
         else
            do  j= i,m
               a(j,i)=0.0
            enddo
         endif
         a(i,i)=a(i,i)+1.0
      enddo
      do  k=n,1,-1
         do  its=1,30
            do  l=k,1,-1
               nm=l-1
               if((abs(rv1(l))+anorm).eq.anorm)  goto 2
               if((abs(w(nm))+anorm).eq.anorm)  goto 1
            enddo
1           continue
            c=0.0
            s=1.0
            do  i=l,k

               f=s*rv1(i)
               rv1(i)=c*rv1(i)
               if((abs(f)+anorm).eq.anorm) goto 2
               g=w(i)
               h=sqrt(f*f+g*g)
               w(i)=h
               h=1.0/h
               c= (g*h)
               s=-(f*h)
               do  j=1,m
                  y=a(j,nm)
                  z=a(j,i)
                  a(j,nm)=(y*c)+(z*s)
                  a(j,i)=-(y*s)+(z*c)
               enddo
            enddo
2           continue
            z=w(k)
            if(l.eq.k)then
               if(z.lt.0.0)then
                  w(k)=-z
                  do  j=1,n
                     v(j,k)=-v(j,k)
                  enddo
               endif
               goto 3
            endif
            if(its.eq.30) pause 'no convergence in svdcmp'
            x=w(l)
            nm=k-1
            y=w(nm)
            g=rv1(nm)
            h=rv1(k)
            f=((y-z)*(y+z)+(g-h)*(g+h))/(2.0*h*y)
            g=sqrt(f*f+1d0)
            f=((x-z)*(x+z)+h*((y/(f+sign(g,f)))-h))/x
            c=1.0
            s=1.0
            do  j=l,nm
               i=j+1
               g=rv1(i)
               y=w(i)
               h=s*g
               g=c*g
               z=sqrt(f*f+h*h)
               rv1(j)=z
               c=f/z
               s=h/z
               f= (x*c)+(g*s)
               g=-(x*s)+(g*c)
               h=y*s
               y=y*c
               do  jj=1,n
                  x=v(jj,j)
                  z=v(jj,i)
                  v(jj,j)= (x*c)+(z*s)
                  v(jj,i)=-(x*s)+(z*c)
               enddo
               z=sqrt(f*f+h*h)
               w(j)=z
               if(z.ne.0.0)then
                  z=1.0/z
                  c=f*z
                  s=h*z
               endif
               f= (c*g)+(s*y)
               x=-(s*g)+(c*y)
               do  jj=1,m
                  y=a(jj,j)
                  z=a(jj,i)
                  a(jj,j)= (y*c)+(z*s)
                  a(jj,i)=-(y*s)+(z*c)
               enddo
            enddo
            rv1(l)=0.0
            rv1(k)=f
            w(k)=x
         enddo
3        continue
      enddo
      u = a       !return the matrix u of the svd.
      a = aa      !recover a unchanged
      return
      end subroutine svd_decomp
      
!************************************************
      function median(npts, array)
!************************************************
!
! Purpose : Computation of the median value of a set of numbers
!           Robust estimate of the central location
!
! F. Mignard December 2002
!
!  INPUT
!         npts   : number of data points
!        array   : array with the npts data points
!  OUPTUT
!        median  : median value
!      
!
!************************************************
      implicit none
      
      integer,        intent(in)                    :: npts
      real(kind=dp),  intent(in), dimension(npts)   :: array
      real(kind=dp)                                 :: median

      real(kind=dp),              dimension(npts)   :: xdat
      integer,                    dimension(npts)   :: ind
      
      if(npts <1) then
         print *, 'no data in the call of the function median'
         print *, 'program stopped'
         stop
      else
         xdat  = array                               ! the sorted array is altered by quicksort
         call quicksort(npts, xdat, ind)
         if(modulo(npts,2) == 1) then                ! odd number of elements
            median = xdat((npts+1)/2)
         else
            median = 0.5d0*(xdat(npts/2) + xdat(npts/2 +1))
         endif
      endif
      end function median
!***************************************************
      subroutine writefold_lc(idstar,npts,x,y, period)
!***************************************************
!
! Write on a file the folded light curve of a star with a
! trial period.
! The file will be written in the current directory as
! folded_lc_idstar.txt
!
! F. Mignard  OCA/Cassiopee
! 
! Version 1 : Feb 2005
!
! INPUT
!     idstar  : star id (here assumed to be less that 1E6)
!     npts    : number of observations in the data file
!     x       : x(npts) : time sampling
!     y       : y(npts) : observed magnitudes
!     period  : trial period in days
!
!****************************************************
      implicit none
 
      integer      , intent(in)      :: idstar, npts
      real(kind=dp), intent(in)      :: x(npts), y(*)
      real(kind=dp), intent(in)      :: period

      real(kind=dp)                  :: z(npts)
      character*6                    :: filenum
      integer ,      parameter       :: ifold = 99               ! unit is closed in writepower

      write(filenum,'(i6.6)') idstar                            ! to index the filename of power.txt
 
!      open(unit = ifold, file = 'lightcurves/folded_lc_'//filenum//'.txt',status='unknown')
      open(unit = ifold, file = ' folded_lc_'//filenum//'.txt',status='unknown')
      z = (x/period)-floor(x/period)                            ! folding the time
      call writepower(ifold,npts,z,y)                           ! writing the file with the folded LC
      return
      end subroutine writefold_lc
!***********************************************************
 end module famouslib
!***********************************************************


