Re: [sage-devel] Re: about karatsuba multiplication for polynomials over generic rings
Tom Boothby
> For a discussion of practical fast polynomial multiplication,
> see
> http://www.eecs.berkeley.edu/~fateman/papers/dumbisfast.pdf
That's a monologue, not a discussion, and you appear to have done
nothing of note in the paper. Why did you post it? It's got some
hand-waving discussion of how you squared a single sparse polynomial
with a modified dense algorithm, and didn't think the memory usage was
very bad. Moreover, your code is faster than Pearce's on a single
example. Whoop-dee-fucking-doo.
This is navel-gazing rubbish, more of an opinion piece than anything.
And you wonder why nobody reads your papers before seriously thinking
about designing a computer algebra system.
rjf
On Jan 14, 11:43 am, Tom Boothby <tomas.boot...@gmail.com> wrote:
> > For a discussion of practical fast polynomial multiplication,
> > see
> >http://www.eecs.berkeley.edu/~fateman/papers/dumbisfast.pdf
>
> That's a monologue, not a discussion,
dis·cus·sion (d-skshn)
n.
1. Consideration of a subject by a group; an earnest conversation.
2. A formal discourse on a topic; an exposition.
.....
> nothing of note in the paper.
> Why did you post it? It's got some
> hand-waving discussion of how you squared a single sparse polynomial
> with a modified dense algorithm, and didn't think the memory usage was
> very bad. Moreover, your code is faster than Pearce's on a single
> example. Whoop-dee-fucking-doo.
interesting that a half-page of code beats all these asymptotically
faster algorithms?
> This is navel-gazing rubbish, more of an opinion piece than anything.
> And you wonder why nobody reads your papers before seriously thinking
> about designing a computer algebra system.
others' experience are not necessarily doomed. But they are making
tasks more difficult.
Would your parents or teachers think any of this, below, describes
you?
# Not pick up on social cues and may lack inborn social skills, such
as being able to read others' body language, start or maintain a
conversation, and take turns talking.
# Dislike any changes in routines.
# Appear to lack empathy.
# Be unable to recognize subtle differences in speech tone, pitch, and
accent that alter the meaning of others’ speech. Thus, your child may
not understand a joke or may take a sarcastic comment literally.
Likewise, his or her speech may be flat and difficult to understand
because it lacks tone, pitch, and accent.
...
From the webmd page on asperger syndrome
http://www.webmd.com/brain/autism/tc/aspergers-syndrome-symptoms
I would suggest you scoot over to the Student Counseling Center..
RJF
Tom Boothby
>
> Would your parents or teachers think any of this, below, describes
> you?
>
> From the webmd page on asperger syndrome
>
> http://www.webmd.com/brain/autism/tc/aspergers-syndrome-symptoms
>
>
> I would suggest you scoot over to the Student Counseling Center..
You're a doctor, I'm sure you know best. Oh -- and the countless
hours of face-to-face interaction we get probably aids your diagnosis,
too.
rjf
On Jan 14, 9:53 pm, Tom Boothby <tomas.boot...@gmail.com> wrote:
> Oh -- and the countless
> hours of face-to-face interaction we get probably aids your diagnosis,
> too.
is too hard for you.
Tom Boothby
>
> I guess that answering the question (re parents or teachers)
> is too hard for you.
Yeah, it was pretty hard not to laugh. But then, I didn't really
restrain myself.
You *were* making a joke, right? Because you can't possibly think
that my "failure to detect sarcasm" over the internet, where body
language and intonation are crucial missing components of a
well-delivered sarcastic remark, is most readily explained by Asperger
syndrome. I mean, unless you had weakest understanding of
communication found in functioning adults -- um, which happens to be a
symptom of what you're suggesting I've got.
But since you asked twice, no, my parents and "teachers" wouldn't
agree to any of that. I handle myself fine (leaning a little to the
uncouth, as a matter of personal preference) in social situations from
the slums to the symphony. I attempt to break up routines wherever I
see them, and people tend to laugh at my jokes. Any lack of empathy
is probably due to psychopathy, not Asperger syndrome*.
* THAT LAST BIT WAS SARCASM -- NOTE THAT IT WAS PLACED AT THE END OF
A SERIES OF TRUE STATEMENTS TO CREATE A SENSE OF DISCHORD AND THUS
ENHANCE ITS COMEDIC VALUE. ALL-CAPS MAKE THIS SUBTLE.
rjf
syndrome
is relatively common among engineers, computer programmers,
mathematicians,
musicians, ... and sometimes has positive aspects (e.g. obsessive
attention to
details), it seemed to be a possibility for your behavior.
Maybe it is not the explanation.
No sarcasm in this note.
No sarcasm in my note first suggesting Asperger's syndrome.
RJF
Tom Boothby
> I was looking for an excuse for your behavior.
You might try to make excuses for your behavior, but I take full
responsibility for my own.
Perhaps you're offended at the candor with which I reviewed your
article (which, I'm sorry to say, wasn't in jest)? Maybe you can't
take the same level of criticism that you are so fond of dishing out?
You do not hesitate before calling the work of others stupid,
redundant, or irrelevant.
You're only offended at my critique because you know that my
observations are correct -- otherwise, you'd have shrugged it off and
moved on with your life. But instead, you paid lip service to my
complaints about your paper and instead launched an attack on my
character under the guise of concern for my mental health.
That is, you're attempting to "insult" me by indicating that I suffer
from Asperger syndrome. I'm offended on the behalf of those who live
with Asperger syndrome, a few of which* I consider friends, that you
would use their condition as an insult.
To answer the one relevant response to my critique: no, it's not
interesting that your implementation of a naive algorithm beat an
asymptotically faster algorithm. Anybody who is even moderately
surprised by this probably lacks a basic level of familiarity with
asymptotic analysis. Respectable institutions expect this level of
understanding from their undergraduates -- to say nothing of
professors!
> No sarcasm in this note.
> No sarcasm in my note first suggesting Asperger's syndrome.
Thanks for letting me know that you seriously, and without sarcasm,
view Asperger syndrome as material for insult. Though this new
revelation about your character does not surprise me, it does make me
a little sad.
* y'know, the kind who have been diagnosed by a real medical doctor,
not a phony computer scientist.
rjf
On Jan 15, 10:26 pm, Tom Boothby <tomas.boot...@gmail.com> wrote:
> > I was looking for an excuse for your behavior.
>
> You might try to make excuses for your behavior, but I take full
> responsibility for my own.
>
> Perhaps you're offended at the candor with which I reviewed your
> article (which, I'm sorry to say, wasn't in jest)?
this forum, and therefore there is a component of offensiveness
in your activity. Your opinion of my writings does not bother
me.
> Maybe you can't
> take the same level of criticism that you are so fond of dishing out?
> You do not hesitate before calling the work of others stupid,
> redundant, or irrelevant.
>
> You're only offended at my critique because you know that my
> observations are correct -- otherwise, you'd have shrugged it off and
> moved on with your life.
> But instead, you paid lip service to my
> complaints about your paper and instead launched an attack on my
> character under the guise of concern for my mental health.
your behavior WITHOUT addressing your character.
> That is, you're attempting to "insult" me by indicating that I suffer
> from Asperger syndrome.
> I'm offended on the behalf of those who live
> with Asperger syndrome, a few of which* I consider friends, that you
> would use their condition as an insult.
putting you tentatively in the same class. You may in fact merely
be uncouth, but the evidence continues to mount.
>
> To answer the one relevant response to my critique: no, it's not
> interesting that your implementation of a naive algorithm beat an
> asymptotically faster algorithm. Anybody who is even moderately
> surprised by this probably lacks a basic level of familiarity with
> asymptotic analysis. Respectable institutions expect this level of
> understanding from their undergraduates -- to say nothing of
> professors!
implementations of algorithms, you would find programs based on
asymptotically
fast algorithms that, as a practical matter, are quite slow. Your
estimate of the impact of asymptotic analysis on design and
implementation
is unfortunately inaccurate. In particular the original poster of
the Karatsuba question set the "cutoff" at zero, a lame decision.
My guess is that many programs in Sage have questionable choices
for less-than-huge inputs.
>
> > No sarcasm in this note.
> > No sarcasm in my note first suggesting Asperger's syndrome.
>
> Thanks for letting me know that you seriously, and without sarcasm,
> view Asperger syndrome as material for insult.
would not be an insult to say that I suspect you had measles.
Perhaps it is another facet of your Asperger's syndrome that leads you
to misunderstand
such basic notions as my seeking an explanation for your irrational
behavior.
While it is generally inappropriate to discuss one person's mental
health
with him on a public forum, it was my thought that perhaps persons
around you who
also read this might consider the situation and assist you in seeking
help.
Or not.
> Though this new
> revelation about your character does not surprise me, it does make me
> a little sad.
>
> * y'know, the kind who have been diagnosed by a real medical doctor,
> not a phony computer scientist.
positive sign.
RJF
Bill Hart
constructive criticism and insult.
I am tempted to post a copy of a referee's report I saw recently which
illustrates precisely the ignorant and arrogant attitude that I
perceive as endemic in some parts of the mathematical community. I'm
also tempted to post an example of a referee's report which I view as
exemplifying a completely antithetical attitude.
To Tom's credit, he posted his vicious criticism publicly, instead of
hiding behind the anonymity of the peer review process.
What Tom failed to do was make a single contribution to the subject of
polynomial arithmetic. His remarks regarding Richard's paper are no
more enlightened than the implementation that Richard was presumably
reacting to.
Can I also suggest that the spat between Tom and Richard is not even
of mild interest to the other people on this list.
That Asberger's is pretty widespread in the mathematical community is
pretty well known. I myself was awkward socially until about the age
of 21, preferring to hang out with my teachers and other geeks than to
socialise normally. It took many years before I felt like I could fit
in anywhere socially. I still find crowds extremely uncomfortable and
walk with a strange gait. I'm also not the only person in my family
with similar issues. I frequently judge other people's work critically
and fail to account for how my judgement might effect them
emotionally.
Having said all that, I'm not sure if I would say there were definite
signs of Asberger's in Tom, and yes, I've met Tom on numerous
occasions. He's not the only person in the Sage community who people
have speculated has autism though. Instead, I think Tom is picking up
bad habits from the mathematical community.
Interestingly, mathematicians like to justify their bad habits by
talking about rigour, high standards and the need to exclude
crackpots. However, this does not explain the arrogant attitude
towards those whose work is deemed "elementary". I recently observed a
mathematician write something to the effect, "I decided to post this
here because it is extremely elegant, even though it turned out to be
elementary", essentially apologising for wasting the time of their
peers with mathematics that wasn't obscure enough. I frequently hear
algorithmic and computational number theory described as "not number
theory research" and hear horror stories of people suffering their
entire careers against such an attitude.
Again, I feel like posting the two reviews of papers I recently saw to
contrast the two completely different attitudes in the community, and
how manifestly helpful the one attitude is and how manifestly
worthless the other.
Bill.
> --
> You received this message because you are subscribed to the Google Groups "sage-flame" group.
> To post to this group, send email to sage-...@googlegroups.com.
> To unsubscribe from this group, send email to sage-flame+...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/sage-flame?hl=en.
>
>
Bill Hart
multiplication, they might be interested to see this technical report
of Joris van der Hoeven, which appeared some time last year:
http://www.texmacs.org/joris/sparsemult/sparsemult.html
I'll be interested in hearing your analysis. Of course I wouldn't
suggest anyone try to actually implement these "research system"
algorithms in practice. They are far too technical to be of any use in
an elementary practical computer algebra system.
Bill.
rjf
On Jan 16, 10:14 am, Bill Hart <goodwillh...@googlemail.com> wrote:
> Since Tom and Richard seem to be such experts on sparse polynomial
> multiplication, they might be interested to see this technical report
> of Joris van der Hoeven, which appeared some time last year:
>
> http://www.texmacs.org/joris/sparsemult/sparsemult.html
>
> I'll be interested in hearing your analysis. Of course I wouldn't
> suggest anyone try to actually implement these "research system"
> algorithms in practice. They are far too technical to be of any use in
> an elementary practical computer algebra system.
>
> Bill.
>
>
naive algorithm for large enough problems. There is no
reason to doubt that, though I have not analyzed
the paper, apparently written in December, 2010.
My questions would be: How carefully have they implemented their
naive algorithm? Would modest variations on that naive
algorithm bump the cut-off point (much) further out?
I suppose one could try to duplicate their algorithm in another
system to compare it, or to examine their system and hack on
their programs.
I do not know Lecerf, but van der Hoeven has written substantial
programs in the past.
The problem of multiplying truncated power series is somewhat
different
from multiplying polynomials.
Thanks for the pointer to the paper. I'll have to look at it.
RJF
Bill Hart
http://lecerf.perso.math.cnrs.fr/publications/HoLe:2010:sparsemult.pdf
It looks much longer and more detailed and seems to cover polynomial
as well as series multiplication. In fact they seem to build power
series multiplication on top of polynomial multiplication using some
trick I haven't analysed in detail.
Maybe it is just an illusion that this is not the same paper because
of the pdf vs html format. At any rate, it is nicer to read when
typeset.
Bill.
rjf
On Jan 16, 11:10 am, Bill Hart <goodwillh...@googlemail.com> wrote:
> Is this the same paper?
>
> http://lecerf.perso.math.cnrs.fr/publications/HoLe:2010:sparsemult.pdf
>
> It looks much longer and more detailed and seems to cover polynomial
> as well as series multiplication. In fact they seem to build power
> series multiplication on top of polynomial multiplication using some
> trick I haven't analysed in detail.
>
> Maybe it is just an illusion that this is not the same paper because
> of the pdf vs html format. At any rate, it is nicer to read when
> typeset.
more papers in the references. It also has quite different timings.
I will look at this one in preference to the other because it is
in PDF and nicer to look at, and comes to a conclusion I find
interesting.
"If the size of the product is of the order of sP sQ then the naive
algorithm is already softly optimal".
The real issue, according to Monagan and Pierce is not the bit
complexity of the multiplications, but the sorting cost, which
presumably has to do with the bit complexity of comparison of
exponents. Without looking at this paper more, I might be
wrong, but my guess is they ignore that entirely.
As well as such things as efficient use of cache, to the
extent that it can be separately considered.
RJF
rjf
On Jan 16, 11:51 am, rjf <fate...@gmail.com> wrote:
....
> The real issue, according to Monagan and Pierce is not the bit
> complexity of the multiplications, but the sorting cost, which
> presumably has to do with the bit complexity of comparison of
> exponents. Without looking at this paper more, I might be
> wrong, but my guess is they ignore that entirely.
don't ignore it entirely. They dismiss it explicitly,
sort of. Assuming it out of the way.
"
Of course, our assumption that the support of the product is known is
very
strong: in many cases, it can be feared that the computation of this
support is actually
the hardest part of the multiplication problem."
Theoreticians can do that.
Nevertheless they have a section on times.
You will have to look at their timings for details, but
it looks to me like their Naive algorithm is fastest for
problems that have up to 10 thousands of terms.
RJF
Bill Hart
Ouch. I fear you are right!
Bill.
Tom Boothby
> Mathematicians seem to frequently misjudge the line between
> constructive criticism and insult.
This is sage-flame. Polite criticism is boring, so I inflated it to
insult. I would never think to review anybody else's paper so
viciously. Richard is a bit of a prick, so I try to respond in kind.
You don't see me talking to anybody else like this, right?
> Can I also suggest that the spat between Tom and Richard is not even
> of mild interest to the other people on this list.
Oh, probably not. It sure is fun, though. Besides, this is
sage-flame. People only subscribe to this because they like to
rubberneck.
Robert Miller
> sage-flame. People only subscribe to this because they like to
> rubberneck.
What bothers me is when people start having a serious discussion about
implementations of, e.g. sparse polynomial multiplication, on this
forum. This is a forum specifically intended for discord and
impoliteness. Save the intelligent discussions for a real mailing
list, where people who don't get a perverse satisfaction from
rubbernecking can read this!
PS - Tom does most certainly not have Asperger's syndrome. Trust me,
I'm a doctor. ;)
--
Robert L. Miller
http://www.rlmiller.org/
Bill Hart
polynomial multiplication precisely?
Robert Miller
> And where would you suggest we have serious discussions about sparse
> polynomial multiplication precisely?
Why not on sage-devel, where the thread started?
Tom Boothby
> On Sun, Jan 16, 2011 at 12:30 PM, Bill Hart <goodwi...@googlemail.com> wrote:
>> And where would you suggest we have serious discussions about sparse
>> polynomial multiplication precisely?
>
> Why not on sage-devel, where the thread started?
+1
Bill Hart
And are you suggesting you'd get intelligent discussion about such
matters there?
Robert Miller
> matters there?
Wow. What a great thing laughter is. Thank you for that, it was very refreshing.
> I had no idea it started there. It appeared here without context.
Likely with Tom lambasting Fateman's post. I can see how that would
look. For me it shows up as a response to a sage-devel thread, where
it gets nasty for a bit (as expected in sage-flame), and then goes
back to civil and useful, but unfortunately stays on sage-flame. Maybe
this mailing group is harmful? Wait a minute... It's sunny out, and
I'm wearing my bike gear. Bye, guys!
Bill Hart
>> And are you suggesting you'd get intelligent discussion about such
>> matters there?
>
> Wow. What a great thing laughter is. Thank you for that, it was very refreshing.
I wasn't joking. Let's look at the top 10 posts on sage-devel:
0. Trac server is down
1. Error building Sage
2. GCC wrapper on... lost interest after that
3. Question relevant to Sage on mathoverflow.net (couldn't make head
nor tail of it -- maybe a complaint that people used Magma?)
4. Question about EllipticCurve something or other -- question about
the operation of Sage
5. Testing rst files (what's a rst?)
6. Setting up a Notebook server
7. Sage Days 2867 Orsay, France
8. Are computer generated patches allowed?
9. Request for implementation of simplify_full on matrices, whatever that is
Seriously, you think sage-devel is the right place for discussion of
algorithms and their implementation? Now you make *me* laugh.
>
>> I had no idea it started there. It appeared here without context.
>
> Likely with Tom lambasting Fateman's post. I can see how that would
> look. For me it shows up as a response to a sage-devel thread, where
> it gets nasty for a bit (as expected in sage-flame), and then goes
> back to civil and useful, but unfortunately stays on sage-flame. Maybe
> this mailing group is harmful? Wait a minute... It's sunny out, and
> I'm wearing my bike gear. Bye, guys!
>
>
>
>
> --
> Robert L. Miller
> http://www.rlmiller.org/
>
Tom Boothby
> Seriously, you think sage-devel is the right place for discussion of
> algorithms and their implementation? Now you make *me* laugh.
Actually, I recall wonderful discussions about the implementation and
tuning of M4RI taking place on sage-devel. If I recall correctly, you
took part in them.
More recently, the message that initiated this thread, ironic as it
may seem to you, was actually about karatsuba multiplication for
polynomials over generic rings. I brought the conversation here
because RJF was once again being disrespectful to a new contributor,
and my reply in kind would have been inappropriate for sage-devel.
Robert Miller
> On 16 January 2011 20:40, Robert Miller <r...@rlmiller.org> wrote:
>>> And are you suggesting you'd get intelligent discussion about such
>>> matters there?
>>
>> Wow. What a great thing laughter is. Thank you for that, it was very refreshing.
>
> algorithms and their implementation? Now you make *me* laugh.
No, this was another sarcasm perception fail.
Bill Hart
rjf
On Jan 16, 3:09 pm, Bill Hart <goodwillh...@googlemail.com> wrote:
> On 16 January 2011 22:14, Robert Miller <r...@rlmiller.org> wrote:
>
> >> On 16 January 2011 20:40, Robert Miller <r...@rlmiller.org> wrote:
> >>>> And are you suggesting you'd get intelligent discussion about such
> >>>> matters there?
>
>
In order to read it you must have a newsgroup reader that filters out
the spam. In particular, not groups.google.com I use nntp.aioe.org
You can also look at the mailing list for Maxima (see its sourceforge
page).
This too has its share of messages about things that are not
exactly riveting.
As for the origin of this thread, you can go back to sage-devel and
see
it there. As for whether I was intemperate in responding to a first
time
poster, I guess you can look at his response, in which he thanks me
and
confirms most of what I said (points out one place I misunderstood his
timing result.)
So the intemperateness originates with Tom. Go figure.
Tom Boothby
> So the intemperateness originates with Tom. Go figure.
My opinion of your paper stands, but I concede that my reaction was a
knee-jerk based on your history of rude and overly harsh criticism.
Also, I might point out yet again that I don't think my actions are
even remotely appropriate in any forum other than sage-flame. Which
is why I post here, and why others subscribe.
Robert Miller
Woo! Yo mama so fat!