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