function [D,degD,U,degU,UI,degUI] = polgld(A,degA,mes)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Finds greatest left divisor of a polynomial matrix A           %
%                                                                %
%          A * U = [ D 0 ]                                       %
%                                                                %
% U unimodular, UI=U^(-1), number of columns of D = rank A       %
% mes (=0,1,2) ... message and interrupt level                   %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% M. Sebek, September 1990                                       %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% functions used: polmatcl, polmul, polseten, polsize;


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% preliminaries                                                  %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

[rA,cA]=polsize(A,degA);
n=min(rA,cA-1);
[D,degD,DEGD,LCD]=polmatcl(A,degA);
U=eye(cA); degU=0;
UI=U; degUI=0;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% triangularization of D                                         %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

for i=1:n
  
                 			  if mes>0,i,keyboard,end

   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   % reduction of i-th row                                       %
   %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   while max(DEGD(i,i+1:cA))>=0

      T=eye(cA);degT=0;
      TI=T; degTI=0;

      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      % minimum degree nonzero polynomial on  the right of row i %
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

      [Min,K]=min(abs(DEGD(i,i:cA)));
      K=K+(i-1)*ones(1,length(K));
      [Max,KK]=max(abs(LCD(i,K)));
      k=K(KK(1));
                                         if mes>0,k,keyboard,end

      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      % reduction of degrees to the right from (i,i)            %
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

      if k==i
        
	for j=i+1:cA
	  c=LCD(i,j)/LCD(i,i);
	  p=DEGD(i,j)-DEGD(i,i);
	  s=[zeros(1,p) c];
	  [T,degT]=polseten(T,degT,-s,p,i,j);
	  [TI,degTI]=polseten(TI,degTI,s,p,i,j);
        end

      else

	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	% interchange of columns  i and k                       %
	%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	T(i,k)=1; T(k,i)=1; T(i,i)=0; T(k,k)=0;
	TI=T;

      end

				       if mes>0,T,TI,keyboard,end

      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      % application of T,TI                                    %
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

      [U,degU]=polmul(U,degU,T,degT);
      [UI,degUI]=polmul(TI,degTI,UI,degUI);
      [D,degD]=polmul(D,degD,T,degT);
      [D,degD,DEGD,LCD]=polmatcl(D,degD);

				if mes>0,D,DEGD,U,UI,keyboard,end
    end

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    % row i reduced                                            %
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% end of triangularization                                     %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% cancellation of zero columns of D                            %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

cD=cA;
while max(DEGD(:,cD))<0
  DEGD(:,cD)=[];
  D(:,cD:cD:(degD+1)*cD)=[];
  cD=cD-1;
end

				   if mes>0,cD,D,keyboard,end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% clearing of U,UI                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

[U,degU]=polmatcl(U,degU);
[UI,degUI]=polmatcl(UI,degUI);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%