% Copyright (c) 1991 Marcel Roelofs, University of Twente, Enschede,
% The Netherlands.
%
% $Header: supervf.web,v 0.94 92/02/26 17:29:57 roelofs Exp $
%
\input specification
\def\Version$#1Revision: #2 ${Version #2}
\def\title{SUPER VECTORFIELD}
\font\titlefont=cmcsc10 scaled\magstep3
\font\ttitlefont=cmtt10 scaled\magstep4
\def\topofcontents{\null\vfill
\centerline{\titlefont The {\ttitlefont SUPER VECTORFIELD} package for REDUCE}
\vskip15pt\centerline{\Version$Revision: 0.94 $}
\vskip15pt\centerline{\sc Marcel Roelofs}\vfill}
\def\enditem{\medskip\noindent\ignorespaces}
% single control sequences are used by WEB
\def\BZ{{\bf Z}}
\def\BN{{\bf N}}
\def\BR{{\bf R}}
\def\CinfU{C^\infty(U)}
\def\dd#1#2{{\displaystyle{\partial #1\over\partial #2}}}

@*=Super vectorfields in REDUCE. In this \.{WEB} file we shall implement
the action of $\BZ_2$ graded vectorfields on $\BZ_2$ graded functions.
The package is partially based on a former package by Gragert and
Kersten, which also implemented $\BZ_2$ graded forms and operators
like exterior differentiation, Lie derivatives, etc. Since our methods
nowadays mainly consist of using vectorfields, there is no direct
need for an implementation of these operators.

\medskip

\noindent The ``banner line'' defined here is intended for
indentification purposes on loading. It should be changed whenever
this file is modified. System dependent changes, however, should be
made in a separate change file.

@d banner="Super vectorfield package for REDUCE 3.4, $Revision: 0.94 $"

@ We define the following macros for clarity.
@d change_to_symbolic_mode =symbolic
@d change_to_algebraic_mode =algebraic
@d stop_with_error(string_1,expr_1,string_2,expr_2) = @/
  msgpri(string_1,expr_1,string_2,expr_2,t) @;
@d message(string_1,expr_1,string_2,expr_2) = @/
  msgpri(string_1,expr_1,string_2,expr_2,nil) @;
@d operator_name_of=car
@d arguments_of=cdr
@d first_argument_of=cadr
@d second_argument_of=caddr
@d first_element_of=car
@d rest_of=cdr
@d skip_list=cdr   %Skip the |'list| in front of an algebraic list%

@ The following macros are intended as common programming idioms.
@d incr(x) = (x:=x+1)@;
@d decr(x) = (x:=x-1)@;

@ A new REDUCE switch can be introduced using the following code.

@d initialize_global(global_name,value)=@/
global '(global_name)$@/
global_name:=value

@d new_switch(switch_name,value)=@/
initialize_global(!* @& switch_name,value)$@/
flag('(switch_name),'switch)

@ We do all initializations in the beginning of the package.  
@u
change_to_symbolic_mode$@/ 
write banner$terpri()$@/
@<Lisp initializations@>
change_to_algebraic_mode$

@ We shall start with a (very) short description of the local picture of a
graded manifold and vectorfields on these graded manifolds. For a more
detailed description we refer to B. Kostant, Lecture Notes in
Mathematics 570 (1977).

The local picture of a {\it graded manifold} is $U\subset\BR^m$ open
together with the {\it graded commutative algebra}
$
\CinfU\otimes\Lambda(n)
$
where $\Lambda(n)$ is the antisymmetric (exterior) algebra on $n$
elements $s_1,\dots,s_n$, with $\BZ_2$-degree $\vert s_i\vert=1$ and $s_i
s_j=-s_j s_i$.
A particular element $f\in\CinfU\otimes\Lambda(n)$ is represented by
$
f=\sum_\mu f_\mu s_\mu
$
where 
$$\mu\in M_n=\{\mu=(\mu_1,\dots,\mu_k) \mid
\mu_i\in\BN,1\leq\mu_1<\mu_2<\cdots< \mu_k\leq n\},$$
$s_\mu=s_{\mu_1}s_{\mu_2}\cdots s_{\mu_k}$ and $f_\mu\in\CinfU$.

{\it Graded vectorfields} on a graded manifold
$(U,\CinfU\otimes\Lambda(n))$ are introduced as graded derivations of
the algebra $\CinfU\otimes\Lambda(n)$. It can be shown that they
constitute a left $\CinfU\otimes\Lambda(n)$-module. Locally a graded
vectorfield $V$ is represented as
$$
V=\sum_{i=1}^m f_i\dd{}{x_i} + \sum_{j=1}^n g_j\dd{}{s_j}
$$
with $f_i,g_j\in\CinfU\otimes\Lambda(n)$ and $x_i$ $(i=1,\dots,m)$ a
local coordinate system on $U$.

