shouldn't UTS(F, x, 0) export EuclideanDomain if F is a Field?

[Martin R]

Dear all!

the question fits into the title :-)

Martin

[Martin R]

Below is a patch...

diff --git a/src/algebra/pscat.spad b/src/algebra/pscat.spad

index 01ffdb1c..ca7dc970 100644

--- a/src/algebra/pscat.spad

+++ b/src/algebra/pscat.spad

@@ -197,6 +197,7 @@ UnivariateTaylorSeriesCategory(Coef) : Category == Definition where

         ++ When the coefficient ring is a field, we may raise a series

         ++ to an exponent from the coefficient ring provided that the

         ++ constant coefficient of the series is 1.

+      EuclideanDomain

 

     if Coef has Algebra Fraction Integer then

       integrate : % -> %

@@ -287,6 +288,21 @@ UnivariateTaylorSeriesCategory(Coef) : Category == Definition where

     if Coef has Field then

       (x : %) ^ (r : Coef) == series power(r, coefficients x)$STTA

 

+      euclideanSize f == order f

+

+      divide(f, g) ==

+          k := order g

+         if zero? k then

+              g1 := recip g

+              g1 case "failed" => error "this should not happen"

+             return [f*g1, 0]

+

+          r := truncate(f, (k-1)::NNI)

+         f1 := f - r

+          q := f1 exquo g

+          q case "failed" => error "this should not happen"

+          [q, r]

+

     if Coef has Algebra Fraction Integer then

       if Coef has CommutativeRing then

         (x : %) ^ (y : %)    == series(coefficients x ^$STTF coefficients y)

[Waldek Hebisch]

Martin R wrote:
>
> Dear all!
>
> the question fits into the title :-)
>

Does not fit: it is truncated by many viewers. Fixed:

> shouldn't UTS(F, x, 0) export EuclideanDomain if F is
> a Field?

That is a tricky question. I see that you gave an
implementation, but there is a core problem:
EuclideanDomain implies BasicType and this already
is a lie. That is equality for power series is
noncomputable. Which means that generic algorithms
may have very poor performance or fail. To explain
it better, consider Gaussian elimination applied
to invertible matrix of power series. Generic algorithm
will struggle trying to find out if an element is suitable
pivot. Algorithm aware of power series will try increasing orders
and checking all elements of a column for given order.
In this way it will find pivot of best order, without
wasting time examining many entries of zero or nearly
zero series.

So question is if after lying several times we want
to keep lying, or if we want to clean up things.
Pragmatically lying may look attractive as it gives
immediate rewards, while punishment is delayed.
OTOH most had to fix bugs comes from original developers
ignoring problems and opting for immediate "progress".

--
Waldek Hebisch

[Martin R]

thanks for the explanation, and yes, I agree that there is a problem - I have no good idea to fix it, though.  In fact, looking at my code with this in mind, it looks particularly stupid: already the first call to "order" should be avoided, I should simply check whether g has a constant term.

After that, we are probably out of luck, because, as you said, recognising the zero power series is not possible.

On the other hand, if g is zero, calling code should not expect divide to succeed anyway.

I admit I am rather on the "immediate progress" side

Martin

[Ralf Hemmecke]

>> shouldn't UTS(F, x, 0) export EuclideanDomain if F is
>> a Field?

At first I thought, how can we have a Euclidean algorithm without zero
detection? But then ... that's not the definition of a Euclidean domain.
All it needs is a Euclidean size function and a division step. As long
as divide(f, g) does not get (potential) zeros as input, that looks like
a computable problem to me.

Anyway, I still think it's potentially more dangerous than its gain.

> EuclideanDomain implies BasicType and this already
> is a lie.

Oh, now we enter a very dangerous field. In fact, currently UTS claims
BasicType. UTS itself already lies. We have probably lies all over the
place.

> So question is if after lying several times we want
> to keep lying, or if we want to clean up things.

Since long I am in favour of removing our lies. When we say Ring, we
actually mean a computable ring. So power series cannot claim to be of
category Ring. AFAIR, the aldor library tried something in the direction
of relaxing things. There are categories like

AdditiveType, LinearCombinationType, etc.

https://github.com/pippijn/aldor/blob/master/aldor/lib/aldor/src/arith/sal_arith.as

https://github.com/pippijn/aldor/blob/master/aldor/lib/aldor/src/arith/sal_lincomb.as

that just claim existence of operations, but without the respective
properties.

Yes, that makes the category structure a whole lot more complex.
However, I guess when we can come up with a nice naming convention such
a change should be doable and should be done. Clearly this will not
happen overnight, but that should be a longterm goal for FriCAS.

Ralf

[Martin R]

Hi Ralf!

Anyway, I still think it's potentially more dangerous than its gain. 

Well, I must say that I believe that this is one of the reasons why sage now excels: to be useful, it is much better to solve a few instances of a problem, instead of giving up because one cannot solve the problem completely.  Instead, it is much better to have something partially working, and warn the user of possible problems.

