reduce
William Stein
REDUCE is now open source: http://reduce-algebra.com/
Is there anything in there worth using for Sage?
William
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
Tim Lahey
On Jan 3, 2009, at 2:22 AM, William Stein wrote:
>
> Hi,
>
> REDUCE is now open source: http://reduce-algebra.com/
> Is there anything in there worth using for Sage?
>
It looks like it has some nice facilities for differential equations,
both ODEs and PDEs. Not necessarily solutions, but for working with
them and investigating them.
For instance, for my purposes:
crack - CRACK is a package for solving overdetermined systems of
partial or ordinary differential equations (PDEs, ODEs). Examples of
programs which make use of CRACK for investigating ODEs (finding
symmetries, first integrals, an equivalent Lagrangian or a
"differential factorization") are included.
conlaw - This package presents three different approaches for the
determination of conservation laws of differential equations. A paper
describing these approaches is also available.
fide - This package uses computer algebra to automate the process of
numerically solving systems of partial differential equations (PDES).
For PDE solving, the finite difference method is applied. (Note: the
documentation for this package is in text format.)
I thought of making something like fide, but many other things have
got in the way.
The crack package seems to be quite interesting too.
I'm quite certain that there are a lot of useful things in there.
Cheers,
Tim.
---
Tim Lahey
PhD Candidate, Systems Design Engineering
University of Waterloo
http://www.linkedin.com/in/timlahey
David Joyner
This is very interesting. At first, I was wondering how this could be
possible, as surely reduce would have lots of contributors. The history
suggests that Hearn kept the copyright and allowed others the source code
if they contributed (basically giving them reduce if they gave him
their code). Though surprising, but it really is BSD now it seems.
I agree with Tim - this has some nice packages for DEs. However, it uses
some flavors of lisp I'm not familiar with. Still, there is a binary for
ubuntu amd64 which seems to work so I'll play with it a bit.
Bill Page
implementing a Sage interface for reduce and providing it as an
optional package like FriCAS, but this did not seem to generate much
interest at the time.
http://groups.google.com/group/sage-devel/msg/faa5479477132cab
Reduce is available as part of the axiom-wiki environment and I
personally think it would be great to have it available from within
the Sage Notebook. I have not found enough time recently to devote to
this project but I would be very glad to work with someone else who is
also interested in Reduce.
Reduce was/is quite popular among the theoretical physics community
and was used extensively in subjects like general relativity.
From my limited experience with using Reduce, Maxima and Axiom I would
say that Reduce is more like Maxima than Axiom, being an "un-typed"
symbolic computation system where Axiom is more fundamentally an
"algebraic" system. But Reduce has a more rigorous notion of
"evaluation" than Maxima and literally attempts to "reduce" or
simplify expressions to canonical forms where ever possible.
Reduce, Maxima and Axiom are members of the same generation but
originated in rather different environments. All are written in Lisp.
Reduce is written in a very well documented Lisp dialect called
"Standard Lisp"
http://portal.acm.org/citation.cfm?id=1086782
http://reduce-algebra.com/reduce40.pdf
http://en.wikipedia.org/wiki/Portable_Standard_Lisp
which for the most part is just a subset of what is now called "common
lisp". In principle it is possible to build Reduce using Clisp or even
ECL, but I do not know anyone who has actually done this. See:
http://www.uni-koeln.de/REDUCE/info-package/info-package.html
"Since Standard Lisp includes a limited number of functions, it is
possible to run REDUCE on most modern Lisps, since they contain these
functions as a subset. However, the distributed versions of REDUCE are
based on three easily available Lisps, namely:
* Portable Standard Lisp (PSL). This is currently the Lisp used
most widely for running REDUCE. It evolved from the original Standard
Lisp definition, but now contains many more facilities. It is quite
efficient in its use of both space and time, and has been optimized
for algebraic computation. All PSL versions of REDUCE are distributed
with sufficient PSL support to run on the given computing system. PSL
is supported on many architectures and is an ideal system for those
wanting to run REDUCE as a standalone system. The current principal
developer of PSL is the Konrad Zuse Center, Berlin (ZIB).
* Codemist Standard Lisp (CSL). This is a Lisp system written
completely in ANSI C, which makes it very easy to port to a new
machine. Like PSL, it is a faithful implementation of Standard Lisp
and has been optimized for running REDUCE. It requires a very small
memory partition for its Lisp support. Furthermore, most of the REDUCE
facilities are supported as machine independent pseudocode, which is
quite compact. In the worst case, the performance of this system is
about a factor of two slower than PSL, though in many cases it matches
PSL performance. However, the memory use is smaller. All CSL versions
are distributed with sufficient CSL support to run on the given
computing system. This is an ideal system for those wishing to embed
algebraic calculations in a C-based programming environment. The
developer of CSL is Codemist Ltd. A version with Japanese language
support is also available from Forbs Ltd.
* Common Lisp. This is a Lisp supported by many companies. For the
purposes of running REDUCE, Standard Lisp is supported in Common Lisp
by interface software which defines a Standard Lisp package. Although
the version of REDUCE listed in the table below have only been tested
with AKCL 1.619 and IBUKI Common Lisp respectively, older versions
have run with this interface software in many of the available Common
Lisps.
Common Lisp implementations of REDUCE tend to run slower (often
by more than a factor of three) than PSL-based systems, and require
more memory to run. They are only recommended for those who wish to
embed their algebraic calculations in a Common Lisp environment. Users
of Common Lisp versions of REDUCE are normally required to obtain a
suitable Common Lisp in addition to REDUCE. "
----
http://sourceforge.net/projects/reduce-algebra
I was able to compile the Reduce source package using CSL on Debian
4.0 however it failed to run the complete 'make test-all' suite.
Commits to the svn archive show that open-reduce project developers
like Arthur Norman (also the developer of CSL) are actively working on
correcting these problems.
http://sourceforge.net/users/arthurcnorman
Regards,
Bill Page.
On Sat, Jan 3, 2009 at 7:20 AM, David Joyner wrote:
>
> Thanks very much for this info.
>
> This is very interesting. At first, I was wondering how this could be
> possible, as surely reduce would have lots of contributors. The history
> suggests that Hearn kept the copyright and allowed others the source
> code if they contributed (basically giving them reduce if they gave him
> their code). Though surprising, but it really is BSD now it seems.
>
> I agree with Tim - this has some nice packages for DEs. However, it
> uses some flavors of lisp I'm not familiar with. Still, there is a binary
> for ubuntu amd64 which seems to work so I'll play with it a bit.
>
>
Tim Lahey
On Jan 3, 2009, at 11:29 AM, Bill Page wrote:
>
> We have previously discussed (about 1 year ago) the possibility of
> implementing a Sage interface for reduce and providing it as an
> optional package like FriCAS, but this did not seem to generate much
> interest at the time.
>
> http://groups.google.com/group/sage-devel/msg/faa5479477132cab
>
I think the fact that it wasn't open source had a lot to do with that. I
didn't even look at it until the notice that it was open source now.
Some
of the packages might be useful to me, but I won't know until I try
them.
Having access through Sage would mean that I wouldn't need to learn
Reduce
and I could focus on learning the package instead.
I'm certainly interested in trying things out, but my knowledge of
Reduce
is only what I've glimpsed in the documentation yesterday (so basically
none) and it has been a long time since I've written any Lisp (nearly
20 years).
mabshoff
On Jan 3, 8:48 am, Tim Lahey <tim.la...@gmail.com> wrote:
<SNIP>
> I'm certainly interested in trying things out, but my knowledge of
> Reduce
> is only what I've glimpsed in the documentation yesterday (so basically
> none) and it has been a long time since I've written any Lisp (nearly
> 20 years).
>
> Cheers,
>
> Tim.
binary PSL builds which make the source tarball huge and use csl
instead. Maybe even ecl is an optional, but I have not tried to use it
and likely won't be willing to explore this since I have other things
to do :)
Cheers,
Michael
Jason Grout
> We have previously discussed (about 1 year ago) the possibility of
> implementing a Sage interface for reduce and providing it as an
> optional package like FriCAS, but this did not seem to generate much
> interest at the time.
>
> http://groups.google.com/group/sage-devel/msg/faa5479477132cab
>
> Reduce is available as part of the axiom-wiki environment and I
> personally think it would be great to have it available from within
> the Sage Notebook. I have not found enough time recently to devote to
> this project but I would be very glad to work with someone else who is
> also interested in Reduce.
>
> Reduce was/is quite popular among the theoretical physics community
> and was used extensively in subjects like general relativity.
>
> From my limited experience with using Reduce, Maxima and Axiom I would
> say that Reduce is more like Maxima than Axiom, being an "un-typed"
> symbolic computation system where Axiom is more fundamentally an
> "algebraic" system. But Reduce has a more rigorous notion of
> "evaluation" than Maxima and literally attempts to "reduce" or
> simplify expressions to canonical forms where ever possible.
>
Bill,
It seems that you have more experience with Reduce than most of us here.
How would you generally compare Maxima and Reduce in calculus
functionality, specifically integration? Can you interface with Reduce
on a library level, rather than a tty level? Could this be a short-term
answer to the problems we are having with Maxima?
I wonder how the Matlab folks are feeling now, having bought Mupad to
get a symbolic system. I don't know how Mupad and Reduce compare, though.
Thanks,
Jason
Tim Lahey
On Jan 3, 2009, at 12:48 PM, Jason Grout wrote:
>
> Bill,
>
> It seems that you have more experience with Reduce than most of us
> here.
> How would you generally compare Maxima and Reduce in calculus
> functionality, specifically integration? Can you interface with
> Reduce
> on a library level, rather than a tty level? Could this be a short-
> term
> answer to the problems we are having with Maxima?
>
> I wonder how the Matlab folks are feeling now, having bought Mupad to
> get a symbolic system. I don't know how Mupad and Reduce compare,
> though.
>
If Reduce is an optional package and the integration function is exposed
through the Sage interface, I'll support it in the integration test
suite.
Maxima's integration on the whole isn't too bad. In general, it's faster
than FriCAS. The main problem I have is that it can't return multiple
solutions so it requires assumptions to be set to choose the appropriate
branch if one is calling from Sage. So, I don't know if we really have
a problem with Maxima. However, Maxima and the pynac symbolics aren't
really compatible at the moment so that's a problem.
Cheers,
Tim.
Jason Grout
>
> On Jan 3, 2009, at 12:48 PM, Jason Grout wrote:
>
>> Bill,
>>
>> It seems that you have more experience with Reduce than most of us
>> here.
>> How would you generally compare Maxima and Reduce in calculus
>> functionality, specifically integration? Can you interface with
>> Reduce
>> on a library level, rather than a tty level? Could this be a short-
>> term
>> answer to the problems we are having with Maxima?
>>
>> I wonder how the Matlab folks are feeling now, having bought Mupad to
>> get a symbolic system. I don't know how Mupad and Reduce compare,
>> though.
>>
>
> If Reduce is an optional package and the integration function is exposed
> through the Sage interface, I'll support it in the integration test
> suite.
It seems like an older version of Reduce already is in Wester's test
suite. It'd be nice to see how Reduce 3.8 works too.
Jason
Jason Grout
I found at least one answer. CCL apparently was designed with
interfacing with C in mind. That's a great thing.
Jason
Tim Lahey
On Jan 3, 2009, at 12:58 PM, Jason Grout wrote:
>
> I found at least one answer. CCL apparently was designed with
> interfacing with C in mind. That's a great thing.
I wonder if CCL can compile Maxima and if so, how well Maxima
runs on it.
Cheers,
Tim.
mabshoff
On Jan 3, 10:05 am, Tim Lahey <tim.la...@gmail.com> wrote:
> On Jan 3, 2009, at 12:58 PM, Jason Grout wrote:
> > I found at least one answer. CCL apparently was designed with
> > interfacing with C in mind. That's a great thing.
for example does not go away. I asked Robert Dodier about it at Dev1
and he seemed reluctant about this possibility.
> I wonder if CCL can compile Maxima and if so, how well Maxima
> runs on it.
see any reason to use CCL in Sage - at least it seems to be less
portable than ECL.
> Cheers,
>
> Tim.
Overall I don't think that using Reduce instead of Maxima solves the
problem William raised since it shifts the problem, i.e. we would
still have to deal with Lisp code. And it remains to be seen how
powerful Reduce is. I also looked at the code of Reduce and while some
of it is well documented other parts are not. It also has some decent
size test suite, but at least in some of the files I looked it seemed
that only the computation was run without any checks on whether the
output is correct. They also mention in the documentation that certain
rather large subsystems (like all the floating point "stuff") is not
tested at all. That does not mean that we shouldn't add an interface
to Reduce to Sage, but making it part of the core would require a lot
more diligence IMHO.
Cheers,
Michael
Robert Dodier
> Yes, but you can run Maxima on top of ecl, but the issue with asksign
> for example does not go away. I asked Robert Dodier about it at Dev1
> and he seemed reluctant about this possibility.
Robert Dodier
mabshoff
On Jan 3, 11:27 am, Robert Dodier <robert.dod...@gmail.com> wrote:
> mabshoff wrote:
Hi Robert,
> > Yes, but you can run Maxima on top of ecl, but the issue with asksign
> > for example does not go away. I asked Robert Dodier about it at Dev1
> > and he seemed reluctant about this possibility.
>
> Hmm, what is "this possibility" ? I don't understand.
to the best of my recollection that this would be troublesome due to
asksign since there would be the need on occasion by the user to
interact with the integration/limit calculation - unless I
misunderstood you :)
> Robert Dodier
Cheers,
Michael
Tim Lahey
However, Sage doesn't support giving responses to the questions at this
moment anyway, so I don't see why that's a big problem.
mabshoff
On Jan 3, 11:35 am, Tim Lahey <tim.la...@gmail.com> wrote:
> On Jan 3, 2009, at 2:31 PM, mabshoff wrote:
> > I meant embedding Maxima into a library extensions via ecl. You stated
> > to the best of my recollection that this would be troublesome due to
> > asksign since there would be the need on occasion by the user to
> > interact with the integration/limit calculation - unless I
> > misunderstood you :)
>
> However, Sage doesn't support giving responses to the questions at this
> moment anyway, so I don't see why that's a big problem.
since it is triggered in many unneeded cases, Maxima 5.17.1 introduced
them in some new cases, like now
limit(a*x,x,0);
for example will ask for the sign of a while 5.16.3 did not. That
coupled with some other regressions that were not fixed in 5.17.x at
least convinced me to sit out this Maxima upgrade and see how 5.18.x
(or whatever comes next) fares.
Given a choice between Pan-Axiom, Maxima and Reduce for the role of
symbolic calculus in Sage these days I personally would pick FriCAS
over the other choices. But since all of the above do not solve the
fundamental problem of using pexpect I think that in the long term we
will come up with something on our own, i.e. partially sympy and
partially our own code. That doesn't mean the interface to any
existing system will be removed, just that Maxima would potentially at
some point be made optional - should it ever come to the point where
we have something better.
> Cheers,
>
> Tim.
Cheers,
Michael
Tim Lahey
On Jan 3, 2009, at 2:43 PM, mabshoff wrote:
>
> Given a choice between Pan-Axiom, Maxima and Reduce for the role of
> symbolic calculus in Sage these days I personally would pick FriCAS
> over the other choices. But since all of the above do not solve the
> fundamental problem of using pexpect I think that in the long term we
> will come up with something on our own, i.e. partially sympy and
> partially our own code. That doesn't mean the interface to any
> existing system will be removed, just that Maxima would potentially at
> some point be made optional - should it ever come to the point where
> we have something better.
FriCAS has the problem that in some cases it is very slow. It turns out
that there are many of these slow cases based upon my tests. If Reduce
can support multiple solutions directly and is faster than FriCAS then
it is a viable interim solution. However, I think a native solution is
the preferred approach in the long term.
Cheers,
Tim.
mabshoff
On Jan 3, 11:48 am, Tim Lahey <tim.la...@gmail.com> wrote:
> On Jan 3, 2009, at 2:43 PM, mabshoff wrote:
> > Given a choice between Pan-Axiom, Maxima and Reduce for the role of
> > symbolic calculus in Sage these days I personally would pick FriCAS
> > over the other choices. But since all of the above do not solve the
> > fundamental problem of using pexpect I think that in the long term we
> > will come up with something on our own, i.e. partially sympy and
> > partially our own code. That doesn't mean the interface to any
> > existing system will be removed, just that Maxima would potentially at
> > some point be made optional - should it ever come to the point where
> > we have something better.
>
> FriCAS has the problem that in some cases it is very slow.
fix this? Part of the problem might also be clisp here, so let's see
how for example ecl fares.
> It turns out
> that there are many of these slow cases based upon my tests. If Reduce
> can support multiple solutions directly and is faster than FriCAS then
> it is a viable interim solution.
the other and sorting out all the build issues and even writing the
code takes a considerable amount of man power. If that is going to be
replaced in a year's time (just to throw around a figure) it is much
better in the mean time to "hang in there" with Maxima and concentrate
on our own code and shifting functionality to SymPy in the cases where
it is appropriate.
And re the speed concern: Correctness should come first. As is non of
the solutions seem to be very fast and/or as powerful as MMA in the
average case (I am sure you can find problem classes when Axiom and or
Maxima beat the pants of MMA, but that is likely on average not the
case).
One thing that reduce did very well last time we checked was mv
factorization. Maybe the mv gcd is also very fast, so I think there is
potential there. But unless someone actually goes out, builds a spkg,
tests it on many platforms this is all an academic exercise :)
> However, I think a native solution is
> the preferred approach in the long term.
> Cheers,
>
> Tim.
Cheers,
Michael
Tim Lahey
On Jan 3, 2009, at 2:55 PM, mabshoff wrote:
>
>
>
> On Jan 3, 11:48 am, Tim Lahey <tim.la...@gmail.com> wrote:
>> On Jan 3, 2009, at 2:43 PM, mabshoff wrote:
>
> Hi Tim,
>
>>> Given a choice between Pan-Axiom, Maxima and Reduce for the role of
>>> symbolic calculus in Sage these days I personally would pick FriCAS
>>> over the other choices. But since all of the above do not solve the
>>> fundamental problem of using pexpect I think that in the long term
>>> we
>>> will come up with something on our own, i.e. partially sympy and
>>> partially our own code. That doesn't mean the interface to any
>>> existing system will be removed, just that Maxima would
>>> potentially at
>>> some point be made optional - should it ever come to the point where
>>> we have something better.
>>
>> FriCAS has the problem that in some cases it is very slow.
>
> Ok, can you report them to the FriCAS people so they can potentially
> fix this? Part of the problem might also be clisp here, so let's see
> how for example ecl fares.
>
However, Maxima is running under the same lisp, so it isn't just that.
Anybody can run the suite and get the timings so it's fairly easy to see
which integrals are slow and which aren't. I'll post complete timings
once
I've finished all the integrals.
>> It turns out
>> that there are many of these slow cases based upon my tests. If
>> Reduce
>> can support multiple solutions directly and is faster than FriCAS
>> then
>> it is a viable interim solution.
>
> Well, interim is a bad, bad word :). Seriously, switching from one to
> the other and sorting out all the build issues and even writing the
> code takes a considerable amount of man power. If that is going to be
> replaced in a year's time (just to throw around a figure) it is much
> better in the mean time to "hang in there" with Maxima and concentrate
> on our own code and shifting functionality to SymPy in the cases where
> it is appropriate.
>
I understand that. I was speaking more from a perspective of FriCAS
vs. Maxima vs. Reduce. If we were to switch away from Maxima to another
Lisp package, I think it should be based upon correctness and
performance. Right now, based upon the tests I've done, aside from the
questions, Maxima's correctness appears to match FriCAS and on average
has better performance.
> And re the speed concern: Correctness should come first. As is non of
> the solutions seem to be very fast and/or as powerful as MMA in the
> average case (I am sure you can find problem classes when Axiom and or
> Maxima beat the pants of MMA, but that is likely on average not the
> case).
Maxima and FriCAS aren't too bad at integration, but I don't know how
Mathematica compares. I have Maple 11 and 12, so once the Maple
interface
is fixed, I'll definitely test Maple against the suite.
>
>
> One thing that reduce did very well last time we checked was mv
> factorization. Maybe the mv gcd is also very fast, so I think there is
> potential there. But unless someone actually goes out, builds a spkg,
> tests it on many platforms this is all an academic exercise :)
>
True. I'm hoping that Reduce is an option, because I definitely want to
try some of the packages. If not, I might look at porting some of them
once I finish my thesis.
Cheers,
Tim.
Robert Dodier
important.
Instead let me spell out my current thoughts about the situation.
Maxima + ECL seems to work OK at this point so I guess you could
indeed link in Maxima via CFFI or some other C interface.
(Although there are two layers of glue here, right? Lisp -> C and
C -> Python; seems like it could be messy.)
asksign would presumably still interfere, but it wouldn't
be any more of problem than it is now.
About disabling asksign, I made an attempt to do that in a non-
intrusive
way, by having asksign throw an exception back to a high-level
handler which could construct a conditional expression.
(The code is in share/contrib/noninteractive/.) That sort of works,
except that it clogs up the assume system (which eventually
stops working). Also, the scheme inherits assume's weakness.
So at this point I think it would be necessary to revise every
call to asksign to construct a conditional expression when asksign
is disabled. That would be tedious --- there are something like 100
calls to asksign or similar functions throughout the core code ---
but it seems straightforward. I might try to work on that in 2009.
FWIW
Robert Dodier