001 /*
002 * $Id: ReductionSeq.java 3288 2010-08-25 21:46:14Z kredel $
003 */
004
005 package edu.jas.gb;
006
007 import java.util.List;
008 import java.util.Map;
009
010 //import org.apache.log4j.Logger;
011
012 import edu.jas.poly.ExpVector;
013 import edu.jas.poly.GenPolynomial;
014
015 import edu.jas.structure.RingElem;
016
017
018 /**
019 * Polynomial Reduction sequential use algorithm.
020 * Implements normalform.
021 * @param <C> coefficient type
022 * @author Heinz Kredel
023 */
024
025 public class ReductionSeq<C extends RingElem<C>> // should be FieldElem<C>>
026 extends ReductionAbstract<C> {
027
028 //private static final Logger logger = Logger.getLogger(ReductionSeq.class);
029
030
031 /**
032 * Constructor.
033 */
034 public ReductionSeq() {
035 }
036
037
038 /**
039 * Normalform.
040 * @param Ap polynomial.
041 * @param Pp polynomial list.
042 * @return nf(Ap) with respect to Pp.
043 */
044 @SuppressWarnings("unchecked")
045 public GenPolynomial<C> normalform(List<GenPolynomial<C>> Pp,
046 GenPolynomial<C> Ap) {
047 if ( Pp == null || Pp.isEmpty() ) {
048 return Ap;
049 }
050 if ( Ap == null || Ap.isZERO() ) {
051 return Ap;
052 }
053 if ( ! Ap.ring.coFac.isField() ) {
054 throw new IllegalArgumentException("coefficients not from a field");
055 }
056 Map.Entry<ExpVector,C> m;
057 int l;
058 GenPolynomial<C>[] P;
059 synchronized (Pp) {
060 l = Pp.size();
061 P = new GenPolynomial[l];
062 //P = Pp.toArray();
063 for ( int i = 0; i < Pp.size(); i++ ) {
064 P[i] = Pp.get(i);
065 }
066 }
067 ExpVector[] htl = new ExpVector[ l ];
068 Object[] lbc = new Object[ l ]; // want C[]
069 GenPolynomial<C>[] p = new GenPolynomial[ l ];
070 int i;
071 int j = 0;
072 for ( i = 0; i < l; i++ ) {
073 p[i] = P[i];
074 m = p[i].leadingMonomial();
075 if ( m != null ) {
076 p[j] = p[i];
077 htl[j] = m.getKey();
078 lbc[j] = m.getValue();
079 j++;
080 }
081 }
082 l = j;
083 ExpVector e;
084 C a;
085 boolean mt = false;
086 GenPolynomial<C> R = Ap.ring.getZERO();
087
088 //GenPolynomial<C> T = null;
089 GenPolynomial<C> Q = null;
090 GenPolynomial<C> S = Ap;
091 while ( S.length() > 0 ) {
092 m = S.leadingMonomial();
093 e = m.getKey();
094 a = m.getValue();
095 for ( i = 0; i < l; i++ ) {
096 mt = e.multipleOf( htl[i] );
097 if ( mt ) break;
098 }
099 if ( ! mt ) {
100 //logger.debug("irred");
101 //T = new OrderedMapPolynomial( a, e );
102 R = R.sum( a, e );
103 S = S.subtract( a, e );
104 // System.out.println(" S = " + S);
105 } else {
106 e = e.subtract( htl[i] );
107 //logger.info("red div = " + e);
108 a = a.divide( (C)lbc[i] );
109 Q = p[i].multiply( a, e );
110 S = S.subtract( Q );
111 }
112 }
113 return R;
114 }
115
116
117 /**
118 * Normalform with recording.
119 * @param row recording matrix, is modified.
120 * @param Pp a polynomial list for reduction.
121 * @param Ap a polynomial.
122 * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
123 */
124 @SuppressWarnings("unchecked")
125 public GenPolynomial<C>
126 normalform(List<GenPolynomial<C>> row,
127 List<GenPolynomial<C>> Pp,
128 GenPolynomial<C> Ap) {
129 if ( Pp == null || Pp.isEmpty() ) {
130 return Ap;
131 }
132 if ( Ap == null || Ap.isZERO() ) {
133 return Ap;
134 }
135 if ( ! Ap.ring.coFac.isField() ) {
136 throw new IllegalArgumentException("coefficients not from a field");
137 }
138 int l = Pp.size();
139 GenPolynomial<C>[] P = new GenPolynomial[l];
140 synchronized (Pp) {
141 //P = Pp.toArray();
142 for ( int i = 0; i < Pp.size(); i++ ) {
143 P[i] = Pp.get(i);
144 }
145 }
146 ExpVector[] htl = new ExpVector[ l ];
147 Object[] lbc = new Object[ l ]; // want C[]
148 GenPolynomial<C>[] p = new GenPolynomial[ l ];
149 Map.Entry<ExpVector,C> m;
150 int j = 0;
151 int i;
152 for ( i = 0; i < l; i++ ) {
153 p[i] = P[i];
154 m = p[i].leadingMonomial();
155 if ( m != null ) {
156 p[j] = p[i];
157 htl[j] = m.getKey();
158 lbc[j] = m.getValue();
159 j++;
160 }
161 }
162 l = j;
163 ExpVector e;
164 C a;
165 boolean mt = false;
166 GenPolynomial<C> zero = Ap.ring.getZERO();
167 GenPolynomial<C> R = Ap.ring.getZERO();
168
169 GenPolynomial<C> fac = null;
170 // GenPolynomial<C> T = null;
171 GenPolynomial<C> Q = null;
172 GenPolynomial<C> S = Ap;
173 while ( S.length() > 0 ) {
174 m = S.leadingMonomial();
175 e = m.getKey();
176 a = m.getValue();
177 for ( i = 0; i < l; i++ ) {
178 mt = e.multipleOf( htl[i] );
179 if ( mt ) break;
180 }
181 if ( ! mt ) {
182 //logger.debug("irred");
183 R = R.sum( a, e );
184 S = S.subtract( a, e );
185 // System.out.println(" S = " + S);
186 //throw new RuntimeException("Syzygy no GB");
187 } else {
188 e = e.subtract( htl[i] );
189 //logger.info("red div = " + e);
190 C c = (C) lbc[i];
191 a = a.divide( c );
192 Q = p[i].multiply( a, e );
193 S = S.subtract( Q );
194 fac = row.get(i);
195 if ( fac == null ) {
196 fac = zero.sum( a, e );
197 } else {
198 fac = fac.sum( a, e );
199 }
200 row.set(i,fac);
201 }
202 }
203 return R;
204 }
205
206 }