Source code

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