The old Google Groups will be going away soon, but your browser is incompatible with the new version.
patches for the calculus code
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 11 messages

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Nov 2 2008, 6:10 am
From: Wilfried_Huss <h...@finanz.math.tugraz.at>
Date: Sun, 2 Nov 2008 03:10:36 -0800 (PST)
Local: Sun, Nov 2 2008 6:10 am
Subject: patches for the calculus code
Hi,

I have written some code for the Maxima interface.
You can find the patches at:
http://www.math.tugraz.at/~huss/sage

calculus1.patch implements the conversion from Maxima
matrices to Sage matrices.

calculus2.patch adds symbolic gamma and factorial functions.
(The factorial is named fact() so it doesn't clash with the
factorial in sage.rings.arith)

Finally calculus3.patch renames the symbolic factorial to factorial(),
and changes all imports of sage.rings.arith.factorial to
sage.calculus.calculus.factorial. I had to keep a renamed version
of the factorial function in sage.rings.arith to avoid circular
imports at startup.

The patches are against 3.2-alpha1, after applying all 3 patches
all tests passed.

Here is a sample session with the new functionality:

sage: var('x,y')
sage: v = maxima('v: vandermonde_matrix([x, y, 1/2])')
sage: v
matrix([1,x,x^2],[1,y,y^2],[1,1/2,1/4])
sage: type(v)
<class 'sage.interfaces.maxima.MaximaElement'>
sage: v.sage()

[  1   x x^2]
[  1   y y^2]
[  1 1/2 1/4]
sage: mlist = maxima('[v, sin(x), 1, v.v]').sage()
sage: mlist

[[  1   x x^2]
[  1   y y^2]
[  1 1/2 1/4],
sin(x),
1,
[       x^2 + x + 1    x*y + x^2/2 + x    x*y^2 + 5*x^2/4]
[       y^2 + y + 1        3*y^2/2 + x  y^3 + y^2/4 + x^2]
[               7/4      y/2 + x + 1/8 y^2/2 + x^2 + 1/16]]
sage: [parent(i) for i in mlist]

[Full MatrixSpace of 3 by 3 dense matrices over Symbolic Ring,
Symbolic Ring,
Symbolic Ring,
Full MatrixSpace of 3 by 3 dense matrices over Symbolic Ring]

sage: gamma(x/2)(x=5)
3*sqrt(pi)/4

sage: f = factorial(x + factorial(y))
sage: maxima(f).sage()
factorial(factorial(y) + x)

sage: f(y=x)(x=3)
362880

I hope it is useful.

Greetings,
Wilfried Huss

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 2 2008, 2:38 pm
From: "William Stein" <wst...@gmail.com>
Date: Sun, 2 Nov 2008 11:38:25 -0800
Local: Sun, Nov 2 2008 2:38 pm
Subject: Re: [sage-devel] patches for the calculus code
On Sun, Nov 2, 2008 at 3:10 AM, Wilfried_Huss

for a trac account, then open three trac tickets, one
for each of the above? Thanks again!

William

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 2 2008, 2:46 pm
Date: Sun, 2 Nov 2008 11:46:05 -0800 (PST)
Local: Sun, Nov 2 2008 2:46 pm
Subject: Re: patches for the calculus code

On Nov 2, 11:38 am, "William Stein" <wst...@gmail.com> wrote:

> On Sun, Nov 2, 2008 at 3:10 AM, Wilfried_Huss

Hi,

> <h...@finanz.math.tugraz.at> wrote:

> > Hi,

> > I have written some code for the Maxima interface.
> > You can find the patches at:
> >  http://www.math.tugraz.at/~huss/sage

> > calculus1.patch implements the conversion from Maxima
> > matrices to Sage matrices.

This should come in handy, but starting with 3.2 we will finally have
pynac available for some of the basic symbolic manipulation tasks. It
is far from bullet proof, but it is a start, so the days of Maxima as
the default implementation of the low level symbolic stuff is coming
finally to an end :)

> > calculus2.patch adds symbolic gamma and factorial functions.
> > (The factorial is named fact() so it doesn't clash with the
> > factorial in sage.rings.arith)

