001/* 002 * $Id: GroebnerBaseSeqQuotient.java 4290 2012-11-04 14:47:45Z kredel $ 003 */ 004 005package edu.jas.gbufd; 006 007 008import java.util.ArrayList; 009import java.util.List; 010 011import org.apache.log4j.Logger; 012 013import edu.jas.gb.GroebnerBaseAbstract; 014import edu.jas.poly.GenPolynomial; 015import edu.jas.poly.GenPolynomialRing; 016import edu.jas.poly.PolyUtil; 017import edu.jas.structure.GcdRingElem; 018import edu.jas.ufd.PolyUfdUtil; 019import edu.jas.ufd.Quotient; 020import edu.jas.ufd.QuotientRing; 021 022 023/** 024 * Groebner Base sequential algorithm for rational function coefficients, 025 * fraction free computation. Implements Groebner bases. 026 * @param <C> Quotient coefficient type 027 * @author Heinz Kredel 028 */ 029 030public class GroebnerBaseSeqQuotient<C extends GcdRingElem<C>> extends GroebnerBaseAbstract<Quotient<C>> { 031 032 033 private static final Logger logger = Logger.getLogger(GroebnerBaseSeqQuotient.class); 034 035 036 private final boolean debug = logger.isDebugEnabled(); 037 038 039 public final GroebnerBaseAbstract<GenPolynomial<C>> bba; 040 041 042 /** 043 * Constructor. 044 * @param rf quotient coefficient ring factory. 045 */ 046 public GroebnerBaseSeqQuotient(QuotientRing<C> rf) { 047 super(); 048 bba = new GroebnerBasePseudoRecSeq<C>(rf.ring); 049 } 050 051 052 /** 053 * Get the String representation with GB engines. 054 * @see java.lang.Object#toString() 055 */ 056 @Override 057 public String toString() { 058 return this.getClass().getSimpleName() + "(" + bba.toString() + ")"; 059 } 060 061 062 /** 063 * Groebner base using fraction free computation. 064 * @param modv module variable number. 065 * @param F polynomial list. 066 * @return GB(F) a Groebner base of F. 067 */ 068 @Override 069 public List<GenPolynomial<Quotient<C>>> GB(int modv, List<GenPolynomial<Quotient<C>>> F) { 070 List<GenPolynomial<Quotient<C>>> G = F; 071 if (F == null || F.isEmpty()) { 072 return G; 073 } 074 GenPolynomialRing<Quotient<C>> rring = F.get(0).ring; 075 QuotientRing<C> cf = (QuotientRing<C>) rring.coFac; 076 GenPolynomialRing<GenPolynomial<C>> iring = new GenPolynomialRing<GenPolynomial<C>>(cf.ring, rring); 077 List<GenPolynomial<GenPolynomial<C>>> Fi = PolyUfdUtil.<C> integralFromQuotientCoefficients(iring, F); 078 //System.out.println("Fi = " + Fi); 079 logger.info("#Fi = " + Fi.size()); 080 081 List<GenPolynomial<GenPolynomial<C>>> Gi = bba.GB(modv, Fi); 082 //System.out.println("Gi = " + Gi); 083 logger.info("#Gi = " + Gi.size()); 084 085 G = PolyUfdUtil.<C> quotientFromIntegralCoefficients(rring, Gi); 086 G = PolyUtil.<Quotient<C>> monic(G); 087 return G; 088 } 089 090 091 /** 092 * Minimal ordered Groebner basis. 093 * @param Gp a Groebner base. 094 * @return a reduced Groebner base of Gp. 095 */ 096 @Override 097 public List<GenPolynomial<Quotient<C>>> minimalGB(List<GenPolynomial<Quotient<C>>> Gp) { 098 if (Gp == null || Gp.size() <= 1) { 099 return Gp; 100 } 101 // remove zero polynomials 102 List<GenPolynomial<Quotient<C>>> G = new ArrayList<GenPolynomial<Quotient<C>>>(Gp.size()); 103 for (GenPolynomial<Quotient<C>> a : Gp) { 104 if (a != null && !a.isZERO()) { // always true in GB() 105 // already positive a = a.abs(); 106 G.add(a); 107 } 108 } 109 if (G.size() <= 1) { 110 return G; 111 } 112 // remove top reducible polynomials 113 GenPolynomial<Quotient<C>> a; 114 List<GenPolynomial<Quotient<C>>> F; 115 F = new ArrayList<GenPolynomial<Quotient<C>>>(G.size()); 116 while (G.size() > 0) { 117 a = G.remove(0); 118 if (red.isTopReducible(G, a) || red.isTopReducible(F, a)) { 119 // drop polynomial 120 if (debug) { 121 System.out.println("dropped " + a); 122 List<GenPolynomial<Quotient<C>>> ff; 123 ff = new ArrayList<GenPolynomial<Quotient<C>>>(G); 124 ff.addAll(F); 125 a = red.normalform(ff, a); 126 if (!a.isZERO()) { 127 System.out.println("error, nf(a) " + a); 128 } 129 } 130 } else { 131 F.add(a); 132 } 133 } 134 G = F; 135 if (G.size() <= 1) { 136 return G; 137 } 138 139 // reduce remaining polynomials 140 GenPolynomialRing<Quotient<C>> rring = G.get(0).ring; 141 QuotientRing<C> cf = (QuotientRing<C>) rring.coFac; 142 GenPolynomialRing<GenPolynomial<C>> iring = new GenPolynomialRing<GenPolynomial<C>>(cf.ring, rring); 143 List<GenPolynomial<GenPolynomial<C>>> Fi = PolyUfdUtil.integralFromQuotientCoefficients(iring, F); 144 logger.info("#Fi = " + Fi.size()); 145 146 List<GenPolynomial<GenPolynomial<C>>> Gi = bba.minimalGB(Fi); 147 logger.info("#Gi = " + Gi.size()); 148 149 G = PolyUfdUtil.<C> quotientFromIntegralCoefficients(rring, Gi); 150 G = PolyUtil.<Quotient<C>> monic(G); 151 return G; 152 } 153 154 155 /** 156 * Cleanup and terminate ThreadPool. 157 */ 158 @Override 159 public void terminate() { 160 bba.terminate(); 161 } 162 163 164 /** 165 * Cancel ThreadPool. 166 */ 167 @Override 168 public int cancel() { 169 return bba.cancel(); 170 } 171 172}