Concerning the original question: it might in fact be the case that fricas would be the only system capable of computing Smith normal forms of matrices with entries being power series out of the box.  I am not sure whether that's useful, though.

(sage has power series, but they pale in comparison)

Martin

[Ralf Hemmecke]

> Instead, it is much better to have something partially working, and
> warn the user of possible problems.

I understand. Obviously there are some differences in development
between Sage and FriCAS. Correct me if I am wrong, but in my opinion,
Sage looks more like a moving target. It might easily happen that user
code that once worked, will not run as expected in a future version of
Sage. I must say that I appreciate Waldek's insistence on not changing
too drastically. Yes that slows things down, but it also does not easily
break a somewhat working FriCAS.

On the other hand, you want things to work now. In that sense FriCAS is
not serving its users well. (Unfortunately, we don't even know how many
users FriCAS actually has.)

> Concerning the original question: it might in fact be the case that
> fricas would be the only system capable of computing Smith normal
> forms of matrices with entries being power series out of the box.

Well, fortunately, you can change FriCAS yourself and easily recompile
the respective .spad files in order to make UTS a EuclideanDomain and
have the computation that you would like to run working for you (and
your scientific article) even though it is not part of the official FriCAS.

I know that not everyone feels comfortable with recompiling FriCAS, but
at least a user has the potential to solve his own problems himself
without waiting for the developers (or a company) to solve them for him.

Ralf

[Martin R]

I understand. Obviously there are some differences in development
between Sage and FriCAS. Correct me if I am wrong, but in my opinion,
Sage looks more like a moving target. It might easily happen that user
code that once worked, will not run as expected in a future version of
Sage.

Well, this is bound to happen already if you want to fix bugs :-)

For all user visible changes in behaviour, there is a (roughly) one year

deprecation period.  You will get a printed warning along with a workaround

and a pointer to the discussion if you use a feature that is about to change.

Concerning the original questiion: I admit that I doubt that my addition is

very useful.

Best wishes,

Martin

[Waldek Hebisch]

Martin R wrote:
>
>
> Well, I must say that I believe that this is one of the reasons why sage
> now excels: to be useful, it is much better to solve a few instances of a
> problem, instead of giving up because one cannot solve the problem
> completely. Instead, it is much better to have something partially
> working, and warn the user of possible problems.

Well, I have no problems with isolated piece of code that is imperfect
but is doing something useful. However, fact that types guarantee
that we can perform operations (or at least we get an error when
we can not do them) is quite fundamental for FriCAS. I am pretty
sure that if you proposed change to some fundamental thing Sage
folks would want very strong reason. On technical grounds, FriCAS
was able to do several deep changes because of type safety,
otherwise such changes would be too risky. And we still have
trouble fixing known problem in cases when safety/conventions
were violated (mostly in Boot code and in interaction between
Spad and interpreter).

Let me add that EuclideanDomain is a nice example of things
going wrong: probably more than half of uses in original code
were bugs. Several such buggy uses are now removed but I still
work on removing some other...

> Concerning the original question: it might in fact be the case that fricas
> would be the only system capable of computing Smith normal forms of
> matrices with entries being power series out of the box. I am not sure
> whether that's useful, though.

Well, that should work on easy examples. But already Gaussian
elimination have trouble in heavier cases. I would expect
Smith form to behave much worse.

--
Waldek Hebisch

[Martin R]

Let me add that EuclideanDomain is a nice example of things
going wrong: probably more than half of uses in original code
were bugs.  Several such buggy uses are now removed but I still
work on removing some other...

I'd be very interested in a concrete example!

Sage's approach to safety is in my opinion quite instructive:

on the one hand very heavy use of doctests (using a surprisingly

simple framework), on the other hand generic code using ideas

building on the category-domain scheme of FriCAS', but also

using categorical constructions closer to mathematics.

(I am not advocating for making UTS an EUCDOM)

Martin

[Waldek Hebisch]

Martin R wrote:
>
> >
> > Let me add that EuclideanDomain is a nice example of things
> > going wrong: probably more than half of uses in original code
> > were bugs. Several such buggy uses are now removed but I still
> > work on removing some other...
> >
>
> I'd be very interested in a concrete example!

Well, in ComplexCategory asserting EuclideanDomain is a lie (true
only in very special cases). Uses in multfact.spad and multsqr.spad
are mostly bogus (code should be written in way that works without
using functions from EuclideanDomain). For removed cases see past
diffs. In particular EuclideanDomain was uses in many places
where PolynomialFactorizationExplicit should be used.

--
Waldek Hebisch

[Martin R]

Well, in ComplexCategory asserting EuclideanDomain is a lie (true
only in very special cases).

OK, thanks!  (although I'm unable to come up with an example, it does

seem like it's too much too hope for - do you have an example?)

Many thanks,

Martin