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