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