THIS FILE CONTAINS A MATHEMATICA PACKAGE FOR DOING
CARATHEODORY_FEJER APPROXIMATION -A LA THREFETHEN.
FOLLOWED BY A COPY OF THREFETHEN's MATLAB VERSION.
There are some differences: the mathematica version 
has been adapted to work in the Laplace domain,
instead of the unit circle. O. Merino.  Dec. 92.

(* ---------------- cut ------------------------ cut ----------------- *)


(* :Title: CFApprox *)

(* :Author: September 1992, by O.Merino.  Algorithm by L. N. Threfethen. *)

(* :Context: CFApprox` *)

(* :History: 
*)
    
(* :Discussion:
*)
(* Example:
	(* set the grid points on the w axis *)
	n = 128;
	e = Table[N[Exp[2 Pi I (i-1)/n]],{i,1,n}];
	w = - I (1 + e)/(1-e);
	
	(* sample the function *)
	f = Sqrt[(0.2 s + 2.2)/(s+1)] /. s-> I w;
	f[[1]]=Sqrt[0.2];
	
	(* Approximate the function *)
	CFApproximant[f,1,1]
*)

BeginPackage[ "CFApprox`"]


CFApproximant::usage="CFApproximant[fdisc,dn,dd,var,opts] produces a 
rational function in the variable var with no poles in the closed unid disk in the complex plane, which is a model that approximates the data fdisc in the norm of the supremum.  fdisc is the list of samples of a function on a grid on the jw axis, obtained from the transformation s = b*(1+z)/(1-z) applied to a grid of equally spaced points z on the unit circle.  dn is the degree of the numerator, dd is the degree of the denominator of the output. The algorithm is by L. N. Threfethen.";

HankelSize::usage="Option of CFApproximant[].  Specifies the size of the Hankel matrix"

GridSpread::usage="Option of CFApproximant[].  Scaling parameter for the linear fractional transformation s = b*(1+z)/(1-z), where s=Laplace domain variable, z = unit disk variable."

Var::usage="Option of CFApprox.  Specifies the variable of the output."

s::usage="Laplace Domain variable"

Options[CFApproximant]={HankelSize->Automatic,
			GridSpread->1,
			Var->s};

Begin["CFApprox`Private`"]

CFApproximant[fdisc_,dn_,dd_,opts___Rule]:=
Module[{n,k,dn1,dd1,dim,edisc,fc,hankel,u,v,sdn1,var,rat,gsp,sing,
		 u1,v1,zr,qout,qc,b,rt,rtc,pc1,pc,error,x,y,i,j},
	n = Length[fdisc];
	k = HankelSize /. {opts} /. Options[CFApproximant];
	gsp = GridSpread /. {opts} /. Options[CFApproximant];
	var = Var /. {opts} /. Options[CFApproximant];
	If[k==Automatic,k = n/8];
	dn1 = dn +1;
	dd1 = dd + 1;
	dim = k + dd - dn;
	edisc = Table[N[Exp[2 Pi I (i-1)/n]],{i,1,n}];
	fc=Re[Join[Take[Reverse[RotateLeft[Fourier[fdisc]]]/N[Sqrt[n]],{1,n/2}]
                  ,Table[0.,{n}]]];
	hankel = Table[fc[[i+j+dn-dd]],{i,1,dim},{j,1,dim}];
	svd = Check[SingularValues[hankel],True];
	If[svd==True,Return[$MessageList]];
	{u,sing,v}=svd;
	sdn1 = sing[[dd1]];
	u1 = Reverse[u[[dd1]]];
	v1 = v[[dd1]];
	zr = z /. NSolve[ v1.Reverse[Table[z^i,{i,0,Length[v1]-1}]]==0,z];
	qout = {};
	Do[If[Abs[zr[[i]]]>1,qout = Join[qout,{zr[[i]]}]],
                   {i,1,dim-1}];
	qc = Expand[Product[(x - qout[[i]]),{i,1,Length[qout]}]/
        Product[qout[[i]],{i,1,Length[qout]}]]; 
	b = Reverse[RotateLeft[Fourier[Join[u1,Table[0.,{n-dim}]]]/
              Fourier[Join[v1,Table[0.,{n-dim}]]]]];
	rt = fdisc - sdn1*edisc^k *b;
	rtc = Reverse[RotateLeft[Re[Fourier[rt]/N[Sqrt[n]]]]];
	pc1 = Expand[x^(Length[qout]-1+dn1)*
        (  (y^Length[qout]) (qc /. x->y^(-1) )*
            Take[rtc,{1,dn1}].Reverse[Table[y^i,{i,0,dn1-1}]]
         ) /.y->x^(-1)];
	pc = (pc1 /. x->0. ) + Sum[Coefficient[pc1,x^i]*x^i,{i,1,dn1-1}];
	error = Max[Abs[fdisc - (pc/qc /. x->edisc)]];
	Print["Error = ",error];
	rat = Together[ pc/qc /. {x-> (var - gsp)/(var + gsp)}] ;
	Return[Chop[rat]];
   ]

End[]
EndPackage[]




(* ---------------- cut ------------------------ cut ----------------- *)


% CR complex rational cf approximation on the unit disk
% Lloyd N. Trefethen.  Dept. of Math. MIT, March 1986 
%Reference: L.N.T. Numer. Math. 37 (1981), pp. 297-320.
% (this is type 2 approx., slightly different from above.)
% 
%       fz(z)   -function to be approximated by r(z)=p(z)/q(z)
%       m,n     -degree of p,q
%       nfft    -number of points in FFT (power of 2)
%       K       -degree at which Taylor series is truncated
%       f,p,q,r -functions evaluated on FFT mesh (roots of unity)
%       pc,qc   -coefficients of p and q
%
%CONTROL PARAMETERS
        m = input('m? ');
	n = input('n? ');
	mp = m+1; 
	np = n+1;
        nfft = input('nfft? ');
        K = input('K? '); 
	dim = K + n - m;
%
%TAYLOR COEFFICIENTS OF fz
        z = exp(2*pi*sqrt(-1)*(0:nfft-1)/nfft);
        f =fz(z); 
	fc = real(fft(f))/nfft;
        fc(nfft/2+1:nfft) = zeros(1,nfft/2);
%
%SVD OF HANKEL MATRIX H
        H = toeplitz(fc(1+rem((dim:-1:1)+nfft+m-n,nfft)));
        H = triu(H); 
	H = H(:,(dim:-1:1));
        [u,s,v]=svd(H);
        s = s(np,np); 
	u = u((dim:-1:1),np)';
	v = v(:,np)';
%
%DENOMINATOR POLYNOMIAL q
        zr = roots(v);
	qout = []; 
	for i=1:dim-1;
        if abs(zr(i))>1 qout = [qout,zr(i)]; 
	end; 
	end;
        qc = real(poly(qout)); 
	qc = qc/qc(np); 
	q = polyval(qc,z);
%
%NUMERATOR POLYNOMIAL p 
        b = fft([u zeros(1,nfft-dim)])./fft([v zeros(1,nfft-dim)]);
        rt  = f-s*z.^K.*b; 
	rtc = real(fft(rt))/nfft;
        pc = conv(qc(np:-1:1),rtc(1:mp)); 
	pc = pc(mp:-1:1);
        p = polyval(pc,z); 
	r = p./q;
%
%RESULTS
        axis('square'); 
	plot([f-r f(1)-r(1)]); 
	pause;
        s, err = norm(f-r,'inf'), pc, qc


(* ---------------- cut ------------------------ cut ----------------- *)
 
 
 
                         