On Wed, Feb 29, 2012 at 07:04:48PM +0100, Waldek Hebisch wrote:
> 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].
For example, you write CommutativeRing R
and presume that it is algorithmic, and do not recall of
"also need an algorithm" for arithmetics.
Also Browse -- UniqueFactorizationDomain -- Categories shows:
"A constructive unique factorization domain. ...
can constructively factor members into ...
"
-- which means exactly AlgorithmicalUniqueFactorizationDomain.
This doc (and my DoCon too) removes the prefix Algorithmical (or Constructive)
in this case because
1) in practice, this is a rare case to have R : UniqueFactorizationDomain
which is not constructive,
2) it is better to solve dynamically, by extracting an attribute from a
domain, whether it has `Constructive'.
In the library, this question can be solved simply:
hasFactorizationAlgorithm R = true
means that `factor' is really a function representing a true factorization
in R, and in this case R has ConstructiveUniqueFactorizationDomain
(in this particular library).
hasFactorizationAlgorithm R just extracts the attribute value from the
domain description.
This is not sufficient to apply factor f, one needs to check
hasFactorizationAlgorithm R before this.
`false' means that `factor' may not present a correct factorization.
This all must be explained in doc,
also in the 'false' case, it may be set factor f = error "...",
for more safety.
For example, suppose Axiom has a correct factorOverInteger for
R = UP(x,INT). So, UP(x,INT) : UniqueFactorizationDomain,
and the HasFactorizationAlgorithm attribute is put true.
And in the implementation in this domain R it is put
factor(f : UP(x,INT)) == factorOverInteger f,
and this is the fastest kwnown special method to factor in UP(x,INT).
Then, one implements the method to factor UP over any
D : SuchAndSuchCleverRing,
and INT : SuchAndSuchCleverRing.
In the implementation for UP(x,D) it must be set
factor f == if D has IntegerLike then factorOverInteger f
else genericFactorUP(D, f)
General algorithms overlap with special ones, and a more special overrides.
And this must be expressed in the Spad code in the library.
And I expect that in Axiom it is arranged a similar approach, may be, by
some different means.
Has Axiom a category like AlgorithmicalUniqueFactorizationDomain ?
Is it PolynomialFactorizationExplicit ?
> 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.
I am aware of this.
And this should not reject the definition of UniqueFactorizationDomain given
in Browse (see above) -- for the reasons I write above.
> 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.
Lenstra, Grigoriev, Gianni, Davenport, Trinks, and others (and some of them
even wrote a code for Axiom), developed the methods and algorithms
(not necesssarily programs) which, in particular, describe a wide class of
commutative rings R for which it is built a correct factorization algorithm
in R[x1..xn]. I know of this for a long time.
I expect that the Axiom library somehow follows the main stream of this whole
theory.
> 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.
??
The method of resovling an overlap of a special algorithm and a general one
may be, for example, as I describe above.
Axiom may apply a different method of resolving, but I believe that the
Spad language is expressive enough to have a good resolution method for this.
Why cannot Axiom arrange this clearly?
> > 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).
I do not understand why Axiom cannot efficiently resolve this overlap.
Probably, it can, but I cannot find the decription of this dispatch method.
Currently, I even do not need to observe it. It is only desirable to have a
clear rule for an user of how to choose the most efficient `factor'
implementation.
Example: for determinant of a SquareMatrix over rR, DoCon has
(1) det for CommutativeRing rR => SquareMatrix rR,
(2) det_euc for Euclidean rR => SquareMatrix rR,
(3) det_upol_finField ::
Field k => [ResidueE (UPol k)] -> [[UPol k]] -> UPol k
-- ext mM
-- A degree cost method to compute det M over k[x] for a finite
-- field k.
On average, (2) is faster than (1), (3) is faster than (2).
DoCon provides three different functions, for some reasons.
If it introduced class WithDet, may be, it could have a unique operation
`det', whose instances are efficienly resolved for these three functions
(I am not sure, needs recollection, trying).
But the Spad language is more expressive, and it is likely to have an easier
resolution.
Regards,
------
Sergei
[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.
