001/*
002 * $Id$
003 */
004
005package edu.jas.gb;
006
007
008import java.io.Serializable;
009import java.util.List;
010
011import edu.jas.poly.GenSolvablePolynomial;
012import edu.jas.structure.RingElem;
013
014
015/**
016 * Solvable polynomial Reduction interface. Defines S-Polynomial, normalform and
017 * irreducible set.
018 * @param <C> coefficient type
019 * @author Heinz Kredel
020 */
021
022public interface SolvableReduction<C extends RingElem<C>> extends Serializable {
023
024
025    /**
026     * Left S-Polynomial.
027     * @param Ap solvable polynomial.
028     * @param Bp solvable polynomial.
029     * @return left-spol(Ap,Bp) the left S-polynomial of Ap and Bp.
030     */
031    public GenSolvablePolynomial<C> leftSPolynomial(GenSolvablePolynomial<C> Ap, GenSolvablePolynomial<C> Bp);
032
033
034    /**
035     * S-Polynomial with recording.
036     * @param S recording matrix, is modified.
037     * @param i index of Ap in basis list.
038     * @param Ap a polynomial.
039     * @param j index of Bp in basis list.
040     * @param Bp a polynomial.
041     * @return leftSpol(Ap, Bp), the left S-Polynomial for Ap and Bp.
042     */
043    public GenSolvablePolynomial<C> leftSPolynomial(List<GenSolvablePolynomial<C>> S, int i,
044                    GenSolvablePolynomial<C> Ap, int j, GenSolvablePolynomial<C> Bp);
045
046
047    /**
048     * Left Normalform.
049     * @param Ap solvable polynomial.
050     * @param Pp solvable polynomial list.
051     * @return left-nf(Ap) with respect to Pp.
052     */
053    public GenSolvablePolynomial<C> leftNormalform(List<GenSolvablePolynomial<C>> Pp,
054                    GenSolvablePolynomial<C> Ap);
055
056
057    /**
058     * LeftNormalform with recording.
059     * @param row recording matrix, is modified.
060     * @param Pp a polynomial list for reduction.
061     * @param Ap a polynomial.
062     * @return nf(Pp,Ap), the left normal form of Ap wrt. Pp.
063     */
064    public GenSolvablePolynomial<C> leftNormalform(List<GenSolvablePolynomial<C>> row,
065                    List<GenSolvablePolynomial<C>> Pp, GenSolvablePolynomial<C> Ap);
066
067
068    /**
069     * Left Normalform Set.
070     * @param Ap solvable polynomial list.
071     * @param Pp solvable polynomial list.
072     * @return list of left-nf(a) with respect to Pp for all a in Ap.
073     */
074    public List<GenSolvablePolynomial<C>> leftNormalform(List<GenSolvablePolynomial<C>> Pp,
075                    List<GenSolvablePolynomial<C>> Ap);
076
077
078    /**
079     * Left irreducible set.
080     * @param Pp solvable polynomial list.
081     * @return a list P of solvable polynomials which are in normalform wrt. P.
082     */
083    public List<GenSolvablePolynomial<C>> leftIrreducibleSet(List<GenSolvablePolynomial<C>> Pp);
084
085
086    /**
087     * Is reduction of normal form.
088     * @param row recording matrix, is modified.
089     * @param Pp a solvable polynomial list for reduction.
090     * @param Ap a solvable polynomial.
091     * @param Np nf(Pp,Ap), a left normal form of Ap wrt. Pp.
092     * @return true, if Np + sum( row[i]*Pp[i] ) == Ap, else false.
093     */
094    public boolean isLeftReductionNF(List<GenSolvablePolynomial<C>> row, List<GenSolvablePolynomial<C>> Pp,
095                    GenSolvablePolynomial<C> Ap, GenSolvablePolynomial<C> Np);
096
097
098    /**
099     * Right S-Polynomial.
100     * @param Ap solvable polynomial.
101     * @param Bp solvable polynomial.
102     * @return right-spol(Ap,Bp) the right S-polynomial of Ap and Bp.
103     */
104    public GenSolvablePolynomial<C> rightSPolynomial(GenSolvablePolynomial<C> Ap,
105                    GenSolvablePolynomial<C> Bp);
106
107
108    /**
109     * Right Normalform.
110     * @param Ap solvable polynomial.
111     * @param Pp solvable polynomial list.
112     * @return right-nf(Ap) with respect to Pp.
113     */
114    public GenSolvablePolynomial<C> rightNormalform(List<GenSolvablePolynomial<C>> Pp,
115                    GenSolvablePolynomial<C> Ap);
116
117
118    /**
119     * RightNormalform with recording.
120     * @param row recording matrix, is modified.
121     * @param Pp a polynomial list for reduction.
122     * @param Ap a polynomial.
123     * @return nf(Pp,Ap), the right normal form of Ap wrt. Pp.
124     */
125    public GenSolvablePolynomial<C> rightNormalform(List<GenSolvablePolynomial<C>> row,
126                    List<GenSolvablePolynomial<C>> Pp, GenSolvablePolynomial<C> Ap);
127
128
129    /**
130     * Is top reducible. Condition is lt(B) | lt(A) for some B in F. Is left
131     * right symmetric.
132     * @param A polynomial.
133     * @param P polynomial list.
134     * @return true if A is top reducible with respect to P.
135     */
136    public boolean isTopReducible(List<GenSolvablePolynomial<C>> P, GenSolvablePolynomial<C> A);
137
138
139    /**
140     * Is reducible. Is left right symmetric.
141     * @param A polynomial.
142     * @param P polynomial list.
143     * @return true if A is reducible with respect to P.
144     */
145    public boolean isReducible(List<GenSolvablePolynomial<C>> P, GenSolvablePolynomial<C> A);
146
147
148    /**
149     * Is in normalform. Is left right symmetric.
150     * @param A polynomial.
151     * @param P polynomial list.
152     * @return true if A is in normalform with respect to P.
153     */
154    public boolean isNormalform(List<GenSolvablePolynomial<C>> P, GenSolvablePolynomial<C> A);
155
156
157    /**
158     * Is right reduction of normal form.
159     * @param row recording matrix, is modified.
160     * @param Pp a solvable polynomial list for reduction.
161     * @param Ap a solvable polynomial.
162     * @param Np nf(Pp,Ap), a right normal form of Ap wrt. Pp.
163     * @return true, if Np + sum( Pp[i]*row[i] ) == Ap, else false.
164     */
165    public boolean isRightReductionNF(List<GenSolvablePolynomial<C>> row, List<GenSolvablePolynomial<C>> Pp,
166                    GenSolvablePolynomial<C> Ap, GenSolvablePolynomial<C> Np);
167
168
169    /**
170     * Two-sided Normalform.
171     * @param Ap solvable polynomial.
172     * @param Pp solvable polynomial list.
173     * @return two-sided-nf(Ap) with respect to Pp.
174     */
175    public GenSolvablePolynomial<C> normalform(List<GenSolvablePolynomial<C>> Pp,
176                    GenSolvablePolynomial<C> Ap);
177
178}