The derivations $\dd{}{x_i}$ are even, while the derivation
$\dd{}{s_j}$ are odd; they satisfy the relations
$$
 \dd{x_i}{x_k}=\delta_{ik},\qquad \dd{s_j}{x_k}=0,\qquad
 \dd{x_i}{x_\ell}=0,\qquad \dd{s_j}{s_\ell}=\delta_{j\ell}.
$$

@ In REDUCE we shall represent the elements $s_\mu\in\Lambda(n)$ by
EXT($\mu_1,\dots,\mu_k$). Thus elements of $\CinfU\otimes\Lambda(n)$
can be implemented in REDUCE as ordinary algebraic expressions.

@<Lisp ini...@>=
algebraic operator ext$

@*1 Initializing vectorfields. 
In order to introduce graded vectorfields, we need to know the
local coordinates $x_i$ on $U$, as well as the components of
$\dd{}{x_i}$ and $\dd{}{s_j}$.

In this file we want to implement vectorfields as algebraic operators
with a simplification procedure which takes care of the action on a function.
It is our purpose to keep the local coordinates and the components
local to one vectorfield at a time.

The following procedure initializes a super vectorfield. The macro
|make_oplist| is taken from the TOOLS package; it transforms algebraic
and lisp lists and identifiers into the appropriate lisp lists.

We will not give all components of the vectorfield here: it is much
easier to give them separately, as we shall see in the sequel.

@d make_oplist(op_list)=@/if null op_list then op_list else if atom
op_list then list op_list else if
car op_list='list then cdr op_list else op_list @;

@u lisp operator super_vectorfield;
lisp procedure super_vectorfield(operator_name,even_dimension,
                                 odd_dimension,variables);
