001/* 002 * $Id: ReductionSeq.java 4281 2012-11-03 10:40:06Z 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.GenPolynomial; 014 015import 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 025public 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().copy(); 087 088 //GenPolynomial<C> T = null; 089 GenPolynomial<C> Q = null; 090 GenPolynomial<C> S = Ap.copy(); 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 //R = R.sum( a, e ); 102 //S = S.subtract( a, e ); 103 R.doPutToMap(e,a); 104 S.doRemoveFromMap(e,a); 105 // System.out.println(" S = " + S); 106 } else { 107 e = e.subtract( htl[i] ); 108 //logger.info("red div = " + e); 109 a = a.divide( (C)lbc[i] ); 110 //Q = p[i].multiply( a, e ); 111 //S = S.subtract( Q ); 112 S = S.subtractMultiple(a,e,p[i]); 113 } 114 } 115 return R; 116 } 117 118 119 /** 120 * Normalform 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 normal form of Ap wrt. Pp. 125 */ 126 @SuppressWarnings("unchecked") 127 public GenPolynomial<C> 128 normalform(List<GenPolynomial<C>> row, 129 List<GenPolynomial<C>> Pp, 130 GenPolynomial<C> Ap) { 131 if ( Pp == null || Pp.isEmpty() ) { 132 return Ap; 133 } 134 if ( Ap == null || Ap.isZERO() ) { 135 return Ap; 136 } 137 if ( ! Ap.ring.coFac.isField() ) { 138 throw new IllegalArgumentException("coefficients not from a field"); 139 } 140 int l = Pp.size(); 141 GenPolynomial<C>[] P = new GenPolynomial[l]; 142 synchronized (Pp) { 143 //P = Pp.toArray(); 144 for ( int i = 0; i < Pp.size(); i++ ) { 145 P[i] = Pp.get(i); 146 } 147 } 148 ExpVector[] htl = new ExpVector[ l ]; 149 Object[] lbc = new Object[ l ]; // want C[] 150 GenPolynomial<C>[] p = new GenPolynomial[ l ]; 151 Map.Entry<ExpVector,C> m; 152 int j = 0; 153 int i; 154 for ( i = 0; i < l; i++ ) { 155 p[i] = P[i]; 156 m = p[i].leadingMonomial(); 157 if ( m != null ) { 158 p[j] = p[i]; 159 htl[j] = m.getKey(); 160 lbc[j] = m.getValue(); 161 j++; 162 } 163 } 164 l = j; 165 ExpVector e; 166 C a; 167 boolean mt = false; 168 GenPolynomial<C> zero = Ap.ring.getZERO(); 169 GenPolynomial<C> R = Ap.ring.getZERO().copy(); 170 171 GenPolynomial<C> fac = null; 172 // GenPolynomial<C> T = null; 173 GenPolynomial<C> Q = null; 174 GenPolynomial<C> S = Ap.copy(); 175 while ( S.length() > 0 ) { 176 m = S.leadingMonomial(); 177 e = m.getKey(); 178 a = m.getValue(); 179 for ( i = 0; i < l; i++ ) { 180 mt = e.multipleOf( htl[i] ); 181 if ( mt ) break; 182 } 183 if ( ! mt ) { 184 //logger.debug("irred"); 185 //R = R.sum( a, e ); 186 //S = S.subtract( a, e ); 187 R.doPutToMap(e,a); 188 S.doRemoveFromMap(e,a); 189 // System.out.println(" S = " + S); 190 //throw new RuntimeException("Syzygy no GB"); 191 } else { 192 e = e.subtract( htl[i] ); 193 //logger.info("red div = " + e); 194 C c = (C) lbc[i]; 195 a = a.divide( c ); 196 //Q = p[i].multiply( a, e ); 197 //S = S.subtract( Q ); 198 S = S.subtractMultiple(a,e,p[i]); 199 fac = row.get(i); 200 if ( fac == null ) { 201 fac = zero.sum( a, e ); 202 } else { 203 fac = fac.sum( a, e ); 204 } 205 row.set(i,fac); 206 } 207 } 208 return R; 209 } 210 211}