sage talk
William Stein
I just gave this Sage talk at SeaPIG (Seattle Python Interest Group --
http://www.seapig.org/NorthwestPythonDay):
http://sage.math.washington.edu/talks/20090131-seapig/
This was to about 60 people. It went very well and many people in the
audience thanked us (=the sage developers).
William
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
Minh Nguyen
On Sun, Feb 1, 2009 at 10:37 AM, William Stein <wst...@gmail.com> wrote:
> I just gave this Sage talk at SeaPIG (Seattle Python Interest Group --
> http://www.seapig.org/NorthwestPythonDay):
>
> http://sage.math.washington.edu/talks/20090131-seapig/
>
> This was to about 60 people. It went very well and many people in the
> audience thanked us (=the sage developers).
The talk wiki page at
http://wiki.sagemath.org/Talks
has been updated with the above info.
Regards
Minh Van Nguyen
William Stein
Thanks! I was scared you were going to point out 10 typos :-)
William
Minh Nguyen
Believe it or not, I've been waiting for over 10 minutes and the
Firefox download manager hasn't finished downloading your talk slides.
So unfortunately I can't put on my trademark mvngu pedantic hat :-)
Regards
Minh Van Nguyen
Simon King
On 31 Jan., 19:04, William Stein <wst...@gmail.com> wrote:
...
could not resist when you wrote the line above ;-)
Cheers
Simon
John Cremona
John
Roman Pearce
bad as old Linbox times imply. The linalg package has been obsolete
for some time now.
-bash-3.2$ maple
|\^/| Maple 12 (X86 64 LINUX)
._|\| |/|_. Copyright (c) Maplesoft, a division of Waterloo Maple
Inc. 2008
\ MAPLE / All rights reserved. Maple is a trademark of
<____ ____> Waterloo Maple Inc.
| Type ? for help.
> A := LinearAlgebra:-RandomMatrix(200);
[ 200 x 200
Matrix ]
A := [ Data Type:
anything ]
[ Storage:
rectangular ]
[ Order:
Fortran_order ]
> time(LinearAlgebra:-Determinant(A));
0.479
> A := matrix(convert(A,listlist)):
> time(linalg[det](A));
19.699
The next release of Maple should have similar improvements for solving
dense linear systems. It's not as fast as LinBox, but it's not
embarrassing :)
William Stein
>
> I just want to point out the Maple's linear algebra is not quite as
> bad as old Linbox times imply. The linalg package has been obsolete
> for some time now.
Does
A := LinearAlgebra:-RandomMatrix(n);
create a random matrix with entries uniformly distributed between -99 and 99?
I just tried a few timings comparing Sage and Maple with the commands
you suggest and using "a = random_matrix(ZZ,200,x=-99,y=99)" in Sage:
n=200, sage: 0.56
n=200, Maple: 0.52
n=400, sage: 3.22 seconds
n=400, maple: 6.07 seconds
n=800, sage: 25.1 seconds
n=800, maple: 146.4 seconds
n=1200, sage: 83.3 seconds
n=1200, maple:
Thanks for pointing out that I wasn't using the optimal command in
Maple. I had found those commands by searching the web and doing what
the web pages I found suggested. Obviously, that's not the right way
to use Maple.
What algorithm is maple using to compute the determinants of integer
matrices? I'm curious if it is the same one as Sage uses, but Maple
is just slower because of a worse implementation. Based on the timing
discrepancies above, though, it appears that Maple is using a much
much worse O complexity algorithm.
Also, how does Maple behave if the input involves very large numbers?
For example, in Sage for 129-bit input:
sage: a = random_matrix(ZZ,200,x=-2^128,y=2^128)
sage: time d = a.det()
CPU times: user 4.48 s, sys: 0.00 s, total: 4.48 s
and for 513-bit input:
sage: a = random_matrix(ZZ,200,x=-2^512,y=2^512)
sage: time d = a.det()
CPU times: user 73.76 s, sys: 0.01 s, total: 73.77 s
By the way, most of the work for Sage computing dets uses IML, not
Linbox. Linbox is only used at the very end to compute a couple of
determinants mod p. I think Linbox has a det algorithm, but there is
a subtle overflow issue involving computing the Hadamard bound when
the input matrix has huge entries, which requires using either MPFR
(with Linbox doesn't depend on) or some tedious-to-implement algorithm
which never got implemented in Linbox.... Also, IML is faster/more
robust at solving A*x = b than Linbox, I think, so IML's det may
suffer from that. On the other hand, for all I know Clement fixed all
these issues in Linbox, and they aren't a problem anymore.
-- William
>
> -bash-3.2$ maple
> |\^/| Maple 12 (X86 64 LINUX)
> ._|\| |/|_. Copyright (c) Maplesoft, a division of Waterloo Maple
> Inc. 2008
> \ MAPLE / All rights reserved. Maple is a trademark of
> <____ ____> Waterloo Maple Inc.
> | Type ? for help.
>> A := LinearAlgebra:-RandomMatrix(200);
> [ 200 x 200
> Matrix ]
> A := [ Data Type:
> anything ]
> [ Storage:
> rectangular ]
> [ Order:
> Fortran_order ]
>
>> time(LinearAlgebra:-Determinant(A));
> 0.479
>
>> A := matrix(convert(A,listlist)):
>> time(linalg[det](A));
> 19.699
>
>
> The next release of Maple should have similar improvements for solving
> dense linear systems. It's not as fast as LinBox, but it's not
> embarrassing :)
> >
>
William Stein
> On Sun, Feb 1, 2009 at 11:21 AM, Roman Pearce <rpea...@gmail.com> wrote:
>>
>> I just want to point out the Maple's linear algebra is not quite as
>> bad as old Linbox times imply. The linalg package has been obsolete
>> for some time now.
>
> It should print a deprecation warning so I would know. Could you suggest that?
>
> Does
>
> A := LinearAlgebra:-RandomMatrix(n);
>
> create a random matrix with entries uniformly distributed between -99 and 99?
>
> I just tried a few timings comparing Sage and Maple with the commands
> you suggest and using "a = random_matrix(ZZ,200,x=-99,y=99)" in Sage:
>
> n=200, sage: 0.56
> n=200, Maple: 0.52
>
> n=400, sage: 3.22 seconds
> n=400, maple: 6.07 seconds
>
> n=800, sage: 25.1 seconds
> n=800, maple: 146.4 seconds
>
> n=1200, sage: 83.3 seconds
> n=1200, maple:
n=1200, sage: 83.3 seconds
n=1200, maple: 1045.069 seconds.
By the way, Magma does this 1200x1200 example in 28 seconds! Magma is
very very good at dets around this size when the entries of the input
matrix are small. When they are big, Sage is much better than Magma
(or anything else).
-- William
Tim Lahey
Maple's Linear Algebra is noted for not being particularly good at large
sizes. With symbolic entries, it's much worse. Thanks for these timings,
it just reinforces my idea that I should switch as soon as the calculus
improves.
Is there a particular reason why Magma is that much better for small
inputs?
Cheers,
Tim.
---
Tim Lahey
PhD Candidate, Systems Design Engineering
University of Waterloo
http://www.linkedin.com/in/timlahey
William Stein
I would love to know. I've cc'd Allan Steel, since he would know.
Maybe he'll tell us.
Allan, for reference the complete thread for this discussion is:
http://groups.google.com/group/sage-devel/browse_thread/thread/30d4a52c2795feb9
By the way, we are having major problems with Sage on Fedora 64-bit...
and somebody mentioned you might have some tricks to fix this. The
thread about that is here:
-- William
Roman Pearce
>
> > I just want to point out the Maple's linear algebra is not quite as
> > bad as old Linbox times imply. The linalg package has been obsolete
> > for some time now.
>
> It should print a deprecation warning so I would know. Could you suggest that?
change it now.
> Does A := LinearAlgebra:-RandomMatrix(n);
> create a random matrix with entries uniformly distributed between -99 and 99?
> What algorithm is maple using to compute the determinants of integer
> matrices? I'm curious if it is the same one as Sage uses, but Maple
> is just slower because of a worse implementation. Based on the timing
> discrepancies above, though, it appears that Maple is using a much
> much worse O complexity algorithm.
large determinant. It also has code to identify structured systems.
The linear solver uses p-adic lifting for dense systems (and a bunch
of methods for sparse systems) which is fine.
> By the way, most of the work for Sage computing dets uses IML,
> not Linbox.
is doing, but if I had to guess, I'd say they are solving a system
AX=B mod p where p is 23 bits using SSE floating point and using p-
adic lifting and rational reconstruction to recover the determinant.
I can't help thinking that in another year or two all this stuff will
be done ten times faster on GPUs.
mabshoff
On Feb 1, 1:26 pm, William Stein <wst...@gmail.com> wrote:
<SNIP>
> > Maple's Linear Algebra is noted for not being particularly good at large
> > sizes. With symbolic entries, it's much worse. Thanks for these timings,
> > it just reinforces my idea that I should switch as soon as the calculus
> > improves.
>
> > Is there a particular reason why Magma is that much better for small
> > inputs?
>
> I would love to know. I've cc'd Allan Steel, since he would know.
> Maybe he'll tell us.
> Allan, for reference the complete thread for this discussion is:
>
> By the way, we are having major problems with Sage on Fedora 64-bit...
> and somebody mentioned you might have some tricks to fix this. The
> thread about that is here:
>
I doubt that is the same problem the Magma people saw since that issue
seems related to randomization and/or prelinking. I have thought about
the problem we see some more and IMHO we should modify Singular to
ignore the alleged problem reported by calling sbrk() since high level
Singular does not care about memory allocations failing anyway since
it tends just to crash.
The other solution that works quickly is not to use mmap but the
system malloc for oMalloc allocations exposes another bug that needs
to be fixed anyway, but the way it looks that will be something scope
related in Cython, so I have no clue how to even approach this. My
guess would be that RobertWB would be the man who could fix this the
quickest, but he is busy with real life, so I am not sure how to
approach this.
> -- William
Cheers,
Michael
William Stein
>
> On Feb 1, 12:46 pm, William Stein <wst...@gmail.com> wrote:
>> On Sun, Feb 1, 2009 at 11:21 AM, Roman Pearce <rpear...@gmail.com> wrote:
>>
>> > I just want to point out the Maple's linear algebra is not quite as
>> > bad as old Linbox times imply. The linalg package has been obsolete
>> > for some time now.
>>
>> It should print a deprecation warning so I would know. Could you suggest that?
>
> I can ask but it was deprecated in Maple 6 so I don't think they'll
> change it now.
What does that mean? I am sitting here using Maple 12, and I type
wstein@sage:/space/wstein/sage-3.3.alpha2$ maple
|\^/| Maple 12 (X86 64 LINUX)
...
> with(linalg);
> A := LinearAlgebra:-RandomMatrix(200);
> det(A);
and it takes 30 seconds.
I know it was deprecated in Maple 6, but isn't it odd that Maple doesn't even
print a warning or something like 6 years later that one is recommended not
to use the det function?
I know this is a Maple question, not a Sage question, but the Sage
project is running into very similar issues of deprecation, etc., and
we're trying to come up with the best policies for how to deal with
them. Obviously the Maple devs must have put a lot of thought into
this, and the solution they came up with is extremely different than
what I would do, so I'm wondering if you have any thoughts. In
summary, my perspective is that the Maple devs decided that to
deprecate a function "foo" means:
(1) leave foo in, i.e., never delete it from maple, [in sage we
would remove foo after 6-12 months],
(2) don't print any warnings at all when people use foo ever [in
sage we would print a deprecation warning]
(3) make sure foo continues to work exactly as it always did before
it was deprecated, in particular, even if there is an identical
function Foo elsewhere in maple that is a million times faster, make
sure that foo continues to be a million times slower than Foo [in
Sage, we would at least make foo call Foo, I think].
So in Sage our plan is to do everything differently. Sage is a young
and immature project compared to Maple. Any thoughts about whether
we're just totally headed down the wrong path with respect to
deprecation. Note that in Sage we have put in various deprecation
warnings, but I think we still haven't ever swept up and deleted old
deprecated code. We just plan to.
-- William
William Stein
>> not Linbox.
>
> IML is very good. The algorithms are good :) I'm not sure what Magma
> is doing, but if I had to guess, I'd say they are solving a system
> AX=B mod p where p is 23 bits using SSE floating point and using p-
> adic lifting and rational reconstruction to recover the determinant.
> I can't help thinking that in another year or two all this stuff will
> be done ten times faster on GPUs.
+1
Computing determinants, ranks, minpolys, charpolys, elementary
invariants, etc. of matrices is a perfect example of a superb class of
problems to attack with GPUs. I hope you'll write a nice paper about
doing so!
-- William
Roman Pearce
> > with(linalg);
> > A := LinearAlgebra:-RandomMatrix(200);
> > det(A);
>
> and it takes 30 seconds.
>
> I know it was deprecated in Maple 6, but isn't it odd that Maple doesn't even
> print a warning or something like 6 years later that one is recommended not
> to use the det function?
functionality and possibly new names and have the old commands call
the new commands. In this case it wasn't feasible though. The old
style "matrix" supports things that the new style "Matrix" does not,
like symbolic entries. For example:
A := matrix(4,4);
d := linalg[det](A);
Now this is arguably a useless feature (try 12x12) but there was a lot
of old code (and books, and lecture notes) that required it. So they
decided to leave the linalg package intact. It also didn't help that
the new LinearAlgebra package had a lot of performance problems for
exact matrices at first. Those are gradually being addressed.
> (1) leave foo in, i.e., never delete it from maple, [in sage we
> would remove foo after 6-12 months],
of people who expect their 10 year old code to run. It's almost a
Microsoft-like situation. And since people have to pay for upgrades
there's an entirely different dynamic. Many people skip releases and
will only upgrade if there's something new that interests them. In a
way it makes sense. Maple is a 25 year old product, so any change -
no matter how big - is evolutionary. The developers need to minimize
the hassle that this causes for users, because for many people Maple
is just a tool that they don't want to be bothered by. Sage doesn't
have this problem because it is a young project with a smaller, mostly
enthusiast user base. You should break everything that's wrong while
you can :)
> (2) don't print any warnings at all when people use foo ever [in
> sage we would print a deprecation warning]
>
> (3) make sure foo continues to work exactly as it always did before
> it was deprecated, in particular, even if there is an identical
> function Foo elsewhere in maple that is a million times faster, make
> sure that foo continues to be a million times slower than Foo [in
> Sage, we would at least make foo call Foo, I think].
If it's 10 times faster on average and an order of magnitude faster in
general then users won't complain. This is good for developers too,
because changes require a lot of extra work (tests, etc) so it
guarantees that development time is only spent on something good. My
preference is also to delete old code. Keep a copy somewhere but rip
it out of the system. And - this is the hardest part - hold back new
code that is not good enough. I have thrown out more code than I have
in Maple now. Sometimes a good effort falls short. You have to
accept it, learn from it, and move on.
And, in a different message:
> invariants, etc. of matrices is a perfect example of a superb class of
> problems to attack with GPUs. I hope you'll write a nice paper about
> doing so!
with this approach:
http://www.cis.udel.edu/~wan/publications/jsc05.pdf
Ronan Paixão
> A new version of Maple is only released every year, and there are lots
> of people who expect their 10 year old code to run. It's almost a
> Microsoft-like situation. And since people have to pay for upgrades
> there's an entirely different dynamic. Many people skip releases and
> will only upgrade if there's something new that interests them. In a
> way it makes sense. Maple is a 25 year old product, so any change -
> no matter how big - is evolutionary. The developers need to minimize
> the hassle that this causes for users, because for many people Maple
> is just a tool that they don't want to be bothered by. Sage doesn't
> have this problem because it is a young project with a smaller, mostly
> enthusiast user base. You should break everything that's wrong while
> you can :)
I believe Sage is a direct contrast to that above. Sage releases often
(often enough that some users skip *many* releases, like I've seen
people talking about sage 3.0.X series). Since Sage is freely available,
there's not much users can rant, specially since mabshoff is working
(really hard) to make available older versions of Sage. Specially for
this reason, it's possible for a book to publish some code and specify
Sage's version, and in some years possibly a user will be able to
download the older Sage and run the code. Of course since Sage evolves
much faster, it's also possible that the code will not run on current
versions, but I think that stalling development in favor of backwards
compatibility must have a limit or we risk losing some of what makes
Sage that special. If a user wants to use a new Sage feature with old
code, I think it should be left to the user to choose a compromise
between breaking the code and using the new feature (IF the code breaks,
which is not always).
Ronan