Provided the factorial bit does not interfere with the current non-
symbolic code this could be useful.

> > Finally calculus3.patch renames the symbolic factorial to factorial(),
> > and changes all imports of sage.rings.arith.factorial to
> > sage.calculus.calculus.factorial. I had to keep a renamed version
> > of the factorial function in sage.rings.arith to avoid circular
> > imports at startup.

I don't like this patch at all since it forces us to use a Maxima
function even for integers which ought to be the most common use of
factorial. When the point counting code was using Maxima to compute
ceil, floor and sqrt the code as a whole was slower by a factor of
three which illustrates nicely why we don't want to use Maxima unless
there is a good reason to do so. Especially considering that using
mpfr's functions was abotu a million times faster since there is no
pexpect overhead. I could see using that code in case the argument is
non-integer, but not using the highly optimized gmp implementation for
something that is many orders of magnitude slower is just not what we
want to do.

Cheers,

Michael

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 2 2008, 3:07 pm
From: "William Stein" <wst...@gmail.com>
Date: Sun, 2 Nov 2008 12:07:38 -0800
Local: Sun, Nov 2 2008 3:07 pm
Subject: Re: [sage-devel] Re: patches for the calculus code

And I think we still want to have as many conversions between
Maxima and Sage as possible, even if Maxima isn't the default
backend for symbolic manipulation. It's still very good for
Maxima and Sage to be able to communicate.  The more
capabilities for communication between Sage and other systems,
the better.

>> > calculus2.patch adds symbolic gamma and factorial functions.
>> > (The factorial is named fact() so it doesn't clash with the
>> > factorial in sage.rings.arith)

> Provided the factorial bit does not interfere with the current non-
> symbolic code this could be useful.

+1

>> > Finally calculus3.patch renames the symbolic factorial to factorial(),
>> > and changes all imports of sage.rings.arith.factorial to
>> > sage.calculus.calculus.factorial. I had to keep a renamed version
>> > of the factorial function in sage.rings.arith to avoid circular
>> > imports at startup.

> I don't like this patch at all since it forces us to use a Maxima
> function even for integers which ought to be the most common use of
> factorial.

I didn't look at the patch, but just want to comment that using
doesn't a priori imply that Maxima is used to compute factorials.
I.e., I could imagine an implementation where GMP is still used
for this:

sage: time n = factorial(10^6)
CPU times: user 1.90 s, sys: 0.10 s, total: 2.00 s

> When the point counting code was using Maxima to compute
> ceil, floor and sqrt the code as a whole was slower by a factor of
> three which illustrates nicely why we don't want to use Maxima unless

Do you really mean "three orders of magnitude", i.e., a factor of 1000? :-)

> there is a good reason to do so. Especially considering that using
> mpfr's functions was abotu a million times faster since there is no
> pexpect overhead. I could see using that code in case the argument is
> non-integer, but not using the highly optimized gmp implementation for
> something that is many orders of magnitude slower is just not what we
> want to do.

If a ticket is posted with the third patch, the reviewer should just make
sure that factorial(n) for input an integer (1) doesn't slow down, and (2)
returns an integer.

--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 2 2008, 3:24 pm
Date: Sun, 2 Nov 2008 12:24:51 -0800 (PST)
Local: Sun, Nov 2 2008 3:24 pm
Subject: Re: patches for the calculus code

On Nov 2, 12:07 pm, "William Stein" <wst...@gmail.com> wrote:

Yes, I do not disagree, but I would much rather see fundamental
functionality directly implemented in Sage than to use Maxima for say
the generation of a Vandermonde matrix. Sooner or later someone will
complain about the performance when it is generated in Maxima since
due to pexpect it can never approach native speed implementations for
obviously applies to any system that has to communicate via pexpect
for licensing or technical reasons, i.e. GAP, Axiom, Magma and so on,
but computations where the communication overhead is tiny compared to
the computational effort the pexpect overhead is negligible can employ
pexpect without too much of a penalty. William and I disagree on this
point, but in 10 years I see very little non-optional functionality in
Sage provided via pexpect since someone in the Sage project will
either have implemented the functionality natively or the project we
are using has been library-fied some way.

