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 }