[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Axiom-developer] Bug in GeneralizedMultivariateFactorize?
From: |
William Sit |
Subject: |
Re: [Axiom-developer] Bug in GeneralizedMultivariateFactorize? |
Date: |
Fri, 20 Jul 2007 12:21:40 -0400 |
Waldek Hebisch wrote:
> Well, if you look just at types factor can return anything. However,
> we have:
>
> factor : P -> Factored P
> ++ factor(p) factors the multivariate polynomial p over its coefficient
> ++ domain
> The ++ comment does not mention possibility of unfactored output. Other factor
> functions give completly factored output, so giving unfactored output is
> inconsistent with other functions.
It did not say "completely factors into irreducibles" but it does not preclude
it
either (but that is quibbling :-).
> Given that there are functions like subtractIfCan it is natural that function
> which
> factorizes on "best effort" basis should have different name.
Following that logic, we should also have integrateIfCan, solveIfCan, and lots
of
other IfCan's so that there would be no need for errors messages (like addIfCan
on
vectors instead of signalling error when the summands have different
dimensions).
There has to be some freedom in the way errors or incomplete solutions are
handled.
Given a choice, I would prefer to signal an error at run time instead of using
IfCan's
and asks the compiler to verify the right branch. IfCan requires
Union("failed", ...)
as its target domain, leading to unnecessary overhead. Union("failed", ...)
would be
useful if it is possible to handle the "failed" case, but then there would be
no need
for error signalling anyway.
> Mathematically, to have well-defined (unique) factorizations we need
> something like Krull ring. But Krull ring such that gcd exists for
> all pairs of elements is a unique factorisation domain. I suspect
> that similar things holds for square free decomposition.
>
> Practically, when working with polynomils we may want to ignore
> problems due to coefficient ring, that is consider degree 0 factors
> as trivial. But it is still not clear if we can do square free
> decomposition (without for example extending coefficient ring to a
> field). However, assuming that we can compute such a decomposition
> it would be a different operation than the normal square free
> decomposition, so I feel that it deserves different name.
In that case, the domanis Factored R should also be restricted to hold only
completely
factored forms. You will then need new names for all the intermediately factored
forms.
> Similarly, it may happen that some elements of a ring which is
> not a unique factorisation domain happen to have unique factorisation.
> Again, a operation which factors elements which are factorizable
> and returns other unfactored is IMHO a different operation than
> Axiom factor function.
In the case a domain does not have UFD, if we use factorIfCan, we would be hard
pressed to come up with a general algorithm that can detect which elements can
be
factored uniquely. The complexity is much higher than subtractIfCan. Is this
even
decidable? What domain would have such an algorithm?
William