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    }