Yes, factorial should try to use gmp in case the argument can be
coerced into an Integer and should that fail have pynac/Maxima have a
go at it.

> > When the point counting code was using Maxima to compute
> > ceil, floor and sqrt the code as a whole was slower by a factor of
> > three which illustrates nicely why we don't want to use Maxima unless

> Do you really mean "three orders of magnitude", i.e., a factor of 1000? :-)

The doctest jumped from about 250 seconds to 800 just by using ceil,
floor and sqrt from calculus. And those values were only used to
determine some thresholds for the computation and barely used any
significant time in to algorithm. But using the calculus functionality
instantly I noticed that performance went to shit, so I complained
about it and ceil, floor and sqrt in that code are no longer imported
from calculus :)

> > there is a good reason to do so. Especially considering that using
> > mpfr's functions was abotu a million times faster since there is no
> > pexpect overhead. I could see using that code in case the argument is
> > non-integer, but not using the highly optimized gmp implementation for
> > something that is many orders of magnitude slower is just not what we
> > want to do.

> If a ticket is posted with the third patch, the reviewer should just make
> sure that factorial(n) for input an integer (1) doesn't slow down, and (2)
> returns an integer.

+1

Cheers,

Michael

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 2 2008, 3:36 pm
From: "William Stein" <wst...@gmail.com>
Date: Sun, 2 Nov 2008 12:36:54 -0800
Local: Sun, Nov 2 2008 3:36 pm
Subject: Re: [sage-devel] Re: patches for the calculus code

It's not only pexpect.  It's that maxima via clisp is itself very slow.

> obviously applies to any system that has to communicate via pexpect
> for licensing or technical reasons, i.e. GAP, Axiom, Magma and so on,
> but computations where the communication overhead is tiny compared to
> the computational effort the pexpect overhead is negligible can employ
> pexpect without too much of a penalty. William and I disagree on this
> point, but in 10 years I see very little non-optional functionality in
> Sage provided via pexpect since someone in the Sage project will
> either have implemented the functionality natively or the project we
> are using has been library-fied some way.

I hope I'm wrong!

Thanks for the clarification.  Now I remember what you're talking about.

--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 2 2008, 3:46 pm
Date: Sun, 2 Nov 2008 12:46:14 -0800 (PST)
Local: Sun, Nov 2 2008 3:46 pm
Subject: Re: patches for the calculus code

On Nov 2, 12:36 pm, "William Stein" <wst...@gmail.com> wrote:

> On Sun, Nov 2, 2008 at 12:24 PM, mabshoff <mabsh...@googlemail.com> wrote:

<SNIP>

> > Yes, I do not disagree, but I would much rather see fundamental
> > functionality directly implemented in Sage than to use Maxima for say
> > the generation of a Vandermonde matrix. Sooner or later someone will
> > complain about the performance when it is generated in Maxima since
> > due to pexpect it can never approach native speed implementations for
> > something where the overhead to computational ratio is so bad. That

> It's not only pexpect.  It's that maxima via clisp is itself very slow.

Sure, for example factorization and linear algebra aren't exactly fast
with sbcl either, but there are certainly useful and some times very
complex algorithms implemented in Maxima. Way back it was the right
decision to use Maxima to get up to speed quickly, but as is many
people would claim that for limits or integration it cannot compete
with either MMA or Maple, hence the drive to do our own
implementations starting from the bottom up.

> > obviously applies to any system that has to communicate via pexpect
> > for licensing or technical reasons, i.e. GAP, Axiom, Magma and so on,
> > but computations where the communication overhead is tiny compared to
> > the computational effort the pexpect overhead is negligible can employ
> > pexpect without too much of a penalty. William and I disagree on this
> > point, but in 10 years I see very little non-optional functionality in
> > Sage provided via pexpect since someone in the Sage project will
> > either have implemented the functionality natively or the project we
> > are using has been library-fied some way.

> I hope I'm wrong!

