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