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