Serge D. Mechveliani wrote:
>
> On Tue, Feb 28, 2012 at 10:10:24PM +0100, Ralf Hemmecke wrote:
> > On 02/28/2012 06:24 PM, Serge D. Mechveliani wrote:
> >> For f := (x^2 - 1) :: UP(x,INT)
> >>
> >> factor f
> >> yields
> >> (12) (x - 1)(x + 1)
> >> Type: Factored(UnivariatePolynomial(x,Integer)),
> >>
> >> and prime?(f) $UP(x,INT)
> >
> > That's funny. HyperDoc (and the code) says that factor only exists if
> > the coefficient domain has PolynomialFactorizationExplicit. One can
> > easily check that *no* domain in FriCAS exports this category
> > unconditionally. Strange that FriCAS finds a factorization routine at
> > all.
>
> This is somow against classical algorithmic algebra.
> 1) Classical algebra says that
> Z[x] is an unique factorization domain with an algorithmic factorization.
> 2) Axiom announces that it has polynomial factorization, over Integer too.
> 3) UniqueFactorizationDomain has `factor' and `prime?' among its operations.
Actually situation is more tricky than you think: it is not enough
to know that Z[x] is an unique factorization domain, but you
also need an algorithm to factorize in Z[x]. Typicaly Axiom/Fricas
builds algorithm in Z[x] using algorithm in Z as building block
(where Z now stands for arbitrary Ring). However, IIRC there is
a theorem that essentially says that it is impossible to build
factorization algorithm in R[x] just from arithmetic operations
and factorization algorithm in R. This is quite different then
say gcd, where fraction free version of Euclidean algorithm
uses only arithmetic in R and together with gcd in R is enough
to get gcd in R[x]. So you need more than unique factorization
domain to have factorization. Theoretically Axiom developers
solved the problem -- they invented stronger property namely
PolynomialFactorizationExplicit which correctly propagetes trough
towers of extensions. And they wrote code to handle it.
So, why we do not use this code? The problem is performance,
in cases handled by current code the general code is a lot
slower.
So, currently we have code which handles several special
cases. Mathematically those cases cover the same area
as "general" code. The difference is that currently
factor function has to solve problem similar to what you
(Sergei) is doing in Haskell interface: analyze type and
dispatch to correct factorization routine. This dispatch
only works for some types and some which could work are
not handled.
> Hence it is natural for Axiom to provide `factor' and `prime?' for Z[x]
> for all its representations given in Axiom for UP, SUP, POLY, etc.
> Because as it is done for POLY(..INT..), it is easy to spread them also
> to UP(x,INT) too.
> Probably, it does this, but it is difficult to find.
Orignal Axiom developers wanted to treat 'factor' and `prime?' via
PolynomialFactorizationExplicit. But this is not practical
for performance reasons. For specifice domains, like Z[x] we
could solve the problem in ad hoc manner. But I am not sure
if possible gain is worth the effort: interpreter finds 'factor'
when needed and in Spad one freqently uses more general domains
and need to call factor from appropriate package (possibly
converting polynomial to supported type).
>
> > Looking at MULTFACT reveals that this only applies to very special
> > situation.
> > [..]
> > ==============================================================
> > MultivariateFactorize(OV,E,R,P) : C == T
> > where
> > R : Join(EuclideanDomain, CharacteristicZero)
> > -- with factor on R[x]
> > OV : OrderedSet
> > E : OrderedAbelianMonoidSup
> > P : PolynomialCategory(R,E,OV)
> >
> > [..]
>
>
> Thank you.
> This looks like some hint.
> But to tell it simply: how to factor in UP(x,INT) ?
<snip>
> I suspect that there exists a simple way for this in Spad.
> I am looking into
> "Browse -- factor -- Operations -- Origins"
>
> (in the same time as e-mailing this question)
> and trying to choose ...
> May be, GenUFactorize(INT)
> fits?
> I try in Spad:
> f() : Factored SUP ==
> X := monomial(1 ::INT, 1 ::NNI) $UPol
> y := X pretend SUP
> f := (4*y^2 - 1) :: SUP
> factor(f) $GenUFactorize(INT)
> It works!
> Is this a reasonable approach?
Yes. For factorization over integers the actual factor routine
is in 'UnivatiateFactorize'. GenUFactorize analyses its argument
and dispatches to UnivatiateFactorize or another specific
package.
> And what about `prime?' ? We need to search a package ...
Sorry, unimplemented. But implementation is trival: first
use 'factor' and then check the result for a non-trivial
factors.
> Generally, it is very difficult to find the needed package and also
> often difficult to put a correct parameter values.
>
> May be, there is possible import AllFactorization
> ?
> (in order to apply `factor' without specification,
> and let the compiler give a warning:
> such and such variants for `factor' fit this particular piece of code).
>
> And there is something strange in this total necessity for the user to
> search cleverly among tons of packages.
> The compiler knows itself that SUP INT has UniqueFactorizationDomain,
> and that `factor' and `prime?' are operations from
> UniqueFactorizationDomain.
No. Currently SUP INT does not have UniqueFactorizationDomain.
And we can not make it into UniqueFactorizationDomain without
adding factor to it, because then interpreter would ignore
factor from factorization packages and try to use factor from
UniqueFactorizationDomain (and fail calling non-existent function).
And I wrote, for Integer it would be small amount of work to
add a special case. But then we probably would like to handle
Fraction(Integer) and then tons of other cases. So simple
special casing does not scale.
I know that current situation with 'factor' is not nice and
I am working on solution. But I believe that we need general
solution (like PolynomialFactorizationExplicit, but without
performance problems) not patching to handle few special
cases. General solution takes time to develop, and as long
as it is not finished it does not work at all.
--
Waldek Hebisch
[email protected]
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