Well, when I am looking at two potential software packages for
inclusion in Sage doing the same thing I always would prefer the
library solution even if it means more work. pexpect in the long term
is just a crutch for something that could be linked in as a library.

<SNIP>

> >> Do you really mean "three orders of magnitude", i.e., a factor of 1000? :-)

> > The doctest jumped from about 250 seconds to 800 just by using ceil,
> > floor and sqrt from calculus. And those values were only used to
> > determine some thresholds for the computation and barely used any
> > significant time in to algorithm. But using the calculus functionality
> > instantly I noticed that performance went to shit, so I complained
> > about it and ceil, floor and sqrt in that code are no longer imported
> > from calculus :)

> Thanks for the clarification.  Now I remember what you're talking about.

Good :). Note that the reason to use the calculus imports was that the
double precision version used previously was insufficient due to too
little precision. Right now we should be using mpfr versions of those
functions which are plenty fast and exact on all platforms :)

Cheers,

Michael

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 3 2008, 4:42 am
From: Wilfried_Huss <h...@finanz.math.tugraz.at>
Date: Mon, 3 Nov 2008 01:42:39 -0800 (PST)
Local: Mon, Nov 3 2008 4:42 am
Subject: Re: patches for the calculus code

> for a trac account, then open three trac tickets, one
> for each of the above? Thanks again!

Yes, I just did.

Greetings,
Wilfried

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 3 2008, 5:23 am
From: Wilfried_Huss <h...@finanz.math.tugraz.at>
Date: Mon, 3 Nov 2008 02:23:39 -0800 (PST)
Local: Mon, Nov 3 2008 5:23 am
Subject: Re: patches for the calculus code

On 2 Nov., 20:46, mabshoff <mabsh...@googlemail.com> wrote:

Yes, but as far as I understand Maxima will still be used for the high
level
symbolic stuff for the foreseeable future. So I think it makes sense
to have
the conversions between Sage and Maxima as complete as possible.

But it doesn't use Maxima for non-symbolic input.

Just as before factorial(x) just tries to call

x.factorial()

only if this raises an exception the symbolic version is
constructed.

sage: def f(n):
sage:   s = 0
sage:   for i in xrange(n):
sage:      s += factorial(2^i)
sage:   return s.ndigits()

sage: time f(22)
12346641
CPU time: 10.89 s,  Wall time: 10.94 s

This is the same with or without the patch.

Greetings,
Wilfried

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 3 2008, 12:42 pm
Date: Mon, 3 Nov 2008 09:42:40 -0800
Local: Mon, Nov 3 2008 12:42 pm
Subject: Re: [sage-devel] Re: patches for the calculus code
On Nov 3, 2008, at 2:23 AM, Wilfried_Huss wrote:

Yes, and even when it's not called in the background for a lot of
stuff, it will be very useful to have good conversion routines. For
example, right now there is a lot of hard work going on to improve
the sage-magma interface despite the fact that magma is an optional
package.

That sounds very good. Did you make a ticket?

- Robert

To post a message you must first join this group.
You do not have the permission required to post.
More options Nov 3 2008, 3:09 pm
From: Wilfried_Huss <h...@finanz.math.tugraz.at>
Date: Mon, 3 Nov 2008 12:09:59 -0800 (PST)
Local: Mon, Nov 3 2008 3:09 pm
Subject: Re: patches for the calculus code

On 2 Nov., 12:10, Wilfried_Huss <h...@finanz.math.tugraz.at> wrote:

> Hi,

> I have written some code for the Maxima interface.
> You can find the patches at:
>  http://www.math.tugraz.at/~huss/sage

> calculus1.patch implements the conversion from Maxima
> matrices to Sage matrices.

This is now: #4431

> calculus2.patch adds symbolic gamma and factorial functions.
> (The factorial is named fact() so it doesn't clash with the
> factorial in sage.rings.arith)

This is now: #4432

> Finally calculus3.patch renames the symbolic factorial to factorial(),
> and changes all imports of sage.rings.arith.factorial to
> sage.calculus.calculus.factorial. I had to keep a renamed version
> of the factorial function in sage.rings.arith to avoid circular
> imports at startup.

This is now: #4433