```(* ----------------------------------------------------------------------------
* \$Id: DIPIB.md,v 1.2 1995/12/16 12:21:53 kredel Exp \$
* ----------------------------------------------------------------------------
* This file is part of MAS.
* ----------------------------------------------------------------------------
* Copyright (c) 1995 Universitaet Passau
* ----------------------------------------------------------------------------
* \$Log: DIPIB.md,v \$
* Revision 1.2  1995/12/16 12:21:53  kredel
* Comments slightly changed.
*
* Revision 1.1  1995/10/12  14:44:52  pesch
* Diplomarbeit Rainer Grosse-Gehling.
* Involutive Bases.
* Slightly edited.
*
* ----------------------------------------------------------------------------
*)

DEFINITION MODULE DIPIB;

(* DIP Common Polynomial System Definition Module in the sense of Janet. *)

(* Import lists and declarations. *)

FROM MASSTOR IMPORT LIST;

TYPE PROCP5V2 = PROCEDURE(LIST, LIST, LIST, LIST, LIST, VAR LIST, VAR LIST);

CONST rcsid = "\$Id: DIPIB.md,v 1.2 1995/12/16 12:21:53 kredel Exp \$";
CONST copyright = "Copyright (c) 1995 Universitaet Passau";

PROCEDURE ADCAN(P: LIST): LIST;
(* Arbitrary Polynomial Cancel.
P is an polynomial of arbritrary domain,
P is canceld down with ADPCP iff the domain of P is INT and with
DIPMOC else *)

(*****************************************************************************
* The following two algorithms are from: Zharkov, Blinkov                   *
*        Involutive Bases of Zero-Dimensional Ideals and                    *
*        Involution approach to Solving Systems of Algebraic Equations      *
*****************************************************************************)

PROCEDURE ADPNFJ(G,P: LIST; VAR h: LIST; VAR reduced: BOOLEAN);
(* Arbitrary domain polynomial normalform in the sense of Janet.
G is a list of polynomials in distributive representation over an arbitrary
domain, P is a polynomial as above,
returns a polynomial h such that P is Janet-reducible to h modulo G
and h is in Janet-normalform w.r.t. G, the flag "reduced" is set TRUE iff
a Janet-reduction took place *)

PROCEDURE DIPNFJ(P,S: LIST; VAR h: LIST; VAR reduced: BOOLEAN);
(* Distributive polynomial normal form in the sense of Janet.
P is a list of non zero polynomials in distributive
representation in r variables. S is a distributive polynomial.
The result is a polynomial h such that S is reducible to h modulo P
in the sense of Janet and h is in Janet-normalform with respect to P,
"reduced" is set TRUE iff a Janet-reduction took place. *)

PROCEDURE DIPINFJ(P,S: LIST; VAR h: LIST; VAR reduced: BOOLEAN);
(* Integral Distributive polynomial normal form in the sense of Janet.
P is a list of non zero polynomials in distributive
representation in r variables. S is a distributive
polynomial. h is a polynomial such that S is reducible to h
modulo P in the sense of Janet and h is in normalform with respect to P,
reduced is set TRUE iff a Janet-reduction took place. *)

PROCEDURE DILISJ(P: LIST; VAR PP: LIST; VAR reduced: BOOLEAN);
(* Distributive polynomial list irreducible set in the sense of Janet.
P is a list of distributive polynomials,
PP is the result of reducing each polynomial p in P modulo P-(p)
in the sense of Janet until no further reductions are possible.
reduced is set TRUE if a Janet-reduction took place. *)

PROCEDURE DIPIRLJ(P: LIST; VAR F: LIST; VAR reduced: BOOLEAN);
(* distributive polynomial interreduced list in the sense of Janet.
P is a list of polynomials in distributive representation over an
arbitrary domain,
The result is a Janet-interreduced list of polynoms F,
reduced is set TRUE iff a reduction took place. *)

(*** Algorithms from: Zharkov, Blinkov;
Involutive Bases of zero-dimensional ideals ***)

PROCEDURE DIPCOM(F: LIST): LIST;
(* Distributive polynomial complete.
Subalgorithm for computing Invbase.
Input: Distributive polynomial list F.
Output: G: complete system, such that Ideal(G) = Ideal(F). *)

PROCEDURE DIPIB2(F: LIST): LIST;
(* Distributive polynomial involutive basis.
Mainalgorithm for computing Invbase.
Input: Distributive polynomial list F.
Output: G: involutive system, such that Ideal(G) = Ideal(F). *)

(*** Algorithm from: Zharkov, Blinkov:
Involution Approach to Solving Systems of Algebraic Equations ***)

PROCEDURE DIPIB3(F: LIST): LIST;
(* Distributive polynom involutive base.
Algorithm for computing the involutive Base for a given polynomial list F.
Input: Distributiv Polynomial List F.
Output: Equivalent involutive system G.*)

(******************************************************************************
*    Algorithm analog to: Zharkov, Blinkov:                                  *
*                              Solving zero-dimensional involutive systems,  *
*    an optional using of three criteria is possible. The three criteria are *
*    from Gerdt, Blinkov: Involutive Polynomial Bases.                       *
*----------------------------------------------------------------------------*
* This algorithm works with extended polynomial lists. An extended polynomial*
* is a triple (deg, pol, ht) with:                                           *
*    deg - total degree of the leading term or 0 if the polynomial is already*
*          prolongated.                                                      *
*    pol - the polynomial                                                    *
*    ht  - head term of the starting polynomial. ht must not be equal to the *
*          head term of pol. ht is updated in the procedure IBcrit.          *
*          For details see Gerdt, Blinkov: Involutive Polynomial Bases.      *
******************************************************************************)

PROCEDURE ADEPNFJ(G,P: LIST; VAR h: LIST; VAR reduced: BOOLEAN);
(* Arbitrary domain extended polynomial normalform in the sense of Janet.
G is a list of polynomials in distributive representation over an arbitrary
domain, P is a polynomial as above,
returns a polynomial h such that P is Janet-reducible to h modulo G
and h is in Janet-normalform w.r.t. G, the flag "reduced" is set True iff
a Janet-reduction took place  *)

PROCEDURE DIPENFJ(P,S: LIST; VAR R: LIST; VAR c: BOOLEAN);
(* Distributive extended polynomial normal form in the sense of Janet.
P is a list of non zero extended polynomials in distributive
representation in r variables. S is a distributive extended
polynomial. R is an extended polynomial such that S is reducible
to R modulo P in the sense of Janet and R is in normalform with
respect to P, c is set TRUE iff a Janet-reduction took place. *)

PROCEDURE DIPEINFJ(P,S: LIST; VAR R: LIST; VAR c: BOOLEAN);
(* Integral distributive extended polynomial normal form in the sense of Janet.
P is a list of non zero extended polynomials in distributive
representation in r variables. S is a distributive extended
polynomial. R is a polynomial such that S is reducible to R
modulo P in the sense of Janet and R is in normalform with respect to P. *)

PROCEDURE IsInvolutive(G: LIST): BOOLEAN;
(* Is involutive.
Test wether G is involutive,
G is a list of distributive polynomials,
Returns TRUE iff G is involutive, FALSE else *)

PROCEDURE ADEPmark(g, G: LIST): LIST;
(* Arbitrary domain extended polynomial mark.
g is an extended polynomial, G is a list of extended polynomials;
the first entry of g is set to 0 and G is set to G cup g *)

PROCEDURE DILISJ2(P: LIST): LIST;
(* Distributive polynomial list irreducible set.
P is a list of distributive polynomials,
PP is the result of reducing each p element of P modulo P-(p)
in the sense of Janet until no further reductions are possible. *)

PROCEDURE ADEPtriple(PS, term: LIST): LIST;
(* Arbitrary domain extende polynomial triple.
Input: PS - a list of polynomials, term - term to use as head term or SIL.
Output: a list of extended polynomials *)

PROCEDURE ADEPuntriple(PS: LIST): LIST;
(* Arbitrary domain extended polynomial untriple.
Input: PS - an extended polynomial list.
Output: a polynomial list. *)

PROCEDURE ADEPCrumble(P: LIST; VAR deg, pol, ht: LIST);
(* Arbitrary domain extended polynomial crumble.
Input: an arbritraty domain extended polynomial,
Output: the components of the extended polynomial: deg - the total degree
of the leading term, pol - the polynomial and if exists ht - the
head term of the polynomial and 0 else. *)

PROCEDURE ADEPCompose(deg, pol, ht: LIST): LIST;
(* Arbitrary domain extended polynomial compose.
Input: the components to build an extended polynomial: deg - the total degree
of the polynomial, pol - the polynomial and ht - the head term of
the polynomial or 0 if ht should not be element of the extended
polynomial.
Output: an extended polynomial. *)

PROCEDURE ADEPdegree(P: LIST): LIST;
(* Arbitrary domain extended polynomial degree.
Input: P - an arbitrary domain extended polynomial.
Ouput: the degree of the head term of P, that is the first entry from the
extended polynomial *)

PROCEDURE ADEPpolynomial(P: LIST): LIST;
(* Arbitrary domain extended polynomial polynomial.
Input: P - an arbitrary domain extended polynomial.
Output: the polynomial entry of the extended polynomial, that is the second
entry from the extended polynomial. *)

(* Arbitrary domain extended plynomial head-term.
Input: P - an arbitrary domain extended polynomial.
Output: the head term entry of the extended polynomial. That is the third
entry in the extended polynomial list.
The third list entry must not be equal to the head-term of the polynomial
entry of the extended polynomial list. *)

(* Arbitrary polynomial leading term.
Input: P - an arbitrary domain extended polynomial.
Output: the head term of the polynomial in the extended polynomial list,
that is the first element of the second list entry. *)

PROCEDURE IBcrit(NM, G: LIST): LIST;
(* Inovlutive Base criterium.
Input: NM - a list of prolongated extended polynomials, G - a list of
extended polynomials.
Output: NM minus the polynomials from NM which are reducible to 0 by
one of the criteriums, or which are reducible to 0 modulo G. *)

PROCEDURE DIPIB(F: LIST): LIST;
(* Distributive polynomial involutive basis.
Algorithm for computing the involutive Base for a given F.
Input: Distributiv Polynomial List F.
Output: Equivalent involutive system G.*)

(*****************************************************************************
*     algorithm analog to: Zharkov, Blinkov,                                *
*                         Solving zero-dimensional involutive systems       *
*---------------------------------------------------------------------------*
* This algorithm does not work with extended polynomial list and thus it    *
* needs another Janet-interreducible algorithm.                             *
* This algorithm does a Janet-reduction with two different input sets:      *
*  the first set is a list of possible candidates for prolongations and     *
*  the second set is a list of already condered polynomials                 *
*****************************************************************************)

PROCEDURE ADPNFJS(G1,G2,G3,G4,P: LIST; VAR h: LIST; VAR reduced: BOOLEAN);
(* Arbitrary domain polynomial normalform in the sense of Janet modulo a set
of set of polynomials.
G1-G4 are lists of polynomials in distributive representation over an
arbitrary domain, P is a polynomial.
The result is a polynomial h such that P is Janet-reducible to
h modulo the union of G1-G4 and h is in Janet-Normalform w.r.t. G1-G4,
the flag "reduced" is set TRUE iff a Janet-reduction took place *)

PROCEDURE DIPNFJS(P1,P2,P3,P4,S: LIST; VAR h: LIST; VAR reduced: BOOLEAN);
(* Distributive polynomial normal form in the sense of Janet modulo a set of
sets of polynomials.
P1-P4 are lists of non zero polynomials in distributive
representation in r variables. S is a distributive
polynomial. R is a polynomial such that S is reducible to R modulo P
in the sense of Janet and R is in normalform with respect to P,
reduced is set TRUE iff a reduction took place. *)

PROCEDURE DIPINFJS;
(* Integral Distributive polynomial normal form in the sense of Janet modulo a
set of sets of polynomials.
P1-P4 are lists of non zero polynomials in distributive
representation in r variables. S is a distributive
polynomial. h is a polynomial such that S is reducible to h
modulo P in the sense of Janet and h is in normalform with respect to P,
reduced is set TRUE iff a Janet-reduction took place. *)

PROCEDURE DIPIRLJ2(VAR P, Q: LIST; VAR reduced: BOOLEAN);
(* Distributive polynomial list interreduced list in the sense of Janet.
P and Q are lists of polynomials in distributive representation over an
arbitrary domain,
P and Q already initialised by the calling procedure.
P contains polynomials which are possible candidates for prolongations,
Q are already considered.
Output is the list P of Janet-reduced polynomials from p plus Janet-reduced
polynomials from Q. Q contains polynomials from input Q which are not
Janet-reduced.
reduced is set TRUE iff a reduction took place *)

PROCEDURE DIPIB4(F: LIST): LIST;
(* Distributive polynomial involutive basis.
Algorithm for computing the involutive Base for a given F.
Input: Distributiv Integral Polynomial List F.
Output: Equivalent involutive system G.*)

(******************************************************************************)

PROCEDURE SetDIPIBopt(options: LIST);
(* Set distributive polynomial involutive base options.
Input: List of 4 options in the order Trace-Level, Cancel-Option,
Select-Option, ISJ-Algorithm.
For details see the corresponding procedures *)

PROCEDURE SetDIPIBTraceLevel(level: INTEGER);
(* Set Trace Level.
Input is the integer level. You get the following informatins:
0: no information,
1: computing time and number of polynomials of the computed involutive base,
2: informations about each Janet-reduction,
3: more detailed information of each Janet-reduction. *)

PROCEDURE SetDIPIBCancel(Canc: CARDINAL);
(* Set distributive polynomial involutive base cancel.
Set the function to use to cancel down the coefficients in case of
integer coefficients. Canc=1 means: use ADCAN, 2 means: use DIPMOC *)

PROCEDURE SetDIPIBSelect(SEL: INTEGER);
(* Set distributive polynomial involutive base select.
Set polynomial selection strategy:
1: DIPSSM, 2: DIPFIRST  *)

PROCEDURE SetDIPIBISJ(Sel: INTEGER);
(* Set distributive involutive base irreducible set in the sense of Janet.
Set Janet-Irreducible-Set Algorithm, 1: DILISJ, 2: DIPIRLJ *)

PROCEDURE SetDIPIBCrit(crit: INTEGER);
(* Set distributive polynomial involutive base critera.
Input: an integer crit.
DIPIBOpt.Crit ::= TRUE iff cirt = 1 and FALSE else *)

PROCEDURE SetDomainNFJ;
(* Initialize Jdomain *)

END DIPIB.

(* -EOF- *)
```