001 /*
002 * $Id: ReductionPar.java 2921 2009-12-25 17:06:56Z kredel $
003 */
004
005 package edu.jas.gb;
006
007 import java.util.Collection;
008 import java.util.List;
009 import java.util.Map;
010
011 //import org.apache.log4j.Logger;
012
013 import edu.jas.poly.ExpVector;
014 import edu.jas.poly.GenPolynomial;
015 import edu.jas.structure.RingElem;
016 import edu.jas.util.DistHashTable;
017
018
019 /**
020 * Polynomial Reduction parallel usable algorithm.
021 * Implements normalform.
022 * @param <C> coefficient type
023 * @author Heinz Kredel
024 */
025
026 public class ReductionPar<C extends RingElem<C>>
027 extends ReductionAbstract<C> {
028
029 //private static final Logger logger = Logger.getLogger(ReductionPar.class);
030
031
032 /**
033 * Constructor.
034 */
035 public ReductionPar() {
036 }
037
038
039 /**
040 * Normalform. Allows concurrent modification of the list.
041 * @param Ap polynomial.
042 * @param Pp polynomial list, concurrent modification allowed.
043 * @return nf(Ap) with respect to Pp.
044 */
045 public GenPolynomial<C>
046 normalform(List<GenPolynomial<C>> Pp,
047 GenPolynomial<C> Ap) {
048 if ( Pp == null || Pp.isEmpty() ) {
049 return Ap;
050 }
051 if ( Ap == null || Ap.isZERO() ) {
052 return Ap;
053 }
054 int l;
055 GenPolynomial<C>[] P;
056 synchronized (Pp) { // required, ok in dist
057 l = Pp.size();
058 P = (GenPolynomial<C>[]) new GenPolynomial[l];
059 //P = Pp.values().toArray();
060 for ( int i = 0; i < Pp.size(); i++ ) {
061 P[i] = Pp.get(i);
062 }
063 }
064
065 Map.Entry<ExpVector,C> m;
066 Map.Entry<ExpVector,C> m1;
067 ExpVector e;
068 ExpVector f = null;
069 C a;
070 boolean mt = false;
071 GenPolynomial<C> Rz = Ap.ring.getZERO();
072 GenPolynomial<C> R = Rz;
073 GenPolynomial<C> p = null;
074 GenPolynomial<C> Q = null;
075 GenPolynomial<C> S = Ap;
076 while ( S.length() > 0 ) {
077 if ( Pp.size() != l ) {
078 //long t = System.currentTimeMillis();
079 synchronized (Pp) { // required, bad in parallel
080 l = Pp.size();
081 P = (GenPolynomial<C>[]) new GenPolynomial[ l ];
082 //P = Pp.toArray();
083 for ( int i = 0; i < Pp.size(); i++ ) {
084 P[i] = Pp.get(i);
085 }
086 }
087 //t = System.currentTimeMillis()-t;
088 //logger.info("Pp.toArray() = " + t + " ms, size() = " + l);
089 S = Ap; // S.add(R)? // restart reduction ?
090 R = Rz;
091 }
092 m = S.leadingMonomial();
093 e = m.getKey();
094 a = m.getValue();
095 for ( int i = 0; i < P.length ; i++ ) {
096 p = P[i];
097 f = p.leadingExpVector();
098 if ( f != null ) {
099 mt = e.multipleOf( f );
100 if ( mt ) break;
101 }
102 }
103 if ( ! mt ) {
104 //logger.debug("irred");
105 //T = new OrderedMapPolynomial( a, e );
106 R = R.sum( a, e );
107 S = S.subtract( a, e );
108 // System.out.println(" S = " + S);
109 } else {
110 //logger.debug("red");
111 m1 = p.leadingMonomial();
112 e = e.subtract( f );
113 a = a.divide( m1.getValue() );
114 Q = p.multiply( a, e );
115 S = S.subtract( Q );
116 }
117 }
118 return R;
119 }
120
121
122 /**
123 * Normalform with recording.
124 * @param row recording matrix, is modified.
125 * @param Pp a polynomial list for reduction.
126 * @param Ap a polynomial.
127 * @return nf(Pp,Ap), the normal form of Ap wrt. Pp.
128 */
129 public GenPolynomial<C>
130 normalform(List<GenPolynomial<C>> row,
131 List<GenPolynomial<C>> Pp,
132 GenPolynomial<C> Ap) {
133 throw new RuntimeException("normalform with recording not implemented");
134 }
135
136
137 /**
138 * Normalform. Allows concurrent modification of the DHT.
139 * @param Ap polynomial.
140 * @param Pp distributed hash table, concurrent modification allowed.
141 * @return nf(Ap) with respect to Pp.
142 */
143 public GenPolynomial<C>
144 normalform(DistHashTable Pp,
145 GenPolynomial<C> Ap) {
146 if ( Pp == null || Pp.isEmpty() ) {
147 return Ap;
148 }
149 if ( Ap == null || Ap.isZERO() ) {
150 return Ap;
151 }
152 int l;
153 GenPolynomial<C>[] P;
154 synchronized ( Pp.getList() ) { // required, ok in dist
155 l = Pp.size();
156 P = (GenPolynomial<C>[]) new GenPolynomial[l];
157 //P = Pp.values().toArray();
158 Collection<GenPolynomial<C>> Pv
159 = (Collection<GenPolynomial<C>>)Pp.values();
160 int i = 0;
161 for ( GenPolynomial<C> x : Pv ) {
162 P[i++] = x;
163 }
164 }
165
166 Map.Entry<ExpVector,C> m;
167 Map.Entry<ExpVector,C> m1;
168 ExpVector e;
169 ExpVector f = null;
170 C a;
171 boolean mt = false;
172 GenPolynomial<C> Rz = Ap.ring.getZERO();
173 GenPolynomial<C> R = Rz;
174 GenPolynomial<C> p = null;
175 GenPolynomial<C> Q = null;
176 GenPolynomial<C> S = Ap;
177 while ( S.length() > 0 ) {
178 if ( Pp.size() != l ) {
179 //long t = System.currentTimeMillis();
180 synchronized ( Pp.getList() ) { // required, ok in distributed
181 l = Pp.size();
182 P = (GenPolynomial<C>[]) new GenPolynomial[ l ];
183 //P = Pp.values().toArray();
184 Collection<GenPolynomial<C>> Pv
185 = (Collection<GenPolynomial<C>>)Pp.values();
186 int i = 0;
187 for ( GenPolynomial<C> x : Pv ) {
188 P[i++] = x;
189 }
190 }
191 //t = System.currentTimeMillis()-t;
192 //logger.info("Pp.toArray() = " + t + " ms, size() = " + l);
193 //logger.info("Pp.toArray() size() = " + l);
194 S = Ap; // S.add(R)? // restart reduction ?
195 R = Rz;
196 }
197
198 m = S.leadingMonomial();
199 e = m.getKey();
200 a = m.getValue();
201 for ( int i = 0; i < P.length ; i++ ) {
202 p = P[i];
203 f = p.leadingExpVector();
204 if ( f != null ) {
205 mt = e.multipleOf( f );
206 if ( mt ) break;
207 }
208 }
209 if ( ! mt ) {
210 //logger.debug("irred");
211 //T = new OrderedMapPolynomial( a, e );
212 R = R.sum( a, e );
213 S = S.subtract( a, e );
214 // System.out.println(" S = " + S);
215 } else {
216 //logger.debug("red");
217 m1 = p.leadingMonomial();
218 e = e.subtract( f );
219 a = a.divide( m1.getValue() );
220 Q = p.multiply( a, e );
221 S = S.subtract( Q );
222 }
223 }
224 return R;
225 }
226
227 }