I am thinking what to do with PolynomialFactorizationExplicit.
To remaind you, there is a theory how to propagate factorization
of polynomials trough towers build of algebraic extensions,
ring polynomials and fractions. This code is in "almost work"
state. To activate it one needs to add PolynomialFactorizationExplicit
to Integer and to FiniteFieldCategory. With current trunk this
causes failures for finite fields, which can be fixed by
redirecting gcd-s and factorization over finite fields to old
code. After that testsuite runs OK, however there is substantial
perfomance loss for factorization. AFAICS it should be possible
to regain speed by redirecting affected calls to old code.
So, it should be possible to activate PolynomialFactorizationExplicit
whithout introducing regression (correctenss of speed) in test suite.
OTOH looking at the code I noticed that the code is incorrect.
Namely, factorization of say bivariate polynomial P[x, y] is
done by evaluating one variable, for example y at some random
point a, obtaining P_a[x] = P[x, a] which is now polynomial
in one variable. We factor P_a via recursive call obtaining
factorization:
P_a = Q_1Q_2...Q_n
and use Hensel lifting to obtain (approximate) a-adic factorization
P = R_1R_2...R_n
Now, in many cases R_i give true bivariate factors of P. But
in some cases we need to multiply several R_i to get factor
of P (this is so called factor recombination). Code supporting
PolynomialFactorizationExplicit apparently assumes that
factor recombination will be never needed. This is OK for
bivariate polynomials over integers, because we know that
for a randomly taken from sufficiently large set with high
probablity there will be one to one correspondence between
factors of P and factors of P_a. But if base ring is an
algebraically closed field, then P_a will allways split into
linear factors, while P may have interesting factorization
(for example it may be irreducible). I am not sure if we
can now build charactristic zero ring for which this assumption
fails, but if finite characteristic coefficients may come
from finite field so there is no obvios way to avoid
the problem. Another problem is that we need
random evaluation points. Generically all we can get
are images of random integers, which in finite characteritic
may be a very small set, and it may be impossible to find
good evaluation point. For finite fields solution is to
perform computations over extension field (and to old code is
doing just that). But if ring is infinite there is plenty
of evaluation points, we just have no way to find them...
Problem with evaluation points could be solved in
practice by propagating trough type tower 'random'
with following description:
random : NonNegativeInteger -> Union(%, "failed")
++ random(n) picks random element from some subset
++ of cardianlity n or "failed" if % has
++ cardinality smaller than n
Alternatively, we could drop "failed" case and instead
define it only for infinite domains.
I am not sure how problematic is lack of recombination
in characteristic 0. Theoretically we could add
factor recombination to existing code, but it would
lead to substantial complication and probably significant
loss of efficiency.
Concerning efficency, base approach of code behind
PolynomialFactorizationExplicit is Hensel listing,
which is reasonably efficient. But "black box"
approach to base ring has substantial cost. For
example, calculations with fractions lead to recursive
gcd computations which may be more expensive than
original factorization with better approach. If
we have algebraic extension close to top of tower,
than PolynomialFactorizationExplicit likes to
compute norm of the polynomial to be factored,
which may be quite large. OTOH applying modular
reduction to original polynomial means that
norm will be applied to modular image, which
typically is much cheaper.
I consider alternative approach: if F is algebraic
extension of field or rational functions, then
existing (non PFECAT) code can factor polynomials
over R. Efficiency of current code is suboptimal
(but almost surely better than of PFECAT code),
but can be improved using known methods. Now,
general finitely generated field is isomorphic to
field like F. So instead of PFECAT we could
introduce another property, say AlgebraicallyExplicitRingOver(S),
meaning that for any finite subset {ai} aof our ring R we can
find explicit finitely generated field F (that is set of
variables and polynomials giving algebraic relations)
such that ring generated by {ai} and S is isomorhic to
subring of F generated by images of {ai} and S.
This in in analogy to LinearlyExplicitRingOver(S): here
for finite subset {ai} we can find free module M such that
submodule of R over S generated by {ai} is isomorphic
to submodule of M generated by images of {ai}. There
is a small subtelty here: in linear case definitin via
submodule isomorphism is equvalent to definiton in terms of
solvability of linear equations (given in documentation).
In algebraic case solvability of equations would need
king of algebraic closure, which for constrictors we
support seems easy, but in general looks harder than
problem of computing subrings.
Anyway, once w can compute F isomorphic to quotient field of
algebraic closure in quotient field of R of subfield of
quotient field of R generated by {ai}, problem of factoring
polynomials over R with coefficients {ai} is reducend to
problem of factoring over F.
Comparing the two approaches let me note that "black box"
approach taken by PFECAT has some appeal.
AlgebraicallyExplicitRingOver essentially means
"you can use any representation, as long as it is
convertible to standard representation". OTOH
standard representation is based on deep mathematical
properties and it seems that to have those properties
is essentially equivalent to beeing able to convert.
Also, neither approach gracefuly handles things like
algebraic closure. Actually in case of algebraic closure
good approach probably would use absolute factorization
(say Gao method) for bivariate polynomials, which typically
produces univariate polynomial of much lower degree than
evaluation.
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
