% Copyright (c) 1991 Marcel Roelofs, University of Twente, Enschede,
% The Netherlands.
%
% $Header: tools.web,v 1.4 92/02/06 17:32:32 roelofs Exp $
%
\input specification
\def\Version$#1Revision: #2 ${Version #2}
\def\title{TOOLS}
\font\titlefont=cmcsc10 scaled\magstep3
\font\ttitlefont=cmtt10 scaled\magstep4
\def\topofcontents{\null\vfill
\centerline{\titlefont The {\ttitlefont TOOLS} package for REDUCE}
\vskip15pt\centerline{\Version$Revision: 1.4 $}
\vskip15pt\centerline{\sc Marcel Roelofs}\vfill}
@* Introduction. In this \.{RWEB} file we will describe some tools
which facilitate working with algebraic operators and can be seen as
rather general extensions to REDUCE. At the moment these tools
are:\medskip
\item{1.}Procedures to find one or all kernels of some specified
algebraic operators in a standard form.
\item{2.}The procedure |operator_coeff|, which is the analogue of the
standard REDUCE procedure |coeff| for kernels of operators. The
procedure |operator_coeff| is intended for expressions which are
linear with respect to kernels of some specified algebraic operators
and returns a list of these kernels, together with their coefficients.
Related to this procedure is the procedure |independent_part| which
extracts the part of an expression, not being a polynomial expression
in kernels of some operators.
\item{3.} The procedure |multi_coeff|, for finding the coefficients of
the basis elements of a polynomial ring in an arbitrary number of
variables.
\item{4.} The procedure |simp_multilinear| to simplify a multilinear
operator.
\item{5.}The procedure |linear_solve| to solve linear expressions
with respect to some specified kernel.
\item{6.}The procedure |solvable_kernels| which analyses if an
algebraic expression is linear with respect to kernels of some
specified operators and returns all those kernels for which the
coefficients do not depend on other operators. \medskip
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="Algebraic operator tools for REDUCE 3.4, $Revision: 1.4 $"
@ We define the following macros for clarity. The reading of the file
is done in symbolic mode.
@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) @;
@u change_to_symbolic_mode$@/
write banner$ terpri()$@/
change_to_algebraic_mode$
@ The following macros are intended as common programming idioms.
@d incr(x) = (x:=x+1)@;
@d decr(x) = (x:=x-1)@;
@* Finding kernels of operators in standard forms. If one wants
perform a lot of automated computations on algebraic expressions
containing algebraic operators, it is very convenient to have a
procedure that extracts one or more kernels of some specified
operator(s) from these algebraic expressions automatically. For this
purpose we will write the procedures |get_first_kernel|,
|get_all_kernels| and |get_recursive_kernels| which extract one or all
kernels from standard forms. We have chosen to let the procedures act
on standard forms, because algebraic expressions are recursively built
up out of standard forms. Therefore, in doing so, the searching can
be done in an easy to understand recursive manner.
A kernel of an operator looks like |a(1,2)| or |a()|, in general an
algebraic operator together with its arguments. In lisp mode these
kernels look like lists, the |car| of which is an algebraic
operator, the |cdr| being its arguments.
@ \specs |@!get_first_kernel|, |@!get_all_kernels| and |@!get_recursive_kernels|.
\descr Syntax: \descno 1.|get_first_kernel(form,oplist)|,\nl
\descno 2.|get_all_kernels(form,oplist)|,\nl
\descno 3.|get_recursive_kernels(form,oplist)|.
\descr Arguments:
\arg |form|: standard form.
\arg |oplist|: identifier or (algebraic or lisp) list of identifiers,
which should be algebraic operator(s).
\descr Result: \descno 1.
the first kernel of operator(s) on
|oplist| occuring in |form| at top level,
i.e.\ not occuring as argument of another
operator.\nl
\descno 2.a (lisp) list of all kernels of
operator(s) on |oplist| occuring in |form| at
top level.\nl
\descno 3.a (lisp) list of all kernels of
operator(s) on |oplist| ocurring in
|form| at any level.
@ The actual work of the procedures described above is done by
recursive procedures one level below, which examines the main variable
for the desired kernels and recursively examines the leading
coefficient and the reductum (which are also standard forms). These
recursive procedures have three arguments, the standard form involved,
the list of operators and a list of kernels found so far
(initially |nil|).
The following macro definition makes sure that the second argument
becomes a lisp list of identifiers.
@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 @;
@ The first procedure we want to discuss is
|get_first_kernel(form,oplist)|. It returns the first occurence of a
kernel of the specified operators occuring at top level. We can stop
examining the standard form if we encounter a domain element.
@u lisp procedure get_first_kernel(form,oplist);
gfk(form,make_oplist(oplist),nil)$@#
lisp procedure gfk(form,oplist,l);
if l or domainp form then l
else gfk(red form,oplist,
gfk(lc form,oplist,
if not atom x and member(car x,oplist)
then x @+else l))
where x=mvar form$
@ The procedure |get_all_kernels(form,oplist)| returns a list of all kernels
of the specified operators occuring in |form| at top level. In |gak|
we use |aconc| instead of |cons| to add new kernels to |l|. We do
this because most times we want to actually use the list obtained to
reorder the standard form and in this way the reordering can be minimized.
@u
lisp procedure get_all_kernels(form,oplist);
gak(form,make_oplist(oplist),nil)$@#
lisp procedure gak(form,oplist,l);
if domainp form
then l
else gak(red form,oplist,
gak(lc form,oplist,
if not atom x and member(car x,oplist) and not member(x,l)
then l:=aconc(l,x) @+else l))@|
where x=mvar form$
@ The procedure |get_recursive_kernels(form,oplist)| returns a list of all
kernels of the specified operators occuring at any level in |form|
(i.e. as main variables, arguments, arguments of arguments, etc).
@u
lisp procedure get_recursive_kernels(form,oplist);
grk(form,make_oplist(oplist),nil)$@#
lisp procedure grk(form,oplist,l);
if domainp form
then l @+else grk(red form,oplist,
grk(lc form,oplist,@|
@))
where x=mvar form$
@ We don't want to use the list obtained by |grk|
for reordering, so here new operator elements are simply added to |l| by
|cons|.
@=
if not atom x
then begin scalar y;
for each arg in cdr x do
if (y:=simp arg) neq 0 then
l:=grk(numr y,oplist,l);
return if member(car x,oplist) and not member(x,l)
then x . l @+else l end
else l@;
@* Finding coefficients of operator expressions. In REDUCE there is
an easy way to get all coefficients of an algebraic expression
regarded as polynomial expression w.r.t.\ some kernel, namely the
procedure |coeff|. However, there is no mechanism available to get
all coefficients of an algebraic expression regarded as a linear
expression w.r.t.\ kernels of some specified operators, whereas such a
mechanism is very often needed if one wants to do automated
computations on expressions containing algebraic operators.
Therefore, in this section we will write the analogue of the procedure
|coeff| for kernels of some specified operators, the procedure
|operator_coeff|.
@
\spec |@!operator_coeff|.
\descr Syntax:|operator_coeff(exprn,oplist)|.
\descr Arguments:
\arg |exprn|: algebraic expression.
\arg |oplist|: identifier or (algebraic or lisp) list of identifiers,
which should be algebraic operator(s).
\descr Result: returns an algebraic list, the first element of which
is the part of |exprn| being independent of
operator(s) on |oplist|, followed by zero or more
algebraic lists consisting of kernels of operators on
|oplist| and their coefficients in |exprn|. Here we
regard |exprn| to be a linear expression with respect
to all kernels of operator(s) on |oplist|. Before
the analysis, |exprn| is simplified.
\descr Errors: stops with an error message if |exprn| is not linear with
respect to all kernels of operator(s) on |oplist|.
\descr Examples: the call |operator_coeff(2*x(1)+3*y(2)+5*z(3),{x,y})| returns
the list \30|{5*z(3),{x(1),2},@/{y(2),3}}|, whereas
|operator_coeff(x(1)*x(2),x)| stops with an error message.
@ Keeping in mind the procedure |get_all_kernels| we have written
above, it is not difficult to think of how the procedure
|operator_coeff| could act: first get a list of all desired kernels
with help of |get_all_kernels| and reorder the numerator of |exprn|
w.r.t.\ this list. Once one has done so, one is sure that, in case of
linearity, all desired kernels occur as a main variable in a reduced
part of the numerator and it's a piece of cake to check the linearity
and to construct the desired list. In fact this is the way the first
version of |operator_coeff| worked.
Unfortunately it is not the most efficient way to obtain the
desired result, since the numerator of |exprn| is scanned twice,
namely in the procedures |get_all_kernels| and |reorder|.
In the current version we will scan the expression $E$ only
once and at the same time construct a list $L$, which contains the
part of $E$ independent of operators on |oplist| together with all
kernels of operators on |oplist| and their coefficients and which is
almost ready for returning.
As in the first version scanning is performed on standard forms. The
actual version is based on the following fact: a standard form consist
of a number of standard terms $T_i$, each of which is the product of a
leading power $P_i$ and its coefficient $C_i$ which again is a
standard form. In the sequel we will assume that the switch |exp| is
|on|; this a legal assumption because otherwise |coeff|'ing and also
|operator_coeff|'ing would become rather useless. We can now find all
the kernels of operators on |oplist| and their coefficients in a
standard term $T_i$ if we distinguish between the following
situations:\medskip
\item{1.} $T_i$ is |nil|. We have to take no action.
\item{2.} $T_i$ is a domain element. In particular it is not a kernel
of one of the operators on |oplist|, hence we can add up $T_i$ to the
independent part of $L$.
\item{3.} The main variable of $P_i$ is a kernel of one of the
operators on |oplist| (the fact that |exp| is |on| assures us that
the main variable is a kernel). If the leading degree is 1 and $C_i$
does not contain kernels of operators on |oplist|, we can update $L$,
otherwise we have to stop with an error message because the expression
is not linear w.r.t. the operators on |oplist|.
\item{4.} The main variable of $P_i$ is not a kernel of one of the
operators on |oplist|. We can recursively examine $C_i$ for the
occurence of appropriate kernels, if we keep in mind that the
coefficients of kernels found there have to be multiplied with the
additional factor $P_i$. \medskip
@ The actions described above are implemented in the procedure
|split_f|, which examines the leading term and recursively the
reductum. The third argument |fact| is the standard form
representing the product of all previous factors, by which the
coefficients of kernels found in |form| have to be multiplied. Hence at
top level it has to be initialized to 1. |kc_list| is a
dotted pair the |car| of which is the part of the expression
independent of operators on |oplist|, the |cdr| an association list of
kernels and (standard form) coefficients. At top level it has to be
initialized to |nil . nil|.
@u
lisp procedure split_f(form,oplist,fact,kc_list);
if null form then kc_list
else if domainp form then
addf(multf(fact,form),
car kc_list) . cdr kc_list
else if not atom mvar form and member(car mvar form,oplist) then
if not ldeg form = 1 or get_first_kernel(lc form,oplist) then
stop_with_error("SPLIT_F: expression not linear w.r.t.",
'list . oplist,nil,nil)
else split_f(red form,oplist,fact,
update_kc_list(kc_list,mvar form,multf(fact,lc form)))
else split_f(red form,oplist,fact,
split_f(lc form,oplist,
multf(fact,!*p2f lpow form),kc_list))$
@ For convenience we will write a surrounding procedure
|split_form|, which can be called at top level and initializes the
third and fourth argument of |split_f|
@u
lisp procedure split_form(form,oplist);
split_f(form,oplist,1,nil . nil)$
@ For updating the |kc_list| as efficient as possible we
need an |assoc|-like procedure |list_assoc|. If applied to an
association list $L$, this procedure returns the remainder of $L$, the
|car| of which would be the result of |assoc| applied to $L$.
@u lisp procedure list_assoc(car_exprn,a_list);
if null a_list then a_list else if caar a_list= car_exprn then a_list
else list_assoc(car_exprn,cdr a_list)$
@ In order to update the |kc_list| we first have to find out
if the kernel w.r.t.\ which we update the list, is already occuring on
it. If so, we have to adjust its coefficient, otherwise we can |cons|
the kernel and coefficient in front of the list. Adjusting a
coefficient is performed by using the procedures |list_assoc| and
|rplaca| in order to avoid rebuilding of the entire list. The reader
should verify that |rplaca| does not do any harm in this application,
since it is replacing a list.
@u lisp procedure update_kc_list(kc_list,kernel,coefficient);
(if rest_list then @+<> else
car kc_list . (kernel . coefficient) . cdr kc_list)
where rest_list=list_assoc(kernel,cdr kc_list)$
@ The procedure |operator_coeff| should be available in algebraic mode.
We will, however, not make it an ordinary lisp operator, since this
leads to unnecessary simplifications of the arguments and the result
of |operator_coeff| (this is done in the standard REDUCE procedure
|reval1|). Instead we will give |operator_coeff| the property |psopfn|
with value |operator_coeff_1|. By this declaration the arguments of
|operator_coeff| are passed to the procedure |operator_coeff_1| as one
unevaluated list and the result is returned without further
simplification.
The procedure |operator_coeff_1| only checks for the right number of
arguments, and passes them as genuine arguments to the lisp procedure
|operator_coeff|. This means that we have access to |operator_coeff|
in both algebraic and symbolic mode with the same appearance. In
algebraic mode, however, the lisp procedure |operator_coeff| is not
directly accessible (since it is not an lisp operator) but only via
the construction described above. In symbolic mode |operator_coeff| is
called directly.
@u
put('operator_coeff,'psopfn,'operator_coeff_1)$
@#
lisp procedure operator_coeff_1 u;
if length u neq 2 then rederr("OPERATOR_COEFF: wrong number of arguments")
else operator_coeff(car u,reval cadr u)$
@ The real work is done by the procedure |operator_coeff|, which
is quite simple: simplify the expression |exprn|, get its numerator,
and finally apply |split_form| to it. After that we have to divide all
coefficients by the denominator of |exprn| and convert the list
returned by |split_form| into a list of algebraic lists.
To simplify |exprn| we use |simp!*| instead of |simp| because |exprn|
may sometimes be an expression which hasn't been simplified before
(like an argument of some other simplification procedure), so we want
a full simplification of |exprn| including a call of |subs2|, which is
done by |simp!*|.
In order to admit the second argument of |operator_coeff| to be a
single operator as well as a list of operators we use the macro
|make_oplist| described above.
@u
lisp procedure operator_coeff(exprn,oplist);
begin scalar numr_ex,denr_ex,kc_list;
oplist:=make_oplist(oplist);
exprn:=simp!* exprn;numr_ex:=numr exprn;denr_ex:=denr exprn;
kc_list:=split_form(numr_ex,oplist);
return 'list . !*ff2a(car kc_list,denr_ex) .
for each kc_pair in cdr kc_list collect@|
list('list,car kc_pair,!*ff2a(cdr kc_pair,denr_ex));
end$
@ Sometimes we are only interested in the part of an expression
independent of some operators instead of in the whole kernel
coefficient list. Of course one can apply |operator_coeff| to the
expression and get the independent part of it, but in time critical
applications it is better to have a procedure |dump_operators| that
only performs the essential actions of the procedure |split_f|,
together with surrounding procedures |independent_part| and
|independent_part_1|.
The basic ideas to get the independent part of an expression during
the scan of a standard form are exactly those underlying the procedure
|split_f|, except that updating the kernel coefficient list is
replaced by doing nothing. Notice that we have skipped the checks for
linearity, hence |independent_part| is even more general than
|operator_coeff| in the sense that we can also get the independent
part of an expression which is not linear w.r.t.\ all kernels of the
specified operator(s).
However, we can get rid of the last argument |kc_list| of |split_f|,
since we can simply add up all independent parts using |addf|.
@u
lisp procedure dump_operators(form,oplist,fact);
if null form then nil
else if domainp form then multf(fact,form)
else if not atom mvar form and member(car mvar form,oplist) then @|
dump_operators(red form,oplist,fact)
else
addf(dump_operators(red form,oplist,fact),@|
dump_operators(lc form,oplist,multf(fact,!*p2f lpow form)))$
@ We copy the surrounding procedures without further comment.
@u
put('independent_part,'psopfn,'independent_part_1)$
@#
lisp procedure independent_part_1 u;
if length u neq 2 then rederr("INDEPENDENT_PART: wrong number of arguments")
else independent_part(car u,reval cadr u)$
@#
lisp procedure independent_part(exprn,oplist);
begin scalar numr_ex,denr_ex;
oplist:=make_oplist(oplist);
exprn:=simp!* exprn;@/numr_ex:=numr exprn;denr_ex:=denr exprn;
return !*ff2a(dump_operators(numr_ex,oplist,1),denr_ex);
end$
@ The successful implementation of |operator_coeff| inspires us to
also introduce a more general version of |coeff|, namely a procedure
for finding the coefficients of basis elements of polynomial rings in
an arbitrary number of variables. Given a list |kernel_list| of
generators of such a ring, we can find all all basis elements and
their coefficients together with the independent part of a standard
form $F$ by analysing each standard term $T_i$ in $F$ in the following
way, where $P_i$ and $C_i$ have the same meaning as in the
introduction to the procedure |split_f|:\medskip
\item{1.} $T_i$ is |nil|. We have to take no action.
\item{2.} $T_i$ is a domain element. In particular does not contain a
kernel of one of the generators on |kernel_list|, hence we can add up
$T_i$ to the independent part of $L$.
\item{3.} The main variable of $P_i$ is a kernel occuring in
|kernel_list| (again the fact that |exp| is |on| assures us that the
main variable is a kernel). Hence $T_i$ will give rise to at least one
basis element. At the time being we cannot, however, be sure about the
final form of the basis element, since $C_i$ may contain additional
factors. Therefore we will add $P_i$ to the variable |multi_power|
which is the list of powers found so far. Here we explicitly use the
fact that the ordering of standard forms assures us that the powers of
basis elements found twice in $F$ will be stored on |multi_power| in
exactly the same order.
\item{4.} The main variable of $P_i$ is not a kernel occuring in
|kernel_list|. We can recursively examine $C_i$ for the occurence of
appropriate kernels, if we keep in mind that the coefficients of
kernels found there have to be multiplied with the additional factor
$P_i$. \medskip
The analysis described above is implement in the procedure
|multi_split_f|.
@d update_pc_list=update_kc_list
@u
lisp procedure multi_split_f(form,kernel_list,multi_power,fact,pc_list);
if null form then pc_list
else if domainp form then
if multi_power then update_pc_list(pc_list,multi_power,multf(fact,form))
else addf(multf(fact,form),car pc_list) . cdr pc_list
else multi_split_f(red form,kernel_list,multi_power,fact,
if member(mvar form,kernel_list) then @|
multi_split_f(lc form,kernel_list,lpow form . multi_power,fact,pc_list)
else multi_split_f(lc form,kernel_list,multi_power,
multf(fact,!*p2f lpow form),pc_list))$
@ As usual |multi_power|, |fact| and |pc_list| have to initialized to
1 and |nil . nil|, respectively, at top level. Again we have a
surrounding procedure |multi_split_form| to take care of this.
@u
lisp procedure multi_split_form(form,kernel_list);
multi_split_f(form,kernel_list,nil,1,nil . nil)$
@ At algebraic level we want to have a procedure
|multi_coeff(exprn,kernel_list)| to our disposal, with |exprn| the
multivariate expression to be analysed and |kernel_list| the list
generators of the polynomial ring. The result of |multi_coeff| is a
list, the first part of which is the independent part, followed by
zero or more pairs of basis elements with their coefficients. Notice
that unlike |coeff| returns its result in a sparse way.
In order to avoid unnecessary simplification we will again use the
|psopfn| mechanism to make |multi_coeff| available in algebraic mode.
@u
put('multi_coeff,'psopfn,'multi_coeff_1)$
@#
lisp procedure multi_coeff_1 u;
if length u neq 2 then rederr("MULTI_COEFF: wrong number of arguments")
else multi_coeff(car u,reval cadr u)$
@ There is no use of analysing the numerator of |exprn| if it is
not polynomial in the variables in |kernel_list|. Therefore we have to
check that the denominator of |exprn| does not depend on any of the
variables in |kernel_list|, before applying |multi_split_form| to the
numerator of |exprn|.
@u lisp procedure multi_coeff(exprn,kernel_list);
begin scalar numr_ex,denr_ex,pc_list;
kernel_list:=make_oplist(kernel_list);
exprn:=simp!* exprn;@/
numr_ex:=numr exprn;denr_ex:=denr exprn;
for each generator in kernel_list do if depends(denr_ex,generator)
then stop_with_error(@|"MULTI_COEFF: expression is not polynomial w.r.t. ",
'list . kernel_list,nil,nil);
pc_list:=multi_split_form(numr_ex,kernel_list);
return 'list . !*ff2a(car pc_list,denr_ex) .
for each pc_pair in cdr pc_list collect@|
list('list,convert_multi_power car pc_pair,!*ff2a(cdr pc_pair,denr_ex));
end$
@ A |multi_power| returned by |multi_split_f| is a list of standard
powers, i.e. dotted pairs, the |car| of which are leading variables, the
|cdr| leading degrees. For use in algebraic expression we have to
convert it to the proper product of powers. Of course if the leading
degree is 1, we can omit it from the result.
@u
lisp procedure convert_multi_power multi_power;
'times . for each power in multi_power collect
if cdr power=1 then car power else list('expt,car power,cdr power)$
@* Simplifying multilinear operators. In REDUCE there is a rather
elementary construct for dealing with operators that are linear in one
argument. Using the procedures written above it is not very hard to
deal with multilinear operators, if we take the notion of linearity as
introduced above. Therefore we will introduce multilinear operators
as a new type of operators in REDUCE by implementing a new
simplification procedure |simp_multilinear| for multilinear operators
and at the same time implement a |multilinear| statement to set up an
environment for multilinear operators.
Before we continue, let us give a more detailed description of what we
understand by multilinearity exactly. If $P$ is multilinear operator
w.r.t.\ operators $P_1,\dots,P_n$ and the result of |operator_coeff|
applied to an expression $a_k$ w.r.t.\ the operators $P_1,\dots,P_n$
is $$ a_k=f_{k,0}+\sum_{i_k=1}^{N_k} f_{k,i_k}p_{k,i_k}=
\sum_{i_k=0}^{N_k} f_{k,i_k}p_{k,i_k}\qquad\hbox{with $p_{k,0}=1$}$$
where $f_{k,0}$ is the part of $a_k$ independent of one of the
operators $P_1,\dots,P_n$ and $p_{k,i_k}$ are operator elements of one
of the operators $P_1,\dots,P_n$, then $P(a_1,\dots,a_m)$ must be
simplified to
$$P(a_1,\dots,a_m)=\sum_{i_1=0}^{N_1}\cdots\sum_{i_m=0}^{N_m}
f_{1,i_1}\cdots f_{m,i_m} P(p_{1,i_1},\dots,p_{m,i_m})$$ To give an
example, suppose that \\{wedge} is an operator representing the
exterior multiplication of differential geometry and suppose that we
have declared \\{wedge} to be multilinear w.r.t.\ to \\{wedge} and $d$,
then $\\{wedge}(x+f(1)+d(1),wedge(d(1),d(2)))$ will be simplified to
$(x+f(1))*\\{wedge}(1,wedge(d(1),d(2)))+\\{wedge}(d(1),\\{wedge}(d(1),d(2)))$
where the components have to be simplified separately to take account
for any other properties of exterior multiplication.
@ The first step of simplifying a multilinear operator is splitting up
its arguments. We can do this by applying |split_form| to the
numerators of all arguments and at the same time keep track of the
product of the denominators of all arguments, since the final result
of the simplification has to be divided by this product.
The actions necessary for splitting the arguments and keeping track of
the denominators are implemented in the procedure |split_arguments|.
The result (and third argument) |splitted_list| of |split_arguments|
is a dotted pair, the |car| of which is the product of all
denominators as a standard form, the |cdr| being the list of results
of |split_form| applied to the numerator of all arguments in reverse
order. |split_arguments| applied to a list of arguments |arg_list|,
processes the first argument by updating the product of denominators
and |cons|'ing the result of |split_form| applied to the numerator of it
in front of the list of splitted arguments, and recursively splits the
rest of the arguments. Hence at top level |splitted_list| has to be
initialized to |1 . nil|.
The procedure |split_arguments| is normally called from within a
simplification procedure. This means that the arguments have not been
simplified before. Therefore we must enforce full simplication of
these arguments by applying |simp!*| to them before processing.
@u
lisp procedure split_arguments(arg_list,oplist,splitted_list);
if null arg_list then splitted_list
else split_arguments(cdr arg_list,oplist,
multf(denr first_arg,car splitted_list) . @|
split_form(numr first_arg,oplist) .
cdr splitted_list) @|where first_arg=simp!* car arg_list$
@ For convenience we will write a surrounding procedure
|split_operator|, in order to hide the last two arguments of
|split_arguments|. Its only argument is an operator element, the
arguments of which are to be splitted. For its proper operation it
assumes that the multilinear operator under consideration has the
property |oplist|, which is the list of operators w.r.t.\ which the
operator is multilinear.
@u lisp procedure split_operator u;@/
split_arguments(cdr u,get(car u,'oplist),1 . nil)$
@ Once we have a list of splitted arguments we can build up the sum of
operator elements of all possible combinations of components of the
(splitted) arguments. Since the list of splitted arguments is stored
in reverse order, this can be done most conveniently by recursive
procedures. If we consider one (splitted) argument of the operator
under consideration as a list of components, and the whole argument
list of the operator as a stack of component lists, we can build up
the sum by applying two recursive procedures |process_arg_stack|,
|process_comp_list| to the argument stack and component list(s)
respectively.
The procedure |process_arg_stack| and |process_comp_list| work as follows.
The procedure |process_arg_stack| applies the procedure
|process_comp_list| to the first component list of the argument stack
it has been offered.
The procedure |process_comp_list| applies the procedure
|process_independent_part| to the independent part of the component
list and adds it to the result of applying |process_components| to the
other components.
The procedure |process_components| takes the first component of the
component list it has been offered and |cons|'es the kernel part of
this component in front of the argument list of the elementary
operator element being built up and updates the factor with which this
elementary operator element has to be multiplied at the end by
multiplying it with the coefficient part of the component being
processed. Now, if the remaining part of the argument stack is
empty the argument list of the elementary operator element is ready
and we can simplify it, multiply it with the product of the
coefficients and add it to the result (in fact this is done in the
procedure |process_arg_stack|). Otherwise we must continue to build an
argument list of an elementary operator element by applying
|process_arg_stack| to the remaining part of the argument stack.
Finally |process_components| has to be applied on the remaining part of
the component list being processed. The procedure
|process_independent_part| takes the similar actions appropriate for
the independent part of a component list.
Throughout the calls of all procedures explained above we need to
know what is the current argument list and the current factor being
built up. We therefore pass them to all procedures as the arguments
|arg_list| and |fact|, which is the factor being build up as a
standard form. Hence it is clear that the argument list and the factor
have to be initialized to |nil| and 1, respectively.
@ We mentioned that the elementary operator elements have to be
simplified before they can be added. It would, however, be unwise
simply to apply |simp| since the operator under consideration will
have the procedure |simp_multilinear| as its simplification
function\dots, leading to an infinite loop. For ordinary cases
applying |simpiden| will be sufficient, but since we wish to take
account for use of multilinear operators in special packages, we will
add to each multilinear operator a property |resimp_fn|, which is the
simplification function to be applied to an elementary operator
element.
With this knowledge we can implement the procedure |process_arg_stack|
right away. Note that |fact| has to be converted into a standard
quotient before multiplying the (simplified) operator kernel with it.
This is done with help of the procedure |!*f2q|.
@u lisp procedure process_arg_stack(arg_stack,op_name,arg_list,fact);
if null arg_stack then multsq(!*f2q fact,
apply1(get(op_name,'resimp_fn),op_name . arg_list))
else process_comp_list(car arg_stack,cdr arg_stack,op_name,arg_list,fact)$
@ The procedure |process_comp_list| consists of adding the results of
applying |process_independent_part| and |process_components| to the
current component list.
@u
lisp procedure process_comp_list(comp_list,arg_stack,op_name,arg_list,fact);
addsq(process_independent_part(car comp_list,arg_stack,op_name,arg_list,fact),
process_components(cdr comp_list,arg_stack,op_name,arg_list,fact))$
@ Following our description of multilinearity, processing the
independent part of an argument boils down to multiplying |fact|
with it and adding the argument 1 to |arg_list|. If, however, the
independent part is |nil|, i.e.\ the operator element being built up
will contain a zero argument, thanks to multilinearity this operator
element will not contribute to the result and we can return |result|
immediately.
@u lisp procedure process_independent_part(independent_part,arg_stack,
op_name,arg_list,fact);
if null independent_part then nil . 1
else
process_arg_stack(arg_stack,op_name,1 . arg_list,@|multf(fact,independent_part))$
@ The procedure |process_components| has to process the |comp_list|
until there are no more components of the argument being processed.
@u lisp procedure process_components(comp_list,arg_stack,op_name,arg_list,fact);
if null comp_list then nil . 1
else
addsq(process_components(cdr comp_list,arg_stack,op_name,arg_list,fact),
process_arg_stack(arg_stack,op_name,caar comp_list . arg_list,
multf(fact,cdar comp_list)))$
@ To hide the rather illogical arguments of |process_arg_stack| we will
write a surrounding procedure |build_sum| for it. Recall that
|arg_list| and |fact| have to be initialized to |nil| and 1,
respectively.
@u lisp procedure build_sum(op_name,arg_stack);@/
process_arg_stack(arg_stack,op_name,nil,1)$
@ With the procedures written above, the simplification function
|simp_multilinear| can be written at once. We recall that the result
of |split_arguments| is a dotted pair, the |car| of which is the
product of the denominators of all arguments, the |cdr| the list of
splitted arguments, a argument stack.
For simplifying a multilinear operator it is clear that we need to
know the operator name, in other words the |car| of the argument
offered to |simp_multilinear| must be the operator name. To achieve
this we must flag the operator under consideration |full|.
@u lisp procedure simp_multilinear u;
quotsq(build_sum(car u,cdr splitted_list),!*f2q car splitted_list) @|
where splitted_list=split_operator u$
@ The last step towards a successful introduction of multilinear
operators in REDUCE, is the implementation of a procedure
|multilinear| to set up the right environment for multilinear
operators. It is our purpose to give meaning to the declaration
$$\hbox{\\{multilinear} $P$(operator${}\mid{}$list of operators
[,resimplification function]);}$$ as to declare $P$ a multilinear
operator w.r.t.\ the operator(s) of the first argument and, if
present, with the second argument as it's |resimp_fn|, otherwise
|simpiden| if $P$ doesn't already possess a simpliciation or
resimplification function.
@ If we give |multilinear| the property |stat| with value |rlis| in
order to allow for more multilinear declarations at a time, the
declaration \\{multilinear} $P_1(\dots),\dots,P_n(\dots)$ will lead to
the call $\\{multilinear} ((P_1\ \dots)\ {\dots}\allowbreak (P_n\ \dots))$. With
this knowledge the source of |multilinear| is rather straightforward.
Notice that since |stat=rlis| the procedure |multilinear| need not be
a lisp operator.
@u
put('multilinear,'stat,'rlis)$@#
lisp procedure multilinear u;
for each decl in u do
begin scalar op_name,resimp_fn;
if length decl neq 2 and length decl neq 3 then@|
stop_with_error(nil,decl,"invalid multilinear declaration",nil);
if not idp(op_name:=car decl) then
stop_with_error(nil,op_name,"invalid as operator",nil);
put(op_name,'oplist,make_oplist(cadr decl));
if (length decl=3 and (resimp_fn:=caddr decl)) or
(resimp_fn:=get(op_name,'resimp_fn)) or@|
(resimp_fn:=get(op_name,'simpfn)) then put(op_name,'resimp_fn,resimp_fn)
else put(op_name,'resimp_fn,'simpiden);
put(op_name,'simpfn,'simp_multilinear);
flag(list(op_name),'full);
end$
@* Solving linear expressions. We prefer not to use the REDUCE
procedure |solve| for solving a kernel from an algebraic expression
which we demand to be linear w.r.t.\ that kernel, because |solve|
doesn't check for linearity and can give more than one solution in
case of non linearity. Therefore we will write two quite
straightforward procedures which do the job properly.
@ \specs |@!linear_solve|, |@!linear_solve_and_assign|.
\descr Syntax: \descno 1. |linear_solve(exprn,kernel)|,\nl
\descno 2. |linear_solve_and_assign(exprn,kernel)|.
\descr Arguments:
\arg |exprn|: algebraic expression.
\arg |kernel|: kernel.
\descr Result:
\descno 1. solves |exprn| for |kernel| and returns the
solution, regarding |exprn| to be a linear equation w.r.t.\
|kernel|. Before solving, |exprn| is simplified.\nl
\descno 2. as |linear_solve|,
but also sets |kernel| equal to this solution.
\descr Errors: stops with an error message if |kernel| is not a
kernel, or if |exprn| is not linear w.r.t.\ |kernel|.
@ The procedure |linear_solve| should be available in algebraic mode.
We will use the same construction as for |operator_coeff| in order to
avoid unnecessary simplification.
@u
put('linear_solve,'psopfn,'linear_solve_1)$
@#
lisp procedure linear_solve_1 u;
if length u neq 2 then
rederr("LINEAR_SOLVE: wrong number of arguments")
else linear_solve(car u,cadr u)$
@ If we are given an expression |exprn| linear in some kernel
|kernel|, we should be aware that |exprn| may be multiplied by some
factors, which might give trouble when solving the equation. In order
to prevent this we will first determine the factor depending on
|kernel|. For this purpose we shall use the standard REDUCE procedure
|fctrf| which finds all factors in a standard form as a list
containing the first factor as a standard form and all other factors
as a standard quotient. If there are more factors depending on
|kernel|, the system is not linear and we can return with an error
message.
@=
exprn:=fctrf numr simp!* exprn;@/
exprn:=if domainp car exprn then cdr exprn @+else (car exprn . 1) . cdr exprn;
form:=for each factor in exprn join@+
if depends(factor,kernel) then list factor;
if length form=1 then form:=numr car form else
stop_with_error("LINEAR_SOLVE: expression not linear with respect to",
kernel,nil,nil)
@ The linearity of |form| can be checked rather easily: reorder form
w.r.t.\ |kernel|. After this, |form| is linear w.r.t.\ |kernel| if and
only if the main variable of |form| is |kernel|, the leading degree of
|form| is 1 and the leading coefficient and the reductum of |form| do
not depend on |kernel|.
At this place it is convenient to explain how reordering of kernels is
performed in REDUCE. In algebraic mode the kernel ordering can be
affected by the command |korder|. This command puts all kernels
following it on the list |kord!*| (a fluid system variable) and forces
reevaluation of all algebraic expressions. The actual reordering is
done by the procedure |reorder| which reorders standard forms using
the list |kord!*|.
If we declare |kord!*| to be local within all procedures where we want
to reorder standard forms, we don't have to worry about the kernel
ordering afterwards, because the values of fluid variables, which are
used locally within a procedure, are saved on a stack when entering
the procedure and restored after leaving it.
The procedure |!*a2k| checks whether |kernel| is a kernel.
@u
lisp procedure linear_solve(exprn,kernel);
begin scalar kord!*,form;
kernel:=!*a2k kernel;
@;
setkorder list kernel;
form:=reorder form;
if (mvar form=kernel) and (ldeg form =1) and
not depends(lc form,kernel) and not depends(red form,kernel) then
return !*ff2a(negf red form,lc form)
else stop_with_error("LINEAR_SOLVE: expression not linear with respect to",
kernel,nil,nil);
end$
@ |linear_solve_and_assign| can simply use the procedures |setk| and
|linear_solve|. It will also get the |psopfn| mechanism to make it
available in algebraic mode.
@u
put('linear_solve_and_assign,'psopfn,'linear_solve_and_assign_1)$
@#
lisp procedure linear_solve_and_assign_1 u;
if length u neq 2 then
rederr("LINEAR_SOLVE_AND_ASSIGN: wrong number of arguments")
else linear_solve_and_assign(car u,cadr u)$
@#
lisp procedure linear_solve_and_assign(exprn,kernel);
setk(kernel,linear_solve(exprn,kernel))$
@* Restricted solving of linear expressions. In our programs we want
to do a lot of automated computations on algebraic expressions
containing algebraic operators. In particular we think it is
convenient to have, together with the procedures |linear_solve| and
|linear_solve_and_assign|, a procedure that searches an algebraic
expression for kernels of some specified operator with respect to
which the algebraic expression is linear, but with the coefficients of
these kernels not depending on some other operators.
Let us give an example in which such a procedure can be used
fruitfully. Suppose we have an expression |a(3)*a(2)-a(1)| from which
we want to solve one the |a(i)|'s automatically. Taking the first
operator element at sight, we would get |a(3):=a(1)/a(2)|. This,
however, is undesirable, because |a(2)| may be equated to 0 during the
process, in which case we are in trouble. Therefore the solution
should be |a(1):=a(3)*a(2)|.
But how can we discover that we must solve for |a(1)|? The answer to
this question is to use the procedure |solvable_kernels|, which
we will specify in a moment: the call
|solvable_kernels(a(3)*a(2)-a(1),a,a)| searches the expression
|a(3)*a(2)-a(1)| for kernels of operator |a| (second argument), but
only those which don't have coefficients containing kernels of
operator |a| (third argument). Hence this call returns the list
|{a(1)}| which is exactly the list of all kernels for which we may
solve without risc.
@ \spec |@!solvable_kernels|.
\descr Syntax: |solvable_kernels(exprn,k_oplist,c_oplist)|.
\descr Arguments:
\arg |exprn|: algebraic expression.
\arg |k_oplist|: identifier or (algebraic or lisp) list of identifiers,
which should be algebraic operator(s).
\arg |c_oplist|: identifier or (algebraic or lisp) list of identifiers,
which should be algebraic operator(s).
\descr Result: returns an algebraic list of all kernels
|opkern| for wich all the following conditions are
satisfied:\nl
\descno 1. |exprn| contains the kernel |opkern| for
some operator on |k_oplist|\nl
\descno 2. |exprn| is linear w.r.t.\ |opkern|\nl
\descno 3. the coefficient of |opkern| in |exprn| is
not a polynomial expression in any kernel of
operator(s) on |c_oplist|.\nl
Before the analysis, |exprn| is simplified.
\descr Examples: the call
|solvable_kernels(a(1)*(b(1)+c(1))+a(2)*b(2),a,c)|
returns the list |{a(2)}|.
@ For |solvable_kernels| we will use the same construction as
for |operator_coeff| to make it an lisp operator.
@u
put('solvable_kernels,'psopfn,'solvable_kernels_1)$
@#
lisp procedure solvable_kernels_1 u;
if length u neq 3 then
rederr("SOLVABLE_KERNELS: wrong number of arguments")
else solvable_kernels(car u,cadr u,caddr u)$
@ As for |operator_coeff| all the essential actions are taken while
scanning the numerator $E$ of |exprn|, which is a standard form.
Seeing $E$ as a sum $E=\sum T_i$ where $T_i=P_i\cdot C_i$, the product
of a leading power and a leading coefficient, again, we can
distinguish the following states for each term $T_i$: \medskip
\item{1.} $T_i$ is domain element, hence in particular not a kernel of
one of the operators on |k_oplist| or |c_oplist|. We have to take no action.
\item{2.} The main variable of $P_i$ is a kernel of one of the
operators on |k_oplist|. If the leading degree is one and $C_i$ does
not contain kernels of operators on |c_oplist|, this kernel is a
possible candidate for solving, otherwise it has to be marked as
unsolvable.
\item{3.} The main variable of $P_i$ is a kernel of one of the
operators on |c_oplist|. We can now recursively examine the standard
form $C_i$ and mark all kernels of operators on |k_oplist| found there
as unsolvable.
\item{4.} In all other cases we can recursively examine the standard
form $C_i$, ignoring the factor $P_i$.
\noindent Note that also in case 2.\ we have to check the form $C_i$,
keeping in mind the conditions of case 3.: the main variable of $P_i$
can be forbidden as well as allowed as a coefficient.
@ Implementing the actions described above requires a function for
merging an new element into a list. It is rather straightforward.
@u
lisp procedure list_merge(element,merge_list);
if member(element,merge_list) then merge_list else element .
merge_list$
@ The actions described above are implemented in the procedure
|mk_kernel_list|. The procedure examines the leading term and
recursively the reductum of the standard form.
The fifth argument of the procedure, |kernel_list|, is a dotted pair,
the |car| of which is the list of all possible candidates for solving,
the |cdr| the list of unsolvable kernels and is returned at the end.
It is clear that, at top level, it has to be initialized to |nil . nil|.
The fourth argument |forbidden| is a flag indicating if, at some
higher level, a kernel of an operator on |c_oplist| has been
encountered, hence that all kernels op operators on |k_oplist| found
have to be marked as unsolvable. At top level is has to be initialized
to |nil|.
@u lisp procedure mk_kernel_list(form,k_oplist,c_oplist,forbidden,kernel_list);
if domainp form then kernel_list
else (
if not atom kernel then
mk_kernel_list(red form,k_oplist,c_oplist,forbidden,@|
mk_kernel_list(lc form,k_oplist,c_oplist,
if member(car kernel,c_oplist) then t @+else forbidden,
if member(car kernel,k_oplist) then
if not forbidden and ldeg form=1 and
not get_first_kernel(lc form,c_oplist) then@|
list_merge(kernel,car kernel_list) . cdr kernel_list
else
car kernel_list . list_merge(kernel,cdr kernel_list)
else kernel_list))
else mk_kernel_list(red form,k_oplist,c_oplist,forbidden,@|
mk_kernel_list(lc form,k_oplist,c_oplist,forbidden,kernel_list))
) where kernel=mvar form$
@ The procedure |solvable_kernels| is a piece of cake now:
simplify |exprn|, get its numerator, apply |mk_kernel_list| to it and
finally delete all unsolvable kernels from the list of possible
candidates for solving. The list obtained in this way is the list of
all solvable kernels in |exprn|.
Again we use |simp!*| to simplify |exprn|, because |exprn| hasn't been
simplified before and we want a full simplification including a call
of |subs2|.
@u
lisp procedure solvable_kernels(exprn,k_oplist,c_oplist);
begin scalar form,kernel_list,forbidden_kernels;
form:=numr simp!* exprn;
k_oplist:=make_oplist(k_oplist);
c_oplist:=make_oplist(c_oplist);
kernel_list:=mk_kernel_list(form,k_oplist,c_oplist,nil,nil . nil);
forbidden_kernels:=cdr kernel_list;
kernel_list:=car kernel_list;
for each kernel in forbidden_kernels do kernel_list:=delete(kernel,kernel_list);
return 'list . kernel_list;
end$
@ The end of a REDUCE input file must be marked with |end|.
@u end;
@* Index. This section contains the cross reference index of all
identifiers, together with the numbers of the modules in which they
are used. Underlined entries correspond to module numbers where the
identifier was declared.