begin 
  if not idp operator_name then @/
    stop_with_error("SUPER_VECTORFIELD:",operator_name,"is not an identifier",nil);
  if not fixp even_dimension or even_dimension<0 or
     not fixp odd_dimension or odd_dimension<0 then@/
    rederr("SUPER_VECTORFIELD: improper dimensions");
  put(operator_name,'simpfn,'super_der_simp);
  flag(list(operator_name),'full);@/
  put(operator_name,'even_dimension,even_dimension);@/
  put(operator_name,'odd_dimension,odd_dimension);@/
  put(operator_name,'variables,make_oplist(variables));
end$

@*1 Implementation of exterior multiplication.
Before we can implement the action of a graded vectorfield on a
graded function we need to have a function that computes the
(exterior) multiplication of two elements of $\Lambda(n)$.

If we have two elements EXT($i_1,\dots,i_n$) and
EXT($j_1,\dots,j_m$) then the product will be 0 or an expression of
the form $\pm{}$EXT(\dots). In order to find this result we need to
merge the lists $(i_1,\dots,i_n)$ and $(j_1,\dots,j_m)$ into one
ordered list, taking into account the signs that occur due to the
switching of all pairs of elements of the lists.

In fact, since it is needed for cohomology computations by van den
Hijligenberg and Post, we shall implement an even more general
procedure: given two {\it ordered} lists $(i_1,\dots,i_m)$ and
$(j_1,\dots,j_m)$, return the list which results from merging the two
lists into one ordered lists, together with a sign due to the
switching of indices. The elements of the list need, however, not only
be positive integers anymore, but may also be negative integers, with
the proviso that switching two negative integers does {\it not} cause
a sign.

The algorithm is rather simple: given two lists |x1| and |x2| we
construct the merged list |x2| as follows (the notation |cx1| is an
abbreviation for |car x1|, and the same for all other lists):

\medskip 
\item{1.} reverse |x1| (|x1| is now ordered reversely) and move all
the elements of |x2|, with which the first element of |x1| (i.e.\ the
highest element) has to be interchanged for merging both lists, in
reverse order on the list |lx2|. Keep track if the number of elements
of |lx2| is odd or even with help of the boolean |oddskip|.

\item{2.} if either |x1| or |lx2| is empty return the appropriate
result.

\item{3.} if |cx1=clx2| then we can return |nil| if both are positive,
due to the anticommutativity.

\item{4.} if |cx1>clx2| put |cx1| in front of |x2| and adjust the sign
according to |oddskip| only if |cx1| is positive: if |cx1| is
negative, so are all elements of |lx2| and thus no sign need to be added.
Continue with 2.

\item{5.} if |cx1<=clx2| put |clx2| in front of |x2| and adjust
|oddskip|. Continue with 2.

\enditem
Since it is used quite frequently, we shall implement this procedure
using labels in order to prevent overhead caused by (recursive)
function calls.

@u lisp procedure merge_lists(x1,x2);
begin scalar cx1,cx2,lx2,clx2,oddskip,sign;
@<Prepare |x1|, |x2| and |lx2|, if ready |goto b|@>;
b: @<Weave all elements of |x1| and |lx2| in front of |x2|, return if done@>;
end$

@ The implementation of step 1. 
@<Prepare |x1|, |x2| and |lx2|, if ready |goto b|@>=
    sign:=1;
    x1:=reverse x1;
    if x1 then cx1:=car x1 @+else goto b;
a:  if x2 then cx2:=car x2 @+else goto b;
    if cx1<cx2 then goto b;
    lx2:=cx2 . lx2;@/
    oddskip:=not oddskip;@/
    x2:=cdr x2;@/
    goto a

@ The implementation of steps 2 and 3.
@<Weave all elements of |x1| and |lx2| in front of |x2|, return if done@>=
    if null x1 then @+return sign . nconc(reversip lx2,x2);
    if null lx2 then @+return sign . nconc(reversip x1,x2);
    clx2:=car lx2;
    if cx1=clx2 and cx1>0 then @+return nil;
    if cx1>clx2 then goto b1;
    @<Move first element of |lx2| to |x2| and |goto b|@>;
b1: @<Move first element of |x1| to |x2| and |goto b|@>

@ The implementation of step 5.
@<Move first element of |lx2| to |x2| and |goto b|@>=
    x2:=clx2 . x2;@/
    lx2:=cdr lx2;@/
    oddskip:=not oddskip;@/
    goto b

@ And finally step 4.
@<Move first element of |x1| to |x2| and |goto b|@>=@/
    x2:=cx1 . x2;@/
    x1:=cdr x1;
    if oddskip and cx1>0 then sign:=-sign;
    cx1:=car x1;@/
    goto b

@ It's a piece of cake now the write a procedure for the
multiplication of two ``EXT'' kernels. By definition |ext()| is equal
to 1.

@d sign_of=car
@d arg_list_of=cdr

@u 
lisp procedure ext_mult(x1,x2);
(if null x then nil ./ 1 
 else @+if null arg_list_of x then 1 ./ 1
 else (((!*a2k('ext . arg_list_of x) .^ 1) .* sign_of x) .+ nil) ./ 1)@/
where x=merge_lists(arguments_of x1,arguments_of x2)$

@*=The simplification procedure for vectorfields. 
The only thing left now is to implement the action of a vectorfield
on a function by means of the simplification procedure
|super_der_simp|.

If $V$ is a vectorfield we shall assume that the components of
$\dd{}{x_i}$ and $\dd{}{s_j}$ are given by $V(0,i)$ and $V(1,j)$,
respectively.

Since we want to be able to look at the value of the components, we have to make
the following distinction: if a vectorfield has just one argument it
is the action on a function, otherwise we just have to return the
value of the kernel.

@u
lisp procedure super_der_simp u;
if length u=2 then @<Return the action of the vectorfield on a function@>
else simpiden u$

@ The action is not very complicated: collect all the even and odd
components of the vectorfield and apply the vectorfield to the
numerator and denominator of the function, using the quotient rule.

Notice that we don't want denominators of any function to contain
odd variables, since such an expression can always be rewritten to a
finite expression without odd variables in the denominator.

@<Return the action of the vectorfield...@>= 
begin scalar derivation_name,variables,even_components,odd_components,@|
      splitted_numr,splitted_denr;
  derivation_name:=reval operator_name_of u;@/
  variables:=get(derivation_name,'variables);@/
  u:=simp!* first_argument_of u;
  @<Get the lists |splitted_numr|, |splitted_denr|, |even_components|
and |odd_components|@>;
  return subtrsq(@|
      quotsq(addsq(even_action(even_components,splitted_numr),@|
                   odd_action(odd_components,splitted_numr)), denr u ./ 1),@|
      quotsq(multsq(numr u ./ 1, even_action(even_components,splitted_denr)),@|
             multf(denr u,denr u) ./ 1));
end

@*1 Getting the vectorfield components. 
Finding all linear kernels of an algebraic operator and their
coefficients in a standard form is performed by the procedure
|split_form| of the TOOLS package, which acts on standard forms.
Since it is more convenient for the components of the vectorfield to
have the coefficients returned by |split_form| as standard quotients
instead of standard forms, the following procedure applies
|split_form| to the numerator of a standard quotient and takes care of
the necessary conversion of the coefficients to standard quotients.

In order to allow simple processing of the lists the independent part
must be preceded by |ext()|.

@d independent_part_of=car
@d kc_list_of=cdr
@d kernel_of=car
@d coefficient_of=cdr

@u 
lisp procedure split_ext(sq,op_list);
begin scalar denr_sq,splitted_form;
  denr_sq:=denr sq;
  splitted_form:=split_form(numr sq,op_list);
  return (list('ext) . cancel(independent_part_of splitted_form ./ denr_sq)) . 
    for each kc_pair in kc_list_of splitted_form collect@/
      (kernel_of kc_pair . cancel(coefficient_of kc_pair ./ denr_sq))
end$

@ For a proper action of |even_action| and |odd_action| all components
need to be decomposed into ``EXT'' kernels and their coefficients.
Since the action is most conveniently performed recursively on
standard forms, the numerator and denominator are decomposed at
standard form level.

@<Get the lists ...@>=
  splitted_numr:=split_form(numr u,'(ext));@/
  splitted_numr:=
      (list('ext) . independent_part_of splitted_numr) . kc_list_of splitted_numr;@/
  splitted_denr:=split_form(denr u,'(ext));@/
  splitted_denr:=
      (list('ext) . independent_part_of splitted_denr) . kc_list_of splitted_denr;@/
  even_components:=for i:=1:get(derivation_name,'even_dimension) collect@/
    (nth(variables,i) . split_ext(component,'(ext)))@|
      where component=simp!* list(derivation_name,0,i);@/
  odd_components:=for i:=1:get(derivation_name,'odd_dimension) collect@/
    (i . split_ext(component,'(ext)))@|
      where component=simp!* list(derivation_name,1,i)

@*1 Action of the even components. 
The action of the even part of a vectorfield on a function is fairly
simple at top level: just add the actions on all kernel-coefficient pairs.

@u
lisp procedure even_action(components,splitted_form);
begin scalar action;
  action:=nil ./ 1;
  for each kc_pair in splitted_form do@/
    action:=addsq(action,
      even_action_sf(components,coefficient_of kc_pair,kernel_of kc_pair,1));
  return action;
end$

@ The action on a standard form is the sum of the actions on all
terms. If the last term is a domain element we don't have to take it
into consideration.

@u
lisp procedure even_action_sf(components,sf,ext_kernel,fac);
begin scalar action;
  action:=nil ./ 1;
  while not domainp sf do
    <<action:=addsq(action,even_action_term(components,lt sf,ext_kernel,fac));
      sf:=red sf>>;
  return action;
end$

@ For the action on the leading term we use the derivation property: the
action on the leading power has to be added to the action on the
leading coefficient.  The last argument of |even_action_sf| is the
product of all leading powers which have already been treated and with
which the result has to be multiplied.

For reasons of efficiency it is more convenient to have the factor as
in standard quotient in |even_action_pow|.

@d term_pow=car
@d term_coeff=cdr

@u
lisp procedure even_action_term(components,term,ext_kernel,fac);
addsq(even_action_pow(components,term_pow term,
                           ext_kernel,!*f2q multf(fac,term_coeff term)),@|
      even_action_sf(components,term_coeff term,
                          ext_kernel,multf(fac,!*p2f term_pow term)))$

@ Finally we have to implement the action on leading powers. For this
we have to find all dependencies of the main variable on local coordinates
occuring in the vectorfield, and act accordingly. 

@u
lisp procedure even_action_pow(components,pow,ext_kernel,fac);
begin scalar kernel,n,component,derivative,action,active_components;
  kernel:=car pow; n:=cdr pow;  %|pow=kernel^n|%
  @<If |kernel| is one the even local coordinates, return the action on |pow|@>;
  @<Find all the dependencies of |kernel| and construct |active_components|@>;
  @<Return the sum of the actions of |active_components| on |pow|@>;
end$

@ We can check if |kernel| is one of the local coordinates by a simple
|assoc| on |components|.

@<If |kernel| is one the even ...@>=
if (component:=assoc(kernel,components)) then 
return 
 <<derivative:=if n=1 then 1 ./ 1 @+else ((((kernel .^ n-1 ) .* n) .+ nil) ./ 1);
   action:=component_action(component,ext_kernel,derivative);@/
   multsq(action,fac)>>

@ The procedure |component_action| takes care of returning the sum of all
products of the |kc_pairs| in |component| with |ext_kernel| and
|derivative|.

Recall that super vectorfields have a left $\CinfU\otimes\Lambda(n)$
module structure. This means that we have to take care that the
arguments in the |ext_mult| call have to be in the right order:
components of the vectorfield left and the |ext_kernel|'s from the
function right.  Of course, if the product of the two ``EXT'' kernels
is zero, there is no need to consider the summand.

@d combined_product(x,y,z)=@/multsq(multsq(x,y),z)

@u
lisp procedure component_action(component,ext_kernel,coefficient);
begin scalar action;
  action:=nil ./ 1;
  for each kc_pair in kc_list_of component do@/
    (if numr ext_product then@/
      action:=addsq(action,
        combined_product(ext_product,even_coefficient,coefficient)))@|
  where ext_product=ext_mult(kernel_of kc_pair,ext_kernel),@|
        even_coefficient=coefficient_of kc_pair;
  return action;
end$

@ If a kernel is not one of the local coordinates, it may still depend
on them, in which case we can still differentiate it w.r.t. such a coordinate.

The following procedure tries finds all active components in |kernel|
as completely as possible.

@d  get_dependencies_of(kernel)=
  ((if depl_entry then cdr depl_entry) where depl_entry=assoc(kernel,depl!*))

@u
lisp procedure find_active_components(kernel,components,components_found);
begin 
  components_found:=@|
    update_components(kernel . get_dependencies_of(kernel),
                      components,components_found)$
  if not atom kernel then 
    for each element in kernel do@/
      components_found:=find_active_components(element,components,components_found);
  return components_found;
end$

@ The procedure |update_components| takes care that |components_found|
contains all active components just once.

@u
lisp procedure update_components(dependencies,components,components_found);
begin scalar component;
  for each kernel in dependencies do
    if (component:=assoc(kernel,components)) 
       and not assoc(kernel,components_found) then@/
     components_found:=component . components_found;
  return components_found;
end$

@
@<Find all the dependencies of |kernel| and construct |active_components|@>=@/
active_components:=find_active_components(kernel,components,nil)

@ Once we know all active components we can simply apply |diffp| to
compute the derivatives of |pow| and |component_action| to compute the
action of the different components. Recall that the final result has
to be multiplied with |fac|.

@<Return the sum of the actions of |active_components| on |pow|@>=
action:=nil ./ 1;
for each component in active_components do
 <<derivative:=diffp(pow,kernel_of component);
   action:=addsq(action,component_action(component,ext_kernel,derivative))>>;
return multsq(action,fac)

@*1 Action of the odd components. 
The action of the odd components is much simpler than the action of
the even components since the dependencies are clear at once: the only
dependency on odd variables are the indices of the ``EXT'' kernels.

Odd differentiations can cause an additional sign:
$$
   \dd{}{s_{i_j}}s_{i_1}\dots,s_{i_j},\dots,s_{i_n}=
      (-1)^{j-1}s_{i_1}\dots,\widehat{s_{i_j}},\dots,s_{i_n}
$$
Additional signs are governed by the boolean |sign|.
After the deletion of one index we have to apply |!*a2k| in order to
get a unique kernel.

@u
lisp procedure odd_action(components,splitted_form);
begin scalar action,sign,derivative,kernel,coefficient,component;
  action:=nil ./ 1;
  for each kc_pair in splitted_form do
  <<kernel:=kernel_of kc_pair;@/
    coefficient:=!*f2q coefficient_of kc_pair;@/
    sign:=t;@/
    for each i in arguments_of kernel do
    <<sign:=not sign;@/
      derivative:=!*a2k delete(i,kernel);@/
      component:=assoc(i,components);@/
      action:=addsq(action,
        component_action(component,derivative,
                         if sign then negsq coefficient @+else coefficient))
    >>
  >>;
  return action;
end$

@*=Multiplication of graded expressions. Since it is useful in
practical problems, we shall finally implement a procedure
|super_product| for multiplying two graded expressions. Using some of
the above procedures this is not difficult at all.

@u
lisp operator super_product;
lisp procedure super_product(x,y);
begin scalar splitted_x,splitted_y,product;
  splitted_x:=split_ext(simp x,'(ext));
  splitted_y:=split_ext(simp y,'(ext));@/
  product:=nil ./ 1;
  for each term_x in splitted_x do
    for each term_y in splitted_y do@/
      product:=addsq(product,@|
                 combined_product(coefficient_of term_x,coefficient_of term_y,@|
                                  ext_mult(kernel_of term_x,kernel_of term_y)));
  return mk!*sq subs2 product;
end$

@ The end of a REDUCE input file must be marked with |end|.

@u end;

@*=Index. This section contains a cross reference index of all
identifiers, together with the numbers of the mdules in which they are
used. Underlined entries correspond to module numbers where the
identifier was declared.