On 09/15/2017 04:23 AM, oldk1331 wrote:
> I reviewed the patch, it's good
Thanks for the review.
I'll push my patch tonight.
> I then took a profile, to my surprise, almost 30% time is spent on
> |DIRPROD;subtractIfCan;2$U;17| and |NNI;subtractIfCan;2$U;4|,
> see the 'subtractIfCan' calls in gbintern.spad. That function is
> implemented in vector.spad
>
> subtractIfCan(u:%, v:%):Union(%,"failed") ==
> w := new(dim, 0)$Vector(R)
> for i in 1..dim repeat
> (c := subtractIfCan(qelt(u, i)$Rep, qelt(v,i)$Rep)) case "failed"
> =>
> return "failed"
> qsetelt!(w, i, c::R)$Rep
> w pretend %
>
> It has 2 problems:
> 1. it allocs the 'w' first, which very likely will not be used.
> 2. subtractIfCan for NNI is very wasteful, the return type
> Union("failed", NNI) takes 3 times the space than NNI.
> (type Maybe doesn't have this problem, but that's a different topic)
>
> I changed it to (subtractIfCan2 is integer subtraction)
>
> subtractIfCan(u:%, v:%):Union(%,"failed") ==
> for i in 1..dim repeat
> qelt(u, i)$Rep < qelt(v,i)$Rep=>
> return "failed"
> map(subtractIfCan2$R, u, v)
>
> together with other small optimization, I managed to speed it up to
> 443 seconds (saves 40% time).
That's wonderful, but although your patch certainly works for NNI, I am
a bit worried, because in general it assumes that < is compatible with
addition/subtraction.
The specification of subtractIfCan
subtractIfCan(x, y) returns an element z such that z+y=x or “failed”
if no such element exists.
does, however, not have such a connection. And neither the specification
of + nor that of < makes such a connection. The connection is only
stated in OrderedAbelianMonoid from which OrderedAbelianMonoidSup
inherits. The latter one is the argument type of Expon in
GroebnerPackage. So your patch is fine, but somehow at the wrong place.
Or rather it must be made conditional
if R has CancellationAbelianMonoid then
if R has OrderedAbelianMonoidSup then
subtractIfCan(u:%, v:%):Union(%,"failed") ==
for i in 1..dim repeat
qelt(u, i)$Rep < qelt(v,i)$Rep=>
return "failed"
map(subtractIfCan2$R, u, v)
else
subtractIfCan(u:%, v:%):Union(%,"failed") ==
w := new(dim, 0)$Vector(R)
for i in 1..dim repeat
(c := subtractIfCan(qelt(u, i)$Rep, qelt(v,i)$Rep)) case "failed" =>
return "failed"
qsetelt!(w, i, c::R)$Rep
w pretend %
In fact, for the most common Groebner computations R is NNI, so I guess,
it even makes sense to have specialized code for it. So then
map(subtractIfCan2$R, u, v) simply becomes something like u-v.
There are a few places in gbintern.spad where it simply says
subtractIfCan(a, b) :: Expon
so subtraction is expected not to fail. Unfortunately, there is no other
export like subtract: (%, %) -> % which gives an error if subtraction is
failing. Such a subtract function would be better in case it is already
known that subtraction will not fail, like in the GB case.
Speaking of subtraction. In VectorCategory I see
if R has AbelianGroup then
- u == map(x +-> - x, u)
n : Integer * u : % == map(x +-> n*x, u)
u - v == u + (-v)
That's fine in mathematically, but in Vector I don't see that
specialised. In other words each subtraction of two vectors allocates 2
new arrays, where one would certainly be enough.
Ralf
--
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 [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
