rr_dfs.m

在matlab中

function [t,p,deg,coeff,f] = rr_dfs(Qu,D,u,t,p,deg,coeff,f,m)

% Roth-Ruckenstein depth first search
%
% Inputs:
%   Qu -- bivariate polynomial
%   D -- stopping condition (search for polynomials of deg < D)
%   u -- node index
%   t -- global node counter
%   p -- vector of node parents
%   deg -- polynomial degree
%   coeff -- coefficient for each node
%   f -- output polynomials

% get Q(x,0)
g = Qu(:,1);

if (g == zeros(size(Qu,1),1))
   fnew = gf(zeros(1,deg(u)+1),m);
   % recurse up the tree
   w = u;
   while (w ~= 1)
      fnew(deg(w)+1) = fnew(deg(w)+1) + coeff(w);
      w = p(w);
   end
   
   lf = size(f,2);
   ln = length(fnew);
   
   if (ln > lf)
     f = [f gf(zeros(1,ln-lf),m); fnew];
   elseif (ln < lf)
     f = [f; fnew gf(zeros(1,lf-ln),m)];
   else
     f = [f; fnew];
   end

elseif (deg(u) < D)
   R = roots(fliplr(Qu(1,:)));
   for ind1=1:length(R)
      a = R(ind1);
      v = t;
      t = t+1;
      p(v) = u;
      deg(v) = deg(u)+1;
      coeff(v) = a;

      Qv = gf(zeros(size(Qu,1)),m);
      for r=1:size(Qu,1)
         gr_y = Qu(r,:);
         for s=1:size(Qv,2);
	    Qv(r+s-1,s) = hasse_deriv1(gr_y, a, s-1, m);
         end
      end
          
      % REDUCE Qv(x,x+a) by dividing by largest x^m possible
      if (size(Qv,1) > 1)
         while ((Qv(1,:) == zeros(1,size(Qv,2))))
	   Qv = Qv(2:end,:);
         end
      
	 % remove zero rows/cols from Qv
	 [Is,Js] = find(Qv~=0);
	 Qv = Qv(1:max(Is), 1:max(Js));
      end


      [t,p,deg,coeff,f] = rr_dfs(Qv,D,v,t,p,deg,coeff,f,m);
   end
end