Interface Summary Interface Description Factorization<C extends GcdRingElem<C>> Factorization algorithms interface.GreatestCommonDivisor<C extends GcdRingElem<C>> Greatest common divisor algorithm interface.Squarefree<C extends GcdRingElem<C>> Squarefree decomposition interface.Class Summary Class Description Examples Examples for ufd and elementaty integration usage.ExamplesPartialFraction Examples related to partial fraction decomposition.FactorAbsolute<C extends GcdRingElem<C>> Absolute factorization algorithms class.FactorAbstract<C extends GcdRingElem<C>> Abstract factorization algorithms class.FactorAlgebraic<C extends GcdRingElem<C>> Algebraic number coefficients factorization algorithms.FactorComplex<C extends GcdRingElem<C>> Complex coefficients factorization algorithms.FactorFactory Factorization algorithms factory.FactorInteger<MOD extends GcdRingElem<MOD> & Modular> FactorModular<MOD extends GcdRingElem<MOD> & Modular> Modular coefficients factorization algorithms.FactorQuotient<C extends GcdRingElem<C>> Rational function coefficients factorization algorithms.FactorRational Rational number coefficients factorization algorithms.Factors<C extends GcdRingElem<C>> Container for the factors of absolute factorization.FactorsList<C extends GcdRingElem<C>> Container for the factors of a squarefree factorization.FactorsMap<C extends GcdRingElem<C>> Container for the factors of a eventually non-squarefree factorization.GCDFactory Greatest common divisor algorithms factory.GCDProxy<C extends GcdRingElem<C>> Greatest common divisor parallel proxy.GreatestCommonDivisorAbstract<C extends GcdRingElem<C>> Greatest common divisor algorithms.GreatestCommonDivisorHensel<MOD extends GcdRingElem<MOD> & Modular> Greatest common divisor algorithms with subresultant polynomial remainder sequence and univariate Hensel lifting.GreatestCommonDivisorModEval<MOD extends GcdRingElem<MOD> & Modular> Greatest common divisor algorithms with modular evaluation algorithm for recursion.GreatestCommonDivisorModular<MOD extends GcdRingElem<MOD> & Modular> Greatest common divisor algorithms with modular computation and chinese remainder algorithm.GreatestCommonDivisorPrimitive<C extends GcdRingElem<C>> Greatest common divisor algorithms with primitive polynomial remainder sequence.GreatestCommonDivisorSimple<C extends GcdRingElem<C>> Greatest common divisor algorithms with monic polynomial remainder sequence.GreatestCommonDivisorSubres<C extends GcdRingElem<C>> Greatest common divisor algorithms with subresultant polynomial remainder sequence.HenselApprox<MOD extends GcdRingElem<MOD> & Modular> Container for the approximation result from a Hensel algorithm.HenselMultUtil Hensel multivariate lifting utilities.HenselUtil Hensel utilities for ufd.PartialFraction<C extends GcdRingElem<C>> Container for the partial fraction decomposition of a squarefree denominator.PolyUfdUtil Polynomial ufd utilities, like conversion between different representations and Hensel lifting.Quotient<C extends GcdRingElem<C>> Quotient, that is a rational function, based on GenPolynomial with RingElem interface.QuotientRing<C extends GcdRingElem<C>> Quotient ring factory based on GenPolynomial with RingElem interface.SquarefreeAbstract<C extends GcdRingElem<C>> Abstract squarefree decomposition class.SquarefreeFactory Squarefree factorization algorithms factory.SquarefreeFieldChar0<C extends GcdRingElem<C>> Squarefree decomposition for coefficient fields of characteristic 0.SquarefreeFieldCharP<C extends GcdRingElem<C>> Squarefree decomposition for coefficient fields of characteristic p.SquarefreeFiniteFieldCharP<C extends GcdRingElem<C>> Squarefree decomposition for finite coefficient fields of characteristic p.SquarefreeInfiniteAlgebraicFieldCharP<C extends GcdRingElem<C>> Squarefree decomposition for algebraic extensions of infinite coefficient fields of characteristic p > 0.SquarefreeInfiniteFieldCharP<C extends GcdRingElem<C>> Squarefree decomposition for infinite coefficient fields of characteristic p.SquarefreeRingChar0<C extends GcdRingElem<C>> Squarefree decomposition for coefficient rings of characteristic 0.Exception Summary Exception Description NoLiftingException Non existing Hensel lifting.

## Package edu.jas.ufd Description

# Unique factorization domain package.

This package contains classes for polynomials rings as unique factorization domains. Provided methods with interface `GreatestCommonDivisor`

are e.g. greatest common divisors `gcd()`

, primitive part `primitivePart()`

or `coPrime()`

. The different classes implement variants of polynomial remainder sequences (PRS) and modular methods. Interface `Squarefree`

provides the greatest squarefree factor `squarefreeFactor()`

and a complete squarefree decompostion can be obtained with method `squarefreeFactors()`

. There is a `Factorization`

interface with an `FactorAbstract`

class with common codes. Factorization of univariate polynomials exists for several coefficient rings: modulo primes in class `FactorModular`

, over integers in class `FactorInteger`

, over rational numbers in class `FactorRational`

, over algebraic numbers in class `FactorAlgebraic<C>`

and over rational functions in class `FactorQuotient<C>`

(where for the last two classes `C`

can be any other ring for which the `FactorFactory. getImplementation`

returns an implementation). Multivatiate polynomials over the integers (and rational numbers) are factored using the algorithm of P. Wang. For other coeffcients the multivatiate polynomials are reduced to univariate polynomials via Kronecker substitution. The rational function class `Quotient`

computes quotients of polynomials reduced to lowest terms.

To choose the correct implementation always use the factory classes `GCDFactory`

, `SquarefreeFactory`

and `FactorFactory`

with methods `getImplementation()`

or `getProxy()`

. These methods will take care of all possible (implemented) coefficient rings properties. The polynomial coefficients must implement the `GcdRingElem`

interface and so must allow greatest common divisor computations. Greatest common divisor computation is completely generic and works for any implemented integral domain. If special, optimized implementations exist they will be used. Squarefree decomposition is also completely generic and works for any implemented integral domain. There are no special, optimized implementations. Factorization is generic relative to the implemented ring constructions: algebraic field extensions and transcendent field extensions. Implemented base cases are modular coefficient, integer coefficients and rational number coefficients.

The implementation follows Geddes & Czapor & Labahn *Algorithms for Computer Algebra* and Cohen *A Curse in Computational Algebraic Number Theory*. See also Kaltofen *Factorization of Polynomials* in Computing Supplement, *Springer, 1982*, Davenport & Gianni & Trager *Scratchpad's View of Algebra II: A Categorical View of Factorization* in *ISSAC'91* and the ALDES/SAC2 code as contained in MAS.

Heinz Kredel

Last modified: Fri Sep 21 21:56:48 CEST 2012

$Id$

**SCaVis 2.1 © jWork.ORG**