% 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.