001    /*
002     * $Id: PolyUtilRoot.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.Map;
011    import java.util.SortedMap;
012    import java.util.TreeMap;
013    
014    import org.apache.log4j.Logger;
015    
016    import edu.jas.arith.Rational;
017    import edu.jas.poly.Complex;
018    import edu.jas.poly.ComplexRing;
019    import edu.jas.poly.PolyUtil;
020    import edu.jas.poly.GenPolynomial;
021    import edu.jas.poly.GenPolynomialRing;
022    import edu.jas.poly.AlgebraicNumber;
023    import edu.jas.poly.AlgebraicNumberRing;
024    import edu.jas.structure.Element;
025    import edu.jas.structure.GcdRingElem;
026    import edu.jas.structure.RingElem;
027    import edu.jas.structure.RingFactory;
028    import edu.jas.structure.UnaryFunctor;
029    import edu.jas.util.ListUtil;
030    
031    
032    /**
033     * Polynomial utilities related to real and complex roots.
034     * @author Heinz Kredel
035     */
036    
037    public class PolyUtilRoot {
038    
039    
040        private static final Logger logger = Logger.getLogger(PolyUtilRoot.class);
041    
042    
043        private static boolean debug = logger.isDebugEnabled();
044    
045    
046        /**
047         * Convert to RealAlgebraicNumber coefficients. Represent as polynomial with
048         * RealAlgebraicNumber<C> coefficients, C is e.g. ModInteger or BigRational.
049         * @param pfac result polynomial factory.
050         * @param A polynomial with C coefficients to be converted.
051         * @return polynomial with RealAlgebraicNumber&lt;C&gt; coefficients.
052         */
053        public static <C extends GcdRingElem<C> & Rational> GenPolynomial<RealAlgebraicNumber<C>> convertToAlgebraicCoefficients(
054                        GenPolynomialRing<RealAlgebraicNumber<C>> pfac, GenPolynomial<C> A) {
055            RealAlgebraicRing<C> afac = (RealAlgebraicRing<C>) pfac.coFac;
056            return PolyUtil.<C, RealAlgebraicNumber<C>> map(pfac, A, new CoeffToReAlg<C>(afac));
057        }
058    
059    
060        /**
061         * Convert to recursive RealAlgebraicNumber coefficients. Represent as
062         * polynomial with recursive RealAlgebraicNumber<C> coefficients, C is e.g.
063         * ModInteger or BigRational.
064         * @param depth recursion depth of RealAlgebraicNumber coefficients.
065         * @param pfac result polynomial factory.
066         * @param A polynomial with C coefficients to be converted.
067         * @return polynomial with RealAlgebraicNumber&lt;C&gt; coefficients.
068         */
069        public static <C extends GcdRingElem<C> & Rational> GenPolynomial<RealAlgebraicNumber<C>> convertToRecAlgebraicCoefficients(
070                        int depth, GenPolynomialRing<RealAlgebraicNumber<C>> pfac, GenPolynomial<C> A) {
071            RealAlgebraicRing<C> afac = (RealAlgebraicRing<C>) pfac.coFac;
072            return PolyUtil.<C, RealAlgebraicNumber<C>> map(pfac, A, new CoeffToRecReAlg<C>(depth, afac));
073        }
074    
075    
076        /**
077         * Convert to RealAlgebraicNumber coefficients. Represent as polynomial with
078         * RealAlgebraicNumber<C> coefficients, C is e.g. ModInteger or BigRational.
079         * @param pfac result polynomial factory.
080         * @param A recursive polynomial with GenPolynomial&lt;BigInteger&gt;
081         *            coefficients to be converted.
082         * @return polynomial with RealAlgebraicNumber&lt;C&gt; coefficients.
083         */
084        public static <C extends GcdRingElem<C> & Rational> GenPolynomial<RealAlgebraicNumber<C>> convertRecursiveToAlgebraicCoefficients(
085                        GenPolynomialRing<RealAlgebraicNumber<C>> pfac, GenPolynomial<GenPolynomial<C>> A) {
086            RealAlgebraicRing<C> afac = (RealAlgebraicRing<C>) pfac.coFac;
087            return PolyUtil.<GenPolynomial<C>, RealAlgebraicNumber<C>> map(pfac, A, new PolyToReAlg<C>(afac));
088        }
089    
090    
091        /**
092         * Convert to AlgebraicNumber coefficients. Represent as polynomial with
093         * AlgebraicNumber<C> coefficients.
094         * @param afac result polynomial factory.
095         * @param A polynomial with RealAlgebraicNumber&lt;C&gt; coefficients to be converted.
096         * @return polynomial with AlgebraicNumber&lt;C&gt; coefficients.
097         */
098        public static <C extends GcdRingElem<C> & Rational> GenPolynomial<AlgebraicNumber<C>> algebraicFromRealCoefficients(
099                        GenPolynomialRing<AlgebraicNumber<C>> afac, GenPolynomial<RealAlgebraicNumber<C>> A) {
100            AlgebraicNumberRing<C> cfac = (AlgebraicNumberRing<C>) afac.coFac;
101            return PolyUtil.<RealAlgebraicNumber<C>, AlgebraicNumber<C>> map(afac, A, new AlgFromRealCoeff<C>(cfac));
102        }
103    
104    
105        /**
106         * Convert to RealAlgebraicNumber coefficients. Represent as polynomial with
107         * RealAlgebraicNumber<C> coefficients.
108         * @param rfac result polynomial factory.
109         * @param A polynomial with AlgebraicNumber&lt;C&gt; coefficients to be converted.
110         * @return polynomial with RealAlgebraicNumber&lt;C&gt; coefficients.
111         */
112        public static <C extends GcdRingElem<C> & Rational> GenPolynomial<RealAlgebraicNumber<C>> realFromAlgebraicCoefficients(
113                        GenPolynomialRing<RealAlgebraicNumber<C>> rfac, GenPolynomial<AlgebraicNumber<C>> A) {
114            RealAlgebraicRing<C> cfac = (RealAlgebraicRing<C>) rfac.coFac;
115            return PolyUtil.<AlgebraicNumber<C>, RealAlgebraicNumber<C>> map(rfac, A, new RealFromAlgCoeff<C>(cfac));
116        }
117    
118    
119        /**
120         * Convert to RealAlgebraicNumber coefficients. Represent as polynomial with
121         * RealAlgebraicNumber<C> coefficients, C is e.g. BigRational.
122         * @param pfac result polynomial factory.
123         * @param A polynomial with C coefficients to be converted.
124         * @return polynomial with RealAlgebraicNumber&lt;C&gt; coefficients.
125         */
126        public static <C extends GcdRingElem<C> & Rational> GenPolynomial<RealAlgebraicNumber<C>> 
127               convertToRealCoefficients(GenPolynomialRing<RealAlgebraicNumber<C>> pfac, GenPolynomial<C> A) {
128            RealAlgebraicRing<C> afac = (RealAlgebraicRing<C>) pfac.coFac;
129            return PolyUtil.<C, RealAlgebraicNumber<C>> map(pfac, A, new CoeffToReal<C>(afac));
130        }
131    
132    
133        /**
134         * Convert to ComplexAlgebraicNumber coefficients. Represent as polynomial with
135         * ComplexAlgebraicNumber<C> coefficients, C is e.g. BigRational.
136         * @param pfac result polynomial factory.
137         * @param A polynomial with C coefficients to be converted.
138         * @return polynomial with ComplexAlgebraicNumber&lt;C&gt; coefficients.
139         */
140        public static <C extends GcdRingElem<C> & Rational> GenPolynomial<ComplexAlgebraicNumber<C>> 
141               convertToComplexCoefficients(GenPolynomialRing<ComplexAlgebraicNumber<C>> pfac, GenPolynomial<C> A) {
142            ComplexAlgebraicRing<C> afac = (ComplexAlgebraicRing<C>) pfac.coFac;
143            return PolyUtil.<C, ComplexAlgebraicNumber<C>> map(pfac, A, new CoeffToComplex<C>(afac));
144        }
145    
146    
147        /**
148         * Convert to ComplexAlgebraicNumber coefficients. Represent as polynomial with
149         * ComplexAlgebraicNumber<C> coefficients, C is e.g. BigRational.
150         * @param pfac result polynomial factory.
151         * @param A polynomial with C coefficients to be converted.
152         * @return polynomial with ComplexAlgebraicNumber&lt;C&gt; coefficients.
153         */
154        public static <C extends GcdRingElem<C> & Rational> GenPolynomial<ComplexAlgebraicNumber<C>> 
155               convertToComplexCoefficientsFromComplex(GenPolynomialRing<ComplexAlgebraicNumber<C>> pfac, GenPolynomial<Complex<C>> A) {
156            ComplexAlgebraicRing<C> afac = (ComplexAlgebraicRing<C>) pfac.coFac;
157            return PolyUtil.<Complex<C>, ComplexAlgebraicNumber<C>> map(pfac, A, new CoeffToComplexFromComplex<C>(afac));
158        }
159    
160    }
161    
162    
163    /**
164     * Polynomial to algebriac functor.
165     */
166    class PolyToReAlg<C extends GcdRingElem<C> & Rational> implements UnaryFunctor<GenPolynomial<C>, RealAlgebraicNumber<C>> {
167    
168    
169        final protected RealAlgebraicRing<C> afac;
170    
171    
172        public PolyToReAlg(RealAlgebraicRing<C> fac) {
173            if (fac == null) {
174                throw new IllegalArgumentException("fac must not be null");
175            }
176            afac = fac;
177        }
178    
179    
180        public RealAlgebraicNumber<C> eval(GenPolynomial<C> c) {
181            if (c == null) {
182                return afac.getZERO();
183            } else {
184                return new RealAlgebraicNumber<C>(afac, c);
185            }
186        }
187    }
188    
189    
190    /**
191     * Coefficient to algebriac functor.
192     */
193    class CoeffToReAlg<C extends GcdRingElem<C> & Rational> implements UnaryFunctor<C, RealAlgebraicNumber<C>> {
194    
195    
196        final protected RealAlgebraicRing<C> afac;
197    
198    
199        final protected GenPolynomial<C> zero;
200    
201    
202        public CoeffToReAlg(RealAlgebraicRing<C> fac) {
203            if (fac == null) {
204                throw new IllegalArgumentException("fac must not be null");
205            }
206            afac = fac;
207            GenPolynomialRing<C> pfac = afac.algebraic.ring;
208            zero = pfac.getZERO();
209        }
210    
211    
212        public RealAlgebraicNumber<C> eval(C c) {
213            if (c == null) {
214                return afac.getZERO();
215            } else {
216                return new RealAlgebraicNumber<C>(afac, zero.sum(c));
217            }
218        }
219    }
220    
221    
222    /**
223     * Coefficient to recursive algebriac functor.
224     */
225    class CoeffToRecReAlg<C extends GcdRingElem<C> & Rational> implements UnaryFunctor<C, RealAlgebraicNumber<C>> {
226    
227    
228        final protected List<RealAlgebraicRing<C>> lfac;
229    
230    
231        final int depth;
232    
233    
234        @SuppressWarnings("unchecked")
235        public CoeffToRecReAlg(int depth, RealAlgebraicRing<C> fac) {
236            if (fac == null) {
237                throw new IllegalArgumentException("fac must not be null");
238            }
239            RealAlgebraicRing<C> afac = fac;
240            this.depth = depth;
241            lfac = new ArrayList<RealAlgebraicRing<C>>(depth);
242            lfac.add(fac);
243            for (int i = 1; i < depth; i++) {
244                RingFactory<C> rf = afac.algebraic.ring.coFac;
245                if (!(rf instanceof RealAlgebraicRing)) {
246                    throw new IllegalArgumentException("fac depth to low");
247                }
248                afac = (RealAlgebraicRing<C>) (Object) rf;
249                lfac.add(afac);
250            }
251        }
252    
253    
254        @SuppressWarnings("unchecked")
255        public RealAlgebraicNumber<C> eval(C c) {
256            if (c == null) {
257                return lfac.get(0).getZERO();
258            }
259            C ac = c;
260            RealAlgebraicRing<C> af = lfac.get(lfac.size() - 1);
261            GenPolynomial<C> zero = af.algebraic.ring.getZERO();
262            RealAlgebraicNumber<C> an = new RealAlgebraicNumber<C>(af, zero.sum(ac));
263            for (int i = lfac.size() - 2; i >= 0; i--) {
264                af = lfac.get(i);
265                zero = af.algebraic.ring.getZERO();
266                ac = (C) (Object) an;
267                an = new RealAlgebraicNumber<C>(af, zero.sum(ac));
268            }
269            return an;
270        }
271    }
272    
273    
274    /**
275     * Coefficient to algebriac from real algebraic functor.
276     */
277    class AlgFromRealCoeff<C extends GcdRingElem<C> & Rational> implements UnaryFunctor<RealAlgebraicNumber<C>, AlgebraicNumber<C>> {
278    
279    
280        final protected AlgebraicNumberRing<C> afac;
281    
282    
283        public AlgFromRealCoeff(AlgebraicNumberRing<C> fac) {
284            if (fac == null) {
285                throw new IllegalArgumentException("fac must not be null");
286            }
287            afac = fac;
288        }
289    
290    
291        public AlgebraicNumber<C> eval(RealAlgebraicNumber<C> c) {
292            if (c == null) {
293                return afac.getZERO();
294            } else {
295                return c.number; 
296            }
297        }
298    }
299    
300    
301    /**
302     * Coefficient to real algebriac from algebraic functor.
303     */
304    class RealFromAlgCoeff<C extends GcdRingElem<C> & Rational> implements UnaryFunctor<AlgebraicNumber<C>, RealAlgebraicNumber<C>> {
305    
306    
307        final protected RealAlgebraicRing<C> rfac;
308    
309    
310        public RealFromAlgCoeff(RealAlgebraicRing<C> fac) {
311            if (fac == null) {
312                throw new IllegalArgumentException("fac must not be null");
313            }
314            rfac = fac;
315        }
316    
317    
318        public RealAlgebraicNumber<C> eval(AlgebraicNumber<C> c) {
319            if (c == null) {
320                return rfac.getZERO();
321            } else {
322                return new RealAlgebraicNumber<C>(rfac, c);
323            }
324        }
325    }
326    
327    
328    /**
329     * Coefficient to real algebriac functor.
330     */
331    class CoeffToReal<C extends GcdRingElem<C> & Rational> implements UnaryFunctor<C, RealAlgebraicNumber<C>> {
332    
333    
334        final protected RealAlgebraicRing<C> rfac;
335    
336    
337        final protected AlgebraicNumber<C> zero;
338    
339    
340        public CoeffToReal(RealAlgebraicRing<C> fac) {
341            if (fac == null) {
342                throw new IllegalArgumentException("fac must not be null");
343            }
344            rfac = fac;
345            AlgebraicNumberRing<C> afac = rfac.algebraic;
346            zero = afac.getZERO();
347        }
348    
349    
350        public RealAlgebraicNumber<C> eval(C c) {
351            if (c == null) {
352                return rfac.getZERO();
353            } else {
354                return new RealAlgebraicNumber<C>(rfac, zero.sum(c));
355            }
356        }
357    }
358    
359    
360    /**
361     * Coefficient to complex algebriac functor.
362     */
363    class CoeffToComplex<C extends GcdRingElem<C> & Rational> implements UnaryFunctor<C, ComplexAlgebraicNumber<C>> {
364    
365    
366        final protected ComplexAlgebraicRing<C> cfac;
367    
368    
369        final protected AlgebraicNumber<Complex<C>> zero;
370    
371    
372        final protected ComplexRing<C> cr;
373    
374    
375        public CoeffToComplex(ComplexAlgebraicRing<C> fac) {
376            if (fac == null) {
377                throw new IllegalArgumentException("fac must not be null");
378            }
379            cfac = fac;
380            AlgebraicNumberRing<Complex<C>> afac = cfac.algebraic;
381            zero = afac.getZERO();
382            cr = (ComplexRing<C>) afac.ring.coFac;
383        }
384    
385    
386        public ComplexAlgebraicNumber<C> eval(C c) {
387            if (c == null) {
388                return cfac.getZERO();
389            } else {
390                return new ComplexAlgebraicNumber<C>(cfac, zero.sum(new Complex<C>(cr,c)));
391            }
392        }
393    }
394    
395    
396    
397    /**
398     * Coefficient to complex algebriac from complex functor.
399     */
400    class CoeffToComplexFromComplex<C extends GcdRingElem<C> & Rational> implements UnaryFunctor<Complex<C>, ComplexAlgebraicNumber<C>> {
401    
402    
403        final protected ComplexAlgebraicRing<C> cfac;
404    
405    
406        final protected AlgebraicNumber<Complex<C>> zero;
407    
408    
409        //final protected ComplexRing<C> cr;
410    
411    
412        public CoeffToComplexFromComplex(ComplexAlgebraicRing<C> fac) {
413            if (fac == null) {
414                throw new IllegalArgumentException("fac must not be null");
415            }
416            cfac = fac;
417            AlgebraicNumberRing<Complex<C>> afac = cfac.algebraic;
418            zero = afac.getZERO();
419            //cr = (ComplexRing<C>) afac.ring.coFac;
420        }
421    
422    
423        public ComplexAlgebraicNumber<C> eval(Complex<C> c) {
424            if (c == null) {
425                return cfac.getZERO();
426            } else {
427                return new ComplexAlgebraicNumber<C>(cfac, zero.sum(c));
428            }
429        }
430    }