Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.ufd;
006
007
008import java.util.ArrayList;
009import java.util.List;
010import java.util.concurrent.Callable;
011import java.util.concurrent.ExecutionException;
012import java.util.concurrent.ExecutorService;
013
014import org.apache.logging.log4j.Logger;
015import org.apache.logging.log4j.LogManager; 
016
017import edu.jas.kern.ComputerThreads;
018import edu.jas.kern.PreemptingException;
019import edu.jas.poly.GenPolynomial;
020import edu.jas.structure.GcdRingElem;
021
022
023/**
024 * Greatest common divisor parallel proxy.  
025 * Executes methods from two implementations in parallel and 
026 * returns the result from the fastest run.
027 * @author Heinz Kredel
028 */
029
030public class GCDProxy<C extends GcdRingElem<C>> extends GreatestCommonDivisorAbstract<C> {
031
032
033    //       implements GreatestCommonDivisor<C> {
034
035    private static final Logger logger = LogManager.getLogger(GCDProxy.class);
036
037
038    private static final boolean debug = logger.isDebugEnabled(); //logger.isInfoEnabled();
039
040
041    /**
042     * GCD and resultant engines.
043     */
044    public final GreatestCommonDivisorAbstract<C> e1;
045
046
047    public final GreatestCommonDivisorAbstract<C> e2;
048
049
050    /**
051     * Thread pool.
052     */
053    protected transient ExecutorService pool;
054
055
056    /**
057     * Proxy constructor.
058     */
059    public GCDProxy(GreatestCommonDivisorAbstract<C> e1, GreatestCommonDivisorAbstract<C> e2) {
060        this.e1 = e1;
061        this.e2 = e2;
062        pool = ComputerThreads.getPool();
063        //System.out.println("pool 2 = "+pool);
064    }
065
066
067    /**
068     * Get the String representation with gcd engines.
069     * @see java.lang.Object#toString()
070     */
071    @Override
072    public String toString() {
073        return "GCDProxy[ " + e1.getClass().getName() + ", " + e2.getClass().getName() + " ]";
074    }
075
076
077    /**
078     * Univariate GenPolynomial greatest common divisor. 
079     * @param P univariate GenPolynomial.
080     * @param S univariate GenPolynomial.
081     * @return gcd(P,S).
082     */
083    @Override
084    public GenPolynomial<C> baseGcd(final GenPolynomial<C> P, final GenPolynomial<C> S) {
085        if ( debug ) {
086            if ( ComputerThreads.NO_THREADS ) {
087                throw new RuntimeException("this should not happen");
088            }
089        }
090        if (S == null || S.isZERO()) {
091            return P;
092        }
093        if (P == null || P.isZERO()) {
094            return S;
095        }
096        // parallel case
097        GenPolynomial<C> g = null;
098        //Callable<GenPolynomial<C>> c0;
099        //Callable<GenPolynomial<C>> c1;
100        List<Callable<GenPolynomial<C>>> cs = new ArrayList<Callable<GenPolynomial<C>>>(2);
101        cs.add(new Callable<GenPolynomial<C>>() {
102
103
104            public GenPolynomial<C> call() {
105                try {
106                    //System.out.println("starting e1 " + e1.getClass().getName());
107                    GenPolynomial<C> g = e1.baseGcd(P, S);
108                    if (debug) {
109                        logger.info("GCDProxy done e1 {}", e1.getClass().getName());
110                    }
111                    return g;
112                } catch (PreemptingException e) {
113                    throw new RuntimeException("GCDProxy e1 pre " + e);
114                    //return P.ring.getONE();
115                } catch (Exception e) {
116                    //e.printStackTrace();
117                    logger.info("GCDProxy e1 {}", e);
118                    logger.info("GCDProxy P = {}", P);
119                    logger.info("GCDProxy S = {}", S);
120                    throw new RuntimeException("GCDProxy e1 " + e);
121                    //return P.ring.getONE();
122                }
123            }
124        });
125        cs.add(new Callable<GenPolynomial<C>>() {
126
127
128            public GenPolynomial<C> call() {
129                try {
130                    //System.out.println("starting e2 " + e2.getClass().getName());
131                    GenPolynomial<C> g = e2.baseGcd(P, S);
132                    if (debug) {
133                        logger.info("GCDProxy done e2 {}", e2.getClass().getName());
134                    }
135                    return g;
136                } catch (PreemptingException e) {
137                    throw new RuntimeException("GCDProxy e2 pre " + e);
138                    //return P.ring.getONE();
139                } catch (Exception e) {
140                    //e.printStackTrace();
141                    logger.info("GCDProxy e2 {}", e);
142                    logger.info("GCDProxy P = {}", P);
143                    logger.info("GCDProxy S = {}", S);
144                    throw new RuntimeException("GCDProxy e2 " + e);
145                    //return P.ring.getONE();
146                }
147            }
148        });
149        try {
150            g = pool.invokeAny(cs);
151        } catch (InterruptedException ignored) {
152            logger.info("InterruptedException {}", ignored);
153            Thread.currentThread().interrupt();
154        } catch (ExecutionException e) {
155            logger.info("ExecutionException {}", e);
156            Thread.currentThread().interrupt();
157        }
158        return g;
159    }
160
161
162    /**
163     * Univariate GenPolynomial recursive greatest common divisor.
164     * @param P univariate recursive GenPolynomial.
165     * @param S univariate recursive GenPolynomial.
166     * @return gcd(P,S).
167     */
168    @Override
169    public GenPolynomial<GenPolynomial<C>> recursiveUnivariateGcd(final GenPolynomial<GenPolynomial<C>> P,
170            final GenPolynomial<GenPolynomial<C>> S) {
171        if ( debug ) {
172            if ( ComputerThreads.NO_THREADS ) {
173                throw new RuntimeException("this should not happen");
174            }
175        }
176        if (S == null || S.isZERO()) {
177            return P;
178        }
179        if (P == null || P.isZERO()) {
180            return S;
181        }
182        // parallel case
183        GenPolynomial<GenPolynomial<C>> g = null;
184        //Callable<GenPolynomial<GenPolynomial<C>>> c0;
185        //Callable<GenPolynomial<GenPolynomial<C>>> c1;
186        List<Callable<GenPolynomial<GenPolynomial<C>>>> cs = new ArrayList<Callable<GenPolynomial<GenPolynomial<C>>>>(
187                2);
188        cs.add(new Callable<GenPolynomial<GenPolynomial<C>>>() {
189
190
191            public GenPolynomial<GenPolynomial<C>> call() {
192                try {
193                    GenPolynomial<GenPolynomial<C>> g = e1.recursiveUnivariateGcd(P, S);
194                    if (debug) {
195                        logger.info("GCDProxy done e1 {}", e1.getClass().getName());
196                    }
197                    return g;
198                } catch (PreemptingException e) {
199                    throw new RuntimeException("GCDProxy e1 pre " + e);
200                    //return P.ring.getONE();
201                } catch (Exception e) {
202                    //e.printStackTrace();
203                    logger.info("GCDProxy e1 {}", e);
204                    logger.info("GCDProxy P = {}", P);
205                    logger.info("GCDProxy S = {}", S);
206                    throw new RuntimeException("GCDProxy e1 " + e);
207                    //return P.ring.getONE();
208                }
209            }
210        });
211        cs.add(new Callable<GenPolynomial<GenPolynomial<C>>>() {
212
213
214            public GenPolynomial<GenPolynomial<C>> call() {
215                try {
216                    GenPolynomial<GenPolynomial<C>> g = e2.recursiveUnivariateGcd(P, S);
217                    if (debug) {
218                        logger.info("GCDProxy done e2 {}", e2.getClass().getName());
219                    }
220                    return g;
221                } catch (PreemptingException e) {
222                    throw new RuntimeException("GCDProxy e2 pre " + e);
223                    //return P.ring.getONE();
224                } catch (Exception e) {
225                    //e.printStackTrace();
226                    logger.info("GCDProxy e2 {}", e);
227                    logger.info("GCDProxy P = {}", P);
228                    logger.info("GCDProxy S = {}", S);
229                    throw new RuntimeException("GCDProxy e2 " + e);
230                    //return P.ring.getONE();
231                }
232            }
233        });
234        try {
235            g = pool.invokeAny(cs);
236        } catch (InterruptedException ignored) {
237            logger.info("InterruptedException {}", ignored);
238            Thread.currentThread().interrupt();
239        } catch (ExecutionException e) {
240            logger.info("ExecutionException {}", e);
241            Thread.currentThread().interrupt();
242        }
243        return g;
244    }
245
246
247    /**
248     * GenPolynomial greatest common divisor. 
249     * @param P GenPolynomial.
250     * @param S GenPolynomial.
251     * @return gcd(P,S).
252     */
253    @Override
254    public GenPolynomial<C> gcd(final GenPolynomial<C> P, final GenPolynomial<C> S) {
255        if ( debug ) {
256            if ( ComputerThreads.NO_THREADS ) {
257                throw new RuntimeException("this should not happen");
258            }
259        }
260        if (S == null || S.isZERO()) {
261            return P;
262        }
263        if (P == null || P.isZERO()) {
264            return S;
265        }
266        // parallel case
267        GenPolynomial<C> g = null;
268        //Callable<GenPolynomial<C>> c0;
269        //Callable<GenPolynomial<C>> c1;
270        List<Callable<GenPolynomial<C>>> cs = new ArrayList<Callable<GenPolynomial<C>>>(2);
271        cs.add(new Callable<GenPolynomial<C>>() {
272
273
274            public GenPolynomial<C> call() {
275                try {
276                    //System.out.println("starting e1 " + e1.getClass().getName());
277                    GenPolynomial<C> g = e1.gcd(P, S);
278                    if (debug) {
279                        logger.info("GCDProxy done e1 {}", e1.getClass().getName());
280                    }
281                    return g;
282                } catch (PreemptingException e) {
283                    throw new RuntimeException("GCDProxy e1 pre " + e);
284                    //return P.ring.getONE();
285                } catch (Exception e) {
286                    //e.printStackTrace();
287                    logger.info("GCDProxy e1 {}", e);
288                    logger.info("GCDProxy P = {}", P);
289                    logger.info("GCDProxy S = {}", S);
290                    throw new RuntimeException("GCDProxy e1 " + e);
291                    //return P.ring.getONE();
292                }
293            }
294        });
295        cs.add(new Callable<GenPolynomial<C>>() {
296
297
298            public GenPolynomial<C> call() {
299                try {
300                    //System.out.println("starting e2 " + e2.getClass().getName());
301                    GenPolynomial<C> g = e2.gcd(P, S);
302                    if (debug) {
303                        logger.info("GCDProxy done e2 {}", e2.getClass().getName());
304                    }
305                    return g;
306                } catch (PreemptingException e) {
307                    throw new RuntimeException("GCDProxy e2 pre " + e);
308                    //return P.ring.getONE();
309                } catch (Exception e) {
310                    //e.printStackTrace();
311                    logger.info("GCDProxy e2 {}", e);
312                    logger.info("GCDProxy P = {}", P);
313                    logger.info("GCDProxy S = {}", S);
314                    throw new RuntimeException("GCDProxy e2 " + e);
315                    //return P.ring.getONE();
316                }
317            }
318        });
319        try {
320            g = pool.invokeAny(cs);
321        } catch (InterruptedException ignored) {
322            logger.info("InterruptedException {}", ignored);
323            Thread.currentThread().interrupt();
324        } catch (ExecutionException e) {
325            logger.info("ExecutionException {}", e);
326            Thread.currentThread().interrupt();
327        }
328        return g;
329    }
330
331
332    /**
333     * Univariate GenPolynomial resultant. 
334     * @param P univariate GenPolynomial.
335     * @param S univariate GenPolynomial.
336     * @return res(P,S).
337     */
338    @Override
339    public GenPolynomial<C> baseResultant(final GenPolynomial<C> P, final GenPolynomial<C> S) {
340        if ( debug ) {
341            if ( ComputerThreads.NO_THREADS ) {
342                throw new RuntimeException("this should not happen");
343            }
344        }
345        if (S == null || S.isZERO()) {
346            return S;
347        }
348        if (P == null || P.isZERO()) {
349            return P;
350        }
351        // parallel case
352        GenPolynomial<C> g = null;
353        //Callable<GenPolynomial<C>> c0;
354        //Callable<GenPolynomial<C>> c1;
355        List<Callable<GenPolynomial<C>>> cs = new ArrayList<Callable<GenPolynomial<C>>>(2);
356        cs.add(new Callable<GenPolynomial<C>>() {
357
358
359            public GenPolynomial<C> call() {
360                try {
361                    //System.out.println("starting e1 " + e1.getClass().getName());
362                    GenPolynomial<C> g = e1.baseResultant(P, S);
363                    if (debug) {
364                        logger.info("GCDProxy done e1 {}", e1.getClass().getName());
365                    }
366                    return g;
367                } catch (PreemptingException e) {
368                    throw new RuntimeException("GCDProxy e1 pre " + e);
369                    //return P.ring.getONE();
370                } catch (Exception e) {
371                    //e.printStackTrace();
372                    logger.info("GCDProxy e1 {}", e);
373                    logger.info("GCDProxy P = {}", P);
374                    logger.info("GCDProxy S = {}", S);
375                    throw new RuntimeException("GCDProxy e1 " + e);
376                    //return P.ring.getONE();
377                }
378            }
379        });
380        cs.add(new Callable<GenPolynomial<C>>() {
381
382
383            public GenPolynomial<C> call() {
384                try {
385                    //System.out.println("starting e2 " + e2.getClass().getName());
386                    GenPolynomial<C> g = e2.baseResultant(P, S);
387                    if (debug) {
388                        logger.info("GCDProxy done e2 {}", e2.getClass().getName());
389                    }
390                    return g;
391                } catch (PreemptingException e) {
392                    throw new RuntimeException("GCDProxy e2 pre " + e);
393                    //return P.ring.getONE();
394                } catch (Exception e) {
395                    //e.printStackTrace();
396                    logger.info("GCDProxy e2 {}", e);
397                    logger.info("GCDProxy P = {}", P);
398                    logger.info("GCDProxy S = {}", S);
399                    throw new RuntimeException("GCDProxy e2 " + e);
400                    //return P.ring.getONE();
401                }
402            }
403        });
404        try {
405            g = pool.invokeAny(cs);
406        } catch (InterruptedException ignored) {
407            logger.info("InterruptedException {}", ignored);
408            Thread.currentThread().interrupt();
409        } catch (ExecutionException e) {
410            logger.info("ExecutionException {}", e);
411            Thread.currentThread().interrupt();
412        }
413        return g;
414    }
415
416
417    /**
418     * Univariate GenPolynomial resultant. 
419     * @param P univariate recursive GenPolynomial.
420     * @param S univariate recursive GenPolynomial.
421     * @return res(P,S).
422     */
423    @Override
424    public GenPolynomial<GenPolynomial<C>> recursiveUnivariateResultant(final GenPolynomial<GenPolynomial<C>> P,
425            final GenPolynomial<GenPolynomial<C>> S) {
426        if ( debug ) {
427            if ( ComputerThreads.NO_THREADS ) {
428                throw new RuntimeException("this should not happen");
429            }
430        }
431        if (S == null || S.isZERO()) {
432            return S;
433        }
434        if (P == null || P.isZERO()) {
435            return P;
436        }
437        // parallel case
438        GenPolynomial<GenPolynomial<C>> g = null;
439        //Callable<GenPolynomial<GenPolynomial<C>>> c0;
440        //Callable<GenPolynomial<GenPolynomial<C>>> c1;
441        List<Callable<GenPolynomial<GenPolynomial<C>>>> cs = new ArrayList<Callable<GenPolynomial<GenPolynomial<C>>>>(
442                2);
443        cs.add(new Callable<GenPolynomial<GenPolynomial<C>>>() {
444
445
446            public GenPolynomial<GenPolynomial<C>> call() {
447                try {
448                    GenPolynomial<GenPolynomial<C>> g = e1.recursiveUnivariateResultant(P, S);
449                    if (debug) {
450                        logger.info("GCDProxy done e1 {}", e1.getClass().getName());
451                    }
452                    return g;
453                } catch (PreemptingException e) {
454                    throw new RuntimeException("GCDProxy e1 pre " + e);
455                    //return P.ring.getONE();
456                } catch (Exception e) {
457                    //e.printStackTrace();
458                    logger.info("GCDProxy e1 {}", e);
459                    logger.info("GCDProxy P = {}", P);
460                    logger.info("GCDProxy S = {}", S);
461                    throw new RuntimeException("GCDProxy e1 " + e);
462                    //return P.ring.getONE();
463                }
464            }
465        });
466        cs.add(new Callable<GenPolynomial<GenPolynomial<C>>>() {
467
468
469            public GenPolynomial<GenPolynomial<C>> call() {
470                try {
471                    GenPolynomial<GenPolynomial<C>> g = e2.recursiveUnivariateResultant(P, S);
472                    if (debug) {
473                        logger.info("GCDProxy done e2 {}", e2.getClass().getName());
474                    }
475                    return g;
476                } catch (PreemptingException e) {
477                    throw new RuntimeException("GCDProxy e2 pre " + e);
478                    //return P.ring.getONE();
479                } catch (Exception e) {
480                    //e.printStackTrace();
481                    logger.info("GCDProxy e2 {}", e);
482                    logger.info("GCDProxy P = {}", P);
483                    logger.info("GCDProxy S = {}", S);
484                    throw new RuntimeException("GCDProxy e2 " + e);
485                    //return P.ring.getONE();
486                }
487            }
488        });
489        try {
490            g = pool.invokeAny(cs);
491        } catch (InterruptedException ignored) {
492            logger.info("InterruptedException {}", ignored);
493            Thread.currentThread().interrupt();
494        } catch (ExecutionException e) {
495            logger.info("ExecutionException {}", e);
496            Thread.currentThread().interrupt();
497        }
498        return g;
499    }
500
501
502    /**
503     * GenPolynomial resultant. Main entry driver method.
504     * @param P GenPolynomial.
505     * @param S GenPolynomial.
506     * @return res(P,S).
507     */
508    @Override
509    public GenPolynomial<C> resultant(final GenPolynomial<C> P, final GenPolynomial<C> S) {
510        if ( debug ) {
511            if ( ComputerThreads.NO_THREADS ) {
512                throw new RuntimeException("this should not happen");
513            }
514        }
515        if (S == null || S.isZERO()) {
516            return S;
517        }
518        if (P == null || P.isZERO()) {
519            return P;
520        }
521        // parallel case
522        GenPolynomial<C> g = null;
523        //Callable<GenPolynomial<C>> c0;
524        //Callable<GenPolynomial<C>> c1;
525        List<Callable<GenPolynomial<C>>> cs = new ArrayList<Callable<GenPolynomial<C>>>(2);
526        cs.add(new Callable<GenPolynomial<C>>() {
527
528
529            public GenPolynomial<C> call() {
530                try {
531                    //System.out.println("starting e1 " + e1.getClass().getName());
532                    GenPolynomial<C> g = e1.resultant(P, S);
533                    if (debug) {
534                        logger.info("GCDProxy done e1 {}", e1.getClass().getName());
535                    }
536                    return g;
537                } catch (PreemptingException e) {
538                    throw new RuntimeException("GCDProxy e1 pre " + e);
539                    //return P.ring.getONE();
540                } catch (Exception e) {
541                    //e.printStackTrace();
542                    logger.info("GCDProxy e1 {}", e);
543                    logger.info("GCDProxy P = {}", P);
544                    logger.info("GCDProxy S = {}", S);
545                    throw new RuntimeException("GCDProxy e1 " + e);
546                    //return P.ring.getONE();
547                }
548            }
549        });
550        cs.add(new Callable<GenPolynomial<C>>() {
551
552
553            public GenPolynomial<C> call() {
554                try {
555                    //System.out.println("starting e2 " + e2.getClass().getName());
556                    GenPolynomial<C> g = e2.resultant(P, S);
557                    if (debug) {
558                        logger.info("GCDProxy done e2 {}", e2.getClass().getName());
559                    }
560                    return g;
561                } catch (PreemptingException e) {
562                    throw new RuntimeException("GCDProxy e2 pre " + e);
563                    //return P.ring.getONE();
564                } catch (Exception e) {
565                    //e.printStackTrace();
566                    logger.info("GCDProxy e2 {}", e);
567                    logger.info("GCDProxy P = {}", P);
568                    logger.info("GCDProxy S = {}", S);
569                    throw new RuntimeException("GCDProxy e2 " + e);
570                    //return P.ring.getONE();
571                }
572            }
573        });
574        try {
575            g = pool.invokeAny(cs);
576        } catch (InterruptedException ignored) {
577            logger.info("InterruptedException {}", ignored);
578            Thread.currentThread().interrupt();
579        } catch (ExecutionException e) {
580            logger.info("ExecutionException {}", e);
581            Thread.currentThread().interrupt();
582        }
583        return g;
584    }
585
586}