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