001 /* 002 * $Id: RootFactory.java 3649 2011-05-28 12:51:09Z kredel $ 003 */ 004 005 package edu.jas.root; 006 007 008 import java.util.ArrayList; 009 import java.util.List; 010 import java.util.Set; 011 012 import edu.jas.arith.Rational; 013 import edu.jas.arith.BigRational; 014 import edu.jas.poly.Complex; 015 import edu.jas.poly.ComplexRing; 016 import edu.jas.poly.PolyUtil; 017 import edu.jas.poly.GenPolynomial; 018 import edu.jas.poly.GenPolynomialRing; 019 import edu.jas.structure.GcdRingElem; 020 import edu.jas.ufd.FactorAbstract; 021 import edu.jas.ufd.FactorFactory; 022 import edu.jas.ufd.SquarefreeAbstract; 023 import edu.jas.ufd.SquarefreeFactory; 024 025 026 /** 027 * Roots factory. 028 * @author Heinz Kredel 029 */ 030 public class RootFactory { 031 032 033 /** 034 * Is real algebraic number a root of a polynomial. 035 * @param f univariate polynomial. 036 * @param r real algebraic number. 037 * @return true, if f(r) == 0, else false; 038 */ 039 public static <C extends GcdRingElem<C> & Rational> 040 boolean isRoot(GenPolynomial<C> f, RealAlgebraicNumber<C> r) { 041 RealAlgebraicRing<C> rr = r.factory(); 042 GenPolynomialRing<RealAlgebraicNumber<C>> rfac 043 = new GenPolynomialRing<RealAlgebraicNumber<C>>(rr,f.factory()); 044 GenPolynomial<RealAlgebraicNumber<C>> p; 045 p = PolyUtilRoot.<C> convertToRealCoefficients(rfac,f); 046 RealAlgebraicNumber<C> a = PolyUtil.<RealAlgebraicNumber<C>> evaluateMain(rr,p,r); 047 return a.isZERO(); 048 } 049 050 051 /** 052 * Real algebraic numbers. 053 * @param f univariate polynomial. 054 * @return a list of different real algebraic numbers. 055 */ 056 public static <C extends GcdRingElem<C> & Rational> 057 List<RealAlgebraicNumber<C>> realAlgebraicNumbers(GenPolynomial<C> f) { 058 RealRoots<C> rr = new RealRootsSturm<C>(); 059 SquarefreeAbstract<C> engine = SquarefreeFactory.<C> getImplementation(f.ring.coFac); 060 Set<GenPolynomial<C>> S = engine.squarefreeFactors(f).keySet(); 061 List<RealAlgebraicNumber<C>> list = new ArrayList<RealAlgebraicNumber<C>>(); 062 for (GenPolynomial<C> sp : S) { 063 List<Interval<C>> iv = rr.realRoots(sp); 064 for (Interval<C> I : iv) { 065 RealAlgebraicRing<C> rar = new RealAlgebraicRing<C>(sp, I); 066 RealAlgebraicNumber<C> rn = rar.getGenerator(); 067 list.add(rn); 068 } 069 } 070 return list; 071 } 072 073 074 /** 075 * Real algebraic numbers. 076 * @param f univariate polynomial. 077 * @param eps rational precision. 078 * @return a list of different real algebraic numbers. 079 */ 080 public static <C extends GcdRingElem<C> & Rational> 081 List<RealAlgebraicNumber<C>> realAlgebraicNumbers(GenPolynomial<C> f, BigRational eps) { 082 RealRoots<C> rr = new RealRootsSturm<C>(); 083 SquarefreeAbstract<C> engine = SquarefreeFactory.<C> getImplementation(f.ring.coFac); 084 Set<GenPolynomial<C>> S = engine.squarefreeFactors(f).keySet(); 085 List<RealAlgebraicNumber<C>> list = new ArrayList<RealAlgebraicNumber<C>>(); 086 for (GenPolynomial<C> sp : S) { 087 List<Interval<C>> iv = rr.realRoots(sp,eps); 088 for (Interval<C> I : iv) { 089 RealAlgebraicRing<C> rar = new RealAlgebraicRing<C>(sp, I); 090 rar.setEps(eps); 091 RealAlgebraicNumber<C> rn = rar.getGenerator(); 092 list.add(rn); 093 } 094 } 095 return list; 096 } 097 098 099 /** 100 * Real algebraic numbers from a field. 101 * @param f univariate polynomial. 102 * @return a list of different real algebraic numbers from a field. 103 */ 104 public static <C extends GcdRingElem<C> & Rational> 105 List<RealAlgebraicNumber<C>> realAlgebraicNumbersField(GenPolynomial<C> f) { 106 RealRoots<C> rr = new RealRootsSturm<C>(); 107 FactorAbstract<C> engine = FactorFactory.<C> getImplementation(f.ring.coFac); 108 Set<GenPolynomial<C>> S = engine.baseFactors(f).keySet(); 109 List<RealAlgebraicNumber<C>> list = new ArrayList<RealAlgebraicNumber<C>>(); 110 for (GenPolynomial<C> sp : S) { 111 List<Interval<C>> iv = rr.realRoots(sp); 112 for (Interval<C> I : iv) { 113 RealAlgebraicRing<C> rar = new RealAlgebraicRing<C>(sp, I, true);//field 114 RealAlgebraicNumber<C> rn = rar.getGenerator(); 115 list.add(rn); 116 } 117 } 118 return list; 119 } 120 121 122 /** 123 * Real algebraic numbers from a field. 124 * @param f univariate polynomial. 125 * @param eps rational precision. 126 * @return a list of different real algebraic numbers from a field. 127 */ 128 public static <C extends GcdRingElem<C> & Rational> 129 List<RealAlgebraicNumber<C>> realAlgebraicNumbersField(GenPolynomial<C> f, BigRational eps) { 130 RealRoots<C> rr = new RealRootsSturm<C>(); 131 FactorAbstract<C> engine = FactorFactory.<C> getImplementation(f.ring.coFac); 132 Set<GenPolynomial<C>> S = engine.baseFactors(f).keySet(); 133 List<RealAlgebraicNumber<C>> list = new ArrayList<RealAlgebraicNumber<C>>(); 134 for (GenPolynomial<C> sp : S) { 135 List<Interval<C>> iv = rr.realRoots(sp,eps); 136 for (Interval<C> I : iv) { 137 RealAlgebraicRing<C> rar = new RealAlgebraicRing<C>(sp, I, true);//field 138 rar.setEps(eps); 139 RealAlgebraicNumber<C> rn = rar.getGenerator(); 140 list.add(rn); 141 } 142 } 143 return list; 144 } 145 146 147 /** 148 * Real algebraic numbers from a irreducible polynomial. 149 * @param f univariate irreducible polynomial. 150 * @return a list of different real algebraic numbers from a field. 151 */ 152 public static <C extends GcdRingElem<C> & Rational> 153 List<RealAlgebraicNumber<C>> realAlgebraicNumbersIrred(GenPolynomial<C> f) { 154 RealRoots<C> rr = new RealRootsSturm<C>(); 155 List<RealAlgebraicNumber<C>> list = new ArrayList<RealAlgebraicNumber<C>>(); 156 List<Interval<C>> iv = rr.realRoots(f); 157 for (Interval<C> I : iv) { 158 RealAlgebraicRing<C> rar = new RealAlgebraicRing<C>(f, I, true);//field 159 RealAlgebraicNumber<C> rn = rar.getGenerator(); 160 list.add(rn); 161 } 162 return list; 163 } 164 165 166 /** 167 * Real algebraic numbers from a irreducible polynomial. 168 * @param f univariate irreducible polynomial. 169 * @param eps rational precision. 170 * @return a list of different real algebraic numbers from a field. 171 */ 172 public static <C extends GcdRingElem<C> & Rational> 173 List<RealAlgebraicNumber<C>> realAlgebraicNumbersIrred(GenPolynomial<C> f, BigRational eps) { 174 RealRoots<C> rr = new RealRootsSturm<C>(); 175 List<RealAlgebraicNumber<C>> list = new ArrayList<RealAlgebraicNumber<C>>(); 176 List<Interval<C>> iv = rr.realRoots(f,eps); 177 for (Interval<C> I : iv) { 178 RealAlgebraicRing<C> rar = new RealAlgebraicRing<C>(f, I, true);//field 179 rar.setEps(eps); 180 RealAlgebraicNumber<C> rn = rar.getGenerator(); 181 list.add(rn); 182 } 183 return list; 184 } 185 186 187 /** 188 * Is complex algebraic number a root of a polynomial. 189 * @param f univariate polynomial. 190 * @param r complex algebraic number. 191 * @return true, if f(r) == 0, else false; 192 */ 193 public static <C extends GcdRingElem<C> & Rational> 194 boolean isRoot(GenPolynomial<C> f, ComplexAlgebraicNumber<C> r) { 195 ComplexAlgebraicRing<C> cr = r.factory(); 196 GenPolynomialRing<ComplexAlgebraicNumber<C>> cfac 197 = new GenPolynomialRing<ComplexAlgebraicNumber<C>>(cr,f.factory()); 198 GenPolynomial<ComplexAlgebraicNumber<C>> p; 199 p = PolyUtilRoot.<C> convertToComplexCoefficients(cfac,f); 200 ComplexAlgebraicNumber<C> a = PolyUtil.<ComplexAlgebraicNumber<C>> evaluateMain(cr,p,r); 201 return a.isZERO(); 202 } 203 204 205 /** 206 * Is complex algebraic number a root of a complex polynomial. 207 * @param f univariate complex polynomial. 208 * @param r complex algebraic number. 209 * @return true, if f(r) == 0, else false; 210 */ 211 public static <C extends GcdRingElem<C> & Rational> 212 boolean isRootComplex(GenPolynomial<Complex<C>> f, ComplexAlgebraicNumber<C> r) { 213 ComplexAlgebraicRing<C> cr = r.factory(); 214 GenPolynomialRing<ComplexAlgebraicNumber<C>> cfac 215 = new GenPolynomialRing<ComplexAlgebraicNumber<C>>(cr,f.factory()); 216 GenPolynomial<ComplexAlgebraicNumber<C>> p; 217 p = PolyUtilRoot.<C> convertToComplexCoefficientsFromComplex(cfac,f); 218 ComplexAlgebraicNumber<C> a = PolyUtil.<ComplexAlgebraicNumber<C>> evaluateMain(cr,p,r); 219 return a.isZERO(); 220 } 221 222 223 /** 224 * Complex algebraic numbers. 225 * @param f univariate polynomial. 226 * @return a list of different complex algebraic numbers. 227 */ 228 public static <C extends GcdRingElem<C> & Rational> 229 List<ComplexAlgebraicNumber<C>> complexAlgebraicNumbersComplex(GenPolynomial<Complex<C>> f) { 230 ComplexRoots<C> cr = new ComplexRootsSturm<C>(f.ring.coFac); 231 SquarefreeAbstract<Complex<C>> engine = SquarefreeFactory 232 .<Complex<C>> getImplementation(f.ring.coFac); 233 Set<GenPolynomial<Complex<C>>> S = engine.squarefreeFactors(f).keySet(); 234 List<ComplexAlgebraicNumber<C>> list = new ArrayList<ComplexAlgebraicNumber<C>>(); 235 for (GenPolynomial<Complex<C>> sp : S) { 236 List<Rectangle<C>> iv = cr.complexRoots(sp); 237 for (Rectangle<C> I : iv) { 238 ComplexAlgebraicRing<C> car = new ComplexAlgebraicRing<C>(sp, I); 239 ComplexAlgebraicNumber<C> cn = car.getGenerator(); 240 list.add(cn); 241 } 242 } 243 return list; 244 } 245 246 247 /** 248 * Complex algebraic numbers. 249 * @param f univariate polynomial. 250 * @param eps rational precision. 251 * @return a list of different complex algebraic numbers. 252 */ 253 public static <C extends GcdRingElem<C> & Rational> 254 List<ComplexAlgebraicNumber<C>> complexAlgebraicNumbersComplex(GenPolynomial<Complex<C>> f, BigRational eps) { 255 ComplexRoots<C> cr = new ComplexRootsSturm<C>(f.ring.coFac); 256 SquarefreeAbstract<Complex<C>> engine = SquarefreeFactory 257 .<Complex<C>> getImplementation(f.ring.coFac); 258 Set<GenPolynomial<Complex<C>>> S = engine.squarefreeFactors(f).keySet(); 259 List<ComplexAlgebraicNumber<C>> list = new ArrayList<ComplexAlgebraicNumber<C>>(); 260 for (GenPolynomial<Complex<C>> sp : S) { 261 List<Rectangle<C>> iv = cr.complexRoots(sp); 262 for (Rectangle<C> I : iv) { 263 Rectangle<C> Iv = I; 264 try { 265 Iv = cr.complexRootRefinement(I,sp,eps); 266 } catch (InvalidBoundaryException e) { 267 e.printStackTrace(); 268 } 269 ComplexAlgebraicRing<C> car = new ComplexAlgebraicRing<C>(sp, Iv); 270 car.setEps(eps); 271 ComplexAlgebraicNumber<C> cn = car.getGenerator(); 272 list.add(cn); 273 } 274 } 275 return list; 276 } 277 278 279 /** 280 * Complex algebraic numbers. 281 * @param f univariate (rational) polynomial. 282 * @return a list of different complex algebraic numbers. 283 */ 284 public static <C extends GcdRingElem<C> & Rational> 285 List<ComplexAlgebraicNumber<C>> complexAlgebraicNumbers(GenPolynomial<C> f) { 286 if ( f.ring.coFac instanceof Complex ) { 287 throw new IllegalArgumentException("f already has Complex coefficients " + f.ring); 288 } 289 ComplexRing<C> cr = new ComplexRing<C>( f.ring.coFac ); 290 GenPolynomialRing<Complex<C>> fac = new GenPolynomialRing<Complex<C>>(cr,f.ring); 291 GenPolynomial<Complex<C>> fc = PolyUtil.<C>complexFromAny(fac,f); 292 return complexAlgebraicNumbersComplex(fc); 293 } 294 295 296 /** 297 * Complex algebraic numbers. 298 * @param f univariate (rational) polynomial. 299 * @param eps rational precision. 300 * @return a list of different complex algebraic numbers. 301 */ 302 public static <C extends GcdRingElem<C> & Rational> 303 List<ComplexAlgebraicNumber<C>> complexAlgebraicNumbers(GenPolynomial<C> f, BigRational eps) { 304 if ( f.ring.coFac instanceof Complex ) { 305 throw new IllegalArgumentException("f already has Complex coefficients " + f.ring); 306 } 307 ComplexRing<C> cr = new ComplexRing<C>( f.ring.coFac ); 308 GenPolynomialRing<Complex<C>> fac = new GenPolynomialRing<Complex<C>>(cr,f.ring); 309 GenPolynomial<Complex<C>> fc = PolyUtil.<C>complexFromAny(fac,f); 310 return complexAlgebraicNumbersComplex(fc,eps); 311 } 312 313 }