Source code

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