Package edu.jas.ufd

Unique factorization domain package.

See:
Description

Interface Summary

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

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.
FactorAlgebraicTest	Factor algebraic tests with JUnit.
FactorComplex<C extends GcdRingElem<C>>	Complex coefficients factorization algorithms.
FactorComplexTest	Factor complex via algebraic tests with JUnit.
FactorFactory	Factorization algorithms factory.
FactorGenericTest	Factor rational tests with JUnit.
FactorInteger<MOD extends GcdRingElem<MOD> & Modular>
FactorIntegerTest	Factor tests with JUnit.
FactorModular<MOD extends GcdRingElem<MOD> & Modular>	Modular coefficients factorization algorithms.
FactorModularTest	Factor modular tests with JUnit.
FactorMoreTest	Factor tests with JUnit.
FactorQuotient<C extends GcdRingElem<C>>	Rational function coefficients factorization algorithms.
FactorQuotientTest	Factor quotient tests with JUnit.
FactorRational	Rational number coefficients factorization algorithms.
FactorRationalTest	Factor rational tests with JUnit.
FactorRealAlgebraic<C extends GcdRingElem<C> & Rational>	Real algebraic number coefficients factorization algorithms.
FactorRealAlgebraicTest	Factor real algebraic tests with JUnit.
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.
FactorTest	Factor tests with JUnit.
GCDFactory	Greatest common divisor algorithms factory.
GCDFactoryTest	GreatestCommonDivisor factory tests with JUnit.
GCDHenselTest	GCD Hensel algorithm tests with JUnit.
GCDModEvalTest	GCD Modular Evaluation algorithm tests with JUnit.
GCDModLongEvalTest	GCD Modular Evaluation algorithm tests with JUnit.
GCDModLongTest	GCD Modular algorithm tests with JUnit.
GCDModularTest	GCD Modular algorithm tests with JUnit.
GCDPartFracRatTest	GCD partial fraction with rational coefficients algorithm tests with JUnit.
GCDPrimitiveTest	GCD Primitive PRS algorithm tests with JUnit.
GCDProxy<C extends GcdRingElem<C>>	Greatest common divisor parallel proxy.
GCDProxyTest	GreatestCommonDivisor proxy tests with JUnit.
GCDSimpleTest	GCD Simple PRS algorithm tests with JUnit.
GCDSubresRatTest	GCD Subres with rational coefficients algorithm tests with JUnit.
GCDSubresTest	GCD Subresultant PRS algorithm tests with JUnit.
GCDTimingTest	GreatestCommonDivisor timing tests with JUnit.
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.
HenselMultUtilTest	HenselMultUtil tests with JUnit.
HenselUtil	Hensel utilities for ufd.
HenselUtilTest	HenselUtil tests with JUnit.
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.
PolyUfdUtilTest	PolyUfdUtil tests with JUnit.
Quotient<C extends GcdRingElem<C>>	Quotient, i.e. rational function, based on GenPolynomial with RingElem interface.
QuotientIntTest	Quotient over BigInteger GenPolynomial tests with JUnit.
QuotientRatTest	Quotient over BigRational GenPolynomial tests with JUnit.
QuotientRing<C extends GcdRingElem<C>>	Quotient ring factory based on GenPolynomial with RingElem interface.
QuotIntPolynomialTest	Quotient BigInteger coefficient GenPolynomial tests with JUnit.
SquarefreeAbstract<C extends GcdRingElem<C>>	Abstract squarefree decomposition class.
SquarefreeAlgModTest	Squarefree factorization tests with JUnit.
SquarefreeAlgQuotModTest	Squarefree factorization tests with JUnit.
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.
SquarefreeIntTest	Squarefree factorization tests with JUnit.
SquarefreeModLongTest	Squarefree factorization tests with JUnit.
SquarefreeModTest	Squarefree factorization tests with JUnit.
SquarefreeQuotModTest	Squarefree factorization tests with JUnit.
SquarefreeRatTest	Squarefree factorization tests with JUnit.
SquarefreeRingChar0<C extends GcdRingElem<C>>	Squarefree decomposition for coefficient rings of characteristic 0.
SquarefreeTest	Squarefree Factory tests with JUnit.

Exception Summary

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 are reduced to the univariate polynomials via Kronecker substitution and are therefore not very efficient at the moment. The factorization of polynomials is partly experimental. 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: Sat Oct 23 18:55:42 CEST 2010

$Id: package.html 3357 2010-10-23 17:10:02Z kredel $