oldk1331 wrote:
>
> I was looking at polynomial remainder sequence related parts
> of FriCAS, and I find there are some improvement space.
>
> I'll use PRS for "polynomial remainder sequence", not to be
> confused with package PseudoRemainderSequence.
>
> 1. PRS parts in FriCAS:
> package PRS in prs.spad by Ducos Lionel
> package SUBRESP in intrf.spad by Barry Trager and Renaud Rioboo
> package SHP in sturm.spad by Lalo Gonzalez-Vega
> package POLUTIL in reclos.spad by Renaud Rioboo
> wrappers in poly.spad and newpoly.spad
>
> They weren't updated for at least 10 years, probably over
> 20 years.
>
> 2. improvements I can think of:
> 2.1 package PRS in prs.spad is pretty good.
>
> 2.2 SUBRESP is an ugly wrapper for chainSubResultants$PRS,
> see the comments in intrf.spad. Maybe we can enhance
> chainSubResultants$PRS and remove SUBRESP.
> (and I think SUBRESP has a bug)
>
> 2.3 I think SHP reinvented the wheel: subresultantSequence$SHP
> should be replaced by chainSubResultants$PRS.
>
> 2.4 POLUTIL reinvented the wheel of SHP: they try to do
> the same thing (find real root), but POLUTIL is inefficient and
> less advanced, however SHP currently contains bugs.
>
>
> This will be a pretty big change, so I want to hear your opinions
> first. (I've done some basic cleaning up, haven't done big
> changes yet).
Changes you propose look good. The devil is in details. I do
not see any traps in proposed change, so let me explain what
I mean using other examples. One is gcd. There is nice
theoretical trick that reduces expected complexity of
gcd of list of polynomials to complexity of single gcd
plus lower order terms. Unfortunately, when I implemented
this I got slowdown on the testsuite -- while theoretically
better in practice the trick was slower than current
implementation. Second example concerns 'map' on polynomials.
I noticed than 'map' is somewhat slow on large polynomials.
I tried to make it faster. It turned out that OutputForm
depended on current implementation (I can handle this by
providing conditional implementation) and again, while
change gives speedup for large polynomials it causes
slowdown for testsuite...
So, basically: change looks good but beware that troubles may
show up only after you implement it.
--
Waldek Hebisch
--
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 fricas-devel+unsubscr...@googlegroups.com.
To post to this group, send email to fricas-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
