SciPy talk

[Aaron Meurer]

Here is the detailed abstract I have so far for a talk for SciPy. Any suggestions are welcome. The deadline is April 1 (probably 5 PM central or thereabouts). I roughly based it on the matplotlib talk from last year http://conference.scipy.org/scipy2013/presentation_detail.php?id=211.

Symbolic computation deals with manipulating mathematical expression symbolically (as opposed to numerically). For instance, representing sqrt(2) without evaluating it is symbolic: representing 1.41421 is numeric. Most software that deals with mathematical expressions symbolically are called computer algebra systems, or CASs for short. SymPy is a computer algebra system written entirely in Python.  

In this talk, we will look at

- Why you should care about symbolic mathematics. Even if you are only interested in doing numerics, how can symbolic mathematics help you to solve your problems more efficiently and/or effectively?

- Some of the design decisions that have guided SymPy, such as why we chose Python to write SymPy, and the importance of being able to use SymPy as a library. 

- How to solve some basic problems in SymPy.

- How to interface SymPy with popular numeric libraries, like NumPy.

Additionally, we will look at the most interesting recent developments of SymPy, and will also discuss some of our plans for the future. 

Finally, we will discuss some of what has made SymPy a success, both as a software product, and as a community.

Aaron Meurer

[Matthew Rocklin]

I like that you emphasized the utility for numerics, I think that this is likely to be a selling point for the SciPy crowd.  I think that it's correct to inform the reader about what symbolics are but I think that the first couple of sentences (which do this) could be stronger/more direct.  Right now they sound conversational.  It's not clear to me how to fix this though. 

Maybe start with something like "SymPy is a computer algebra system.  It provides easy access to a wealth of automated mathematics that helps programmers to reason about their problem producing more clear and efficient numeric solutions."  and then go into what symbolics are?

I would cut the top bullet point, e.g.

- Why you should care about symbolic mathematics, even if you are only interested in doing numerics.

- How symbolic mathematics can help you solve problems more effectively

I have a pretty cynical view about people when they're reading text though (perhaps this comes from teaching freshmen :))  As a result sentences that carry more than one idea seem dirty to me.

Hope this helps,

-Matt

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.
To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6K3OmDsdApN%3DOEvFrRQ4ohEQ1npVfwgUsyxd-K-TLaLOA%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.

[Matthew Rocklin]

Last minute (this morning) I decided to submit a talk based around some of my more esoteric programming projects, multiple dispatch, pattern matching, strategies.  I drew a lot of inspiration from SymPy when I was thinking about these things so if accepted then I'll probably use SymPy heavily for example use cases.  Here is the description and abstract.

I'll add a disclaimer to this talk that the ideas contained within it are my own and not necessarily adopted by the SymPy community.  As I said, this is mostly about some of my more wacky projects.  I'll probably call upon uses of multiple dispatch (if we include it), fu trig simplification with @smichr, and my matrix expressions work with pattern matching (not in master). 

Description

Good solutions to hard problems require both domain and algorithmic expertise. Domain experts know what to do and computer scientists know how to do it well. This talk discusses challenges and experiences trying to reconcile these two groups, particularly within SymPy. It proposes concrete approaches including multiple dispatch, pattern matching, and programmatic strategies.  

Abstract

Good solutions to hard problems require both domain and algorithmic expertise. Domain experts know what to do and computer scientists know how to do it well. Coordination between the algorithmic and domain programmer is challenging to do well and difficult to scale. It is also arguably one of the most relevant blocks to scientific progress today.

This talk draws from experience supporting mathematical programmers in the SymPy project. SymPy is a computer algebra system, a complex problem that requires the graph manipulation algorithms of a modern compiler alongside the mathematics of several PhD theses. SymPy draws from a broad developer base with experienced and novice developers alike and so struggles to maintain a cohesive organized codebase.

We approach this development problem by separating software engineering into a collection of small functions, written by domain experts, alongside an abstract control system, written by algorithmic programmers. We facilitate this division with techniques taken from other languages and compiler technologies. Notably we motivate the use of a few general purpose libraries for multiple dispatch, pattern matching, and programmatic control.

[Aaron Meurer]

On Mon, Mar 31, 2014 at 11:32 AM, Matthew Rocklin <mroc...@gmail.com> wrote:

I like that you emphasized the utility for numerics, I think that this is likely to be a selling point for the SciPy crowd.  

Yes, this was very intentional. I may need some help gathering up some nice motivating examples if this is accepted. 

 

I think that it's correct to inform the reader about what symbolics are but I think that the first couple of sentences (which do this) could be stronger/more direct.  Right now they sound conversational.  It's not clear to me how to fix this though. 

 

Maybe start with something like "SymPy is a computer algebra system.  It provides easy access to a wealth of automated mathematics that helps programmers to reason about their problem producing more clear and efficient numeric solutions."  and then go into what symbolics are?

Except not all problems will eventually be numeric (though maybe for this community they are). 

Also, problem modeling is not the only use of SymPy. I think presenting just that maybe turns away some people who don't care about solving "new problems" in a mathematical sense. For many (most?) people, SymPy is just a really good bookkeeper, which doesn't make stupid sign errors and handles a one-line equation as seamlessly as a 20 line equation. 

 

I would cut the top bullet point, e.g.

- Why you should care about symbolic mathematics, even if you are only interested in doing numerics.

- How symbolic mathematics can help you solve problems more effectively

I have a pretty cynical view about people when they're reading text though (perhaps this comes from teaching freshmen :))  As a result sentences that carry more than one idea seem dirty to me.

OK. I had actually planned to expand all the bullet points to be longer, but I could only think of something to write for the first one :)

I did split it out as I did intentionally, though. The thought in my mind was something like: "why should I care about symbolic mathematics" (the person reads), thinks to him/herself "I don't, I just do numeric things", and then the next bullet addresses that exact thought.

Here's an updated draft. Comments are still welcome, even if I don't get to them by the deadline.

Symbolic computation deals with manipulating mathematical expression symbolically (as opposed to numerically). For instance, representing sqrt(2) without evaluating it is symbolic: representing 1.41421 is numeric. Most software that deals with mathematical expressions symbolically are called computer algebra systems, or CASs for short. SymPy is a computer algebra system written entirely in Python. 

In this talk, we will look at

- Why you should care about symbolic mathematics? 

- Even if you are only interested in doing numerics, symbolic mathematics can help you to solve your problems more efficiently and effectively. Computer algebra systems can be useful for two main purposes, modeling your problem at a higher level, in order to gain some deeper mathematical understanding, and doing mathematical "bookkeeping", which is preferable to doing things by hand because it avoids mistakes and scales even to mathematical expressions that are too large to handle by hand. 

- Some of the design decisions that have guided SymPy, such as why we chose Python to write SymPy, and the importance of being able to use SymPy as a library. 

- How to solve some basic problems in SymPy.

- How to interface SymPy with popular numeric libraries, like NumPy. We will also look at how to use SymPy to generate fast C or Fortran code.

Aaron Meurer

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAJ8oX-EKtRvNmb8SnyAxUaV%3D3m3_%3D2kfe%3D%3DKRsPKj13_bUSBOA%40mail.gmail.com.

[Aaron Meurer]

I like this talk. It sounds similar to the talks you gave last year. 

I've really been sold on this approach in the assumptions system, a la my branch. In the old assumptions and the current new assumptions, to write down a fact, you have to do a lot of logic. You maybe don't need to know the details of how ask() works, but you do need to think about both the fact that you want to implement (say, product of even integers is even), *and* how to write that down so that it works in the system (e.g., an _eval_even in Mul that says "if all(i.is_integer for i in self.args): return all(i.is_even for i in self.args)", or the crazy mess you'd have to write in the new assumptions handlers). In my branch, you just write

(Mul, Implies(AllArgs(Q.integer), Equivalent(AnyArgs(Q.even), Q.even))),

Maybe that is less readable than the old assumptions example I had (although once you get the hang of how the logic works, it really isn't), but there are two advantages:

- It's symbolic. You can reason things about the (Mul, Implies(...)), version that you can't reason about the if all(...) version (e.g., ask(Q.even(x) | Q.even(y), Q.even(x*y) & Q.integer(x) & Q.integer(y))). You can also do fun things like ship it off to something else (maybe auto generate docs for all assumptions facts, or maybe dump all assumptions facts to prolog and see where you can get with that...).

- It doesn't *have* to be less readable. That's just the syntax I came up with. You can keep building higher and higher abstractions. Maybe the Implies(AllArgs(something), Equivalent(something else)) pattern is a common one (it is), and thus should be abstracted somehow.  If you want to restructure the old assumptions like this, you'd have to build a completely new pattern in the assumptions itself (like some new method _eval_x_for_domain_y or something). To build it in my branch, just write some new classes (maybe ForDomain(something, Equivalent(something else))). As long as your classes know how to spit out actual logic in the end (or actually, just how to spit out things in terms of lower abstractions really), they can abstract things however they like . And they don't have to touch the core deduction system, or really even care that it exists.

The point is, with the old ways, you have to figure out, "how do I make deductions on this fact", whereas with the new way, you just have to figure out, "how do I write down this fact" (and note that the latter is really a prerequisite for doing *anything* with the fact, even understanding it). 

Sorry if I don't have any suggestions for you talk abstract, other than "hey, give a shoutout to assumptions too."

I guess my other suggestion would be that data should be data, and whenever it can be represented symbolically, it should be. You never know what kinds of manipulations someone might want to do with the knowledge you have written down. Maintaining the exact structure of it is your best bet.

Aaron Meurer

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAJ8oX-Ei01ZAgWSJmb2Cdm6Q%2BOovh4L4C25c7p2PwQc2shB5qw%40mail.gmail.com.

[Tim Lahey]

On 31 Mar 2014, at 20:29, Aaron Meurer wrote:

> On Mon, Mar 31, 2014 at 11:32 AM, Matthew Rocklin
> <mroc...@gmail.com>wrote:
>
>> I like that you emphasized the utility for numerics, I think that
>> this is
>> likely to be a selling point for the SciPy crowd.
>>
>
> Yes, this was very intentional. I may need some help gathering up some
> nice
> motivating examples if this is accepted.

One motivating example for me is the integration of products of
functions over areas and volumes. For finite elements, you'll get
products of pairs of trial functions (usually polynomials). It's even
more useful for products of trig functions. Performing the integration
of any of theses is easy enough with numerical integration, but it's
much more efficient to calculate the integrals symbolically and then
perform the evaluation for each element.

Cheers,

Tim.

[Aaron Meurer]

That's a good point. One of the nicest things about symbolics, when you can get it, is that it can make things drastically more efficient by doing mathematical simplifications. Evaluating integrals symbolically is a nice example of this (especially for SymPy, which has some pretty nice algorithms to compute definite integrals). 

I'm reminded of a popular blog post (I can't find a link right now) about how know math is important for programmers. It has the example of how all these programming languages show how they they compute factorial, and how tail recursion can make it linear or whatever, but the actual best way to compute it is to use loggamma, which gives the answer in constant time. 

Aaron Meurer

--
You received this message because you are subscribed to the Google Groups "sympy" group.

To unsubscribe from this group and stop receiving emails from it, send an email to sympy+unsubscribe@googlegroups.com.

To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/AE5C61B5-8C69-49AE-BAFF-85E5AC924F8F%40gmail.com.

[Matthew Rocklin]

http://www.evanmiller.org/mathematical-hacker.html

I reference that blog post pretty often.  I fully intend to reference it again in my talk (if it is accepted).

The interesting thing about the Factorial / Gamma / loggamma example is that to find the solution you need to find someone who knows both that n! = Gamma(n+ 1) and who knows that a loggamma routine is commonly found in lower level languages.  Those bits of information are usually held by different experts.  Ondrej said "Of course, that's obvious" when I first reposted the article on G+.

You're right that this is similar to my last talk.  The last one though was mostly about an application (numerical linear algebra).  I actually want to talk a bit more about the philosophy and some of the more abstract tools that people might actually use.  Your first impression is a valuable one though, I should go through my last talk and make sure that I'm not repeating too much that shouldn't be repeated.

To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.

To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6K8F9weBP-7yjpzrN9hQ5FR54TK_QdCPqbzBdwo20zKdg%40mail.gmail.com.

[Matthew Rocklin]

And regarding assumptions I agree with everything that you said.

[Ondřej Čertík]

On Mon, Mar 31, 2014 at 9:14 PM, Matthew Rocklin <mroc...@gmail.com> wrote:
> http://www.evanmiller.org/mathematical-hacker.html
>
> I reference that blog post pretty often. I fully intend to reference it
> again in my talk (if it is accepted).
>
> The interesting thing about the Factorial / Gamma / loggamma example is that
> to find the solution you need to find someone who knows both that n! =
> Gamma(n+ 1) and who knows that a loggamma routine is commonly found in lower
> level languages. Those bits of information are usually held by different
> experts. Ondrej said "Of course, that's obvious" when I first reposted the
> article on G+.

That's funny, I forgot that I said that and just had the same reaction.

However, we are still missing rational function approximation in SymPy
or mpmath.
That's what is used to implement things like log_gamma or erf (error
function) in
Fortran or C. So I have just created an issue for it:

https://github.com/sympy/sympy/issues/7359

and I spent time explaining exactly how it works in it and giving examples,
including for example the implementation of erf() in gfortran.

Aaron, you were asking about examples of numerical cancellation. I
worked out one in the
issue as well.

Ondrej

>>> email to sympy+un...@googlegroups.com.
>>> To post to this group, send email to sy...@googlegroups.com.
>>> Visit this group at http://groups.google.com/group/sympy.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msgid/sympy/AE5C61B5-8C69-49AE-BAFF-85E5AC924F8F%40gmail.com.
>>>
>>> For more options, visit https://groups.google.com/d/optout.
>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "sympy" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to sympy+un...@googlegroups.com.
>> To post to this group, send email to sy...@googlegroups.com.
>> Visit this group at http://groups.google.com/group/sympy.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/sympy/CAKgW%3D6K8F9weBP-7yjpzrN9hQ5FR54TK_QdCPqbzBdwo20zKdg%40mail.gmail.com.
>>
>> For more options, visit https://groups.google.com/d/optout.
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sympy/CAJ8oX-HZABscP43PDuoAeWhcpBYW2w39G8qPx0%2BZCbKcYbJdJg%40mail.gmail.com.

[Aaron Meurer]

FYI, my SciPy talk for SymPy was not accepted (it was accepted for the
poster session). My talk on conda was accepted, as was the SymPy
tutorial.

Aaron Meurer

> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CADDwiVCXMe1zA53fyuoNO%2BaWO2mFqjjfYUNzAtAOSTuJE5N5Jw%40mail.gmail.com.

[Richard Fateman]

I think your arguments are weak, though given the audience, perhaps they would be appealing.

Here's what I think constitute good arguments for people to know about CAS. Maybe even sympy.

1. Scientists, mathematicians and programmers all have a rich language and context for
discussing the solution of difficult problems.  Users of traditional numerical computation
much couch their solutions in terms of objects that are floating-point numbers or collections of
them such as matrices

2. Symbolic computation allows for a much broader class of objects, and supports
the manipulation of formulas, algebraic equations,
differential equations, series, geometric descriptions, and more.

As a simple example, solution of the quadratic equation in s,  s^2+(a/n)*(n^2-1)*s -a^2=0
can be easily expressed, and trivially solved in a CAS to find the solutions s=-a*n and s=a/n.
The presence of extra parameters (a,n) in the problem and the solution would pose difficulties
for a numeric solution.

3. Many algorithms of applied mathematics, usually portrayed in references and texts as appropriate
for "hand calculation"  can in fact be encoded in symbolic form, using formulas as input and output.
Famously, these include symbolic integration, differentiation, expansion in series, summation.

4. Routines may be written which, through symbolic manipulation, produce specialized versions
of algorithms tailored to tasks which themselves be numeric, but whose programming "by hand"
would be too laborious and error-prone to seriously consider. As examples, super-accurate
programs for scientific subroutine libraries have been developed.

5. CAS can be used to symbolically execute and prove the correctness of algorithms that
might otherwise be challenges to understand.

6.  And more...

[Ondřej Čertík]

Hi Richard,

Thanks for the points. I agree with them.

Aaron, I think lots of talks were rejected from this year's SciPy
conference. Are you going to prepare a poster?

Ondrej

[Aaron Meurer]

Probably, if I have time. Help is appreciated. Also I have no idea how
to do that.

Aaron Meurer

>
> Ondrej

>
> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CADDwiVBGTnrK_Dqr2NXH3B-QRWFwO69Tezu4UZaUwTKV4m%2Bvrw%40mail.gmail.com.

[Richard Fateman]

On Tuesday, April 1, 2014 2:58:34 PM UTC-7, Ondřej Čertík wrote:

On Mon, Mar 31, 2014 at 9:14 PM, Matthew Rocklin <mroc...@gmail.com> wrote:
> http://www.evanmiller.org/mathematical-hacker.html
>
> I reference that blog post pretty often.  I fully intend to reference it
> again in my talk (if it is accepted).

That's unfortunate.  I was totally unacquainted with Evan Miller.  I read this particular
blog entry.  I did not follow any of the links, but I think that the essay is a piece of crap.
It is uninformed, shallow, and, I daresay, just wrong.  I hope you re-think referring to it.

 

>
> The interesting thing about the Factorial / Gamma / loggamma example is that
> to find the solution you need to find someone who knows both that n! =
> Gamma(n+ 1) and who knows that a loggamma routine is commonly found in lower
> level languages.  Those bits of information are usually held by different
> experts.  Ondrej said "Of course, that's obvious" when I first reposted the
> article on G+.

Well, let me quote from the article..
"
if it is ever necessary to compute a factorial, a programmer should be taught to take advantage of the system's log-gamma function, as the following C code does:

long int fac(unsigned long int n) {
    return lround(exp(lgamma(n+1)));
}

Again, no recursion is required as long as one...

Here are a few things that are wrong. Rounding an approximate floating point
number to a integer may not get you the exact integer factorial you want.
The program will certainly not work for arbitrary unsigned long int n because
the exp() will overflow. Say certainly by n=175.
If you want a floating-point approximation to any factorial that can be
represented as an IEEE double, you could do it by checking if N<175 and
then index into an array of length 175.  [I'd check that 175 more carefully
if I were really doing this.  And the number would change a little for 64-bit ints.

If you want exact integer factorials on a 32 bit computer, you only need an array of 12, since
13! > 2^32.

So the program is stupid.  Why?  Because the author is mathematically
and computationally ignorant.  (And seemingly quite full of himself.)

Say you want to solve the much more interesting problem of computing factorials
of any size integer.  Then you might see
http://www.luschny.de/math/factorial/FastFactorialFunctions.htm
which tells how it might be done better.

Here's a far superior factorial, in lisp, and yes it is recursive.  I suppose you
could write it iteratively, but why bother. A Lisp compiler will do that for you.

(defun fact(n)(f n 1))

 (defun f (n m) (if (<= n 1) 1 (* n (f (- n m) m))))

It is used in some computer algebra systems.


The snide characterizations that lisp programmers know more or less mathematics
or that what they know is more or less relevant is just junk.

Of the 3 people quoted -- Raymond, Graham, Yegge...
I've never heard of Yegge; I think that Graham is smart, and Raymond just says things
to be, uh, smart-ass. 




 

[Rathmann]

Well, I wouldn't have used such colorful language, but I share

Prof. Fateman's skepticism on the utility of lgamma for computing

factorials.

I tried the expression as given, (see attachment, if you want to try

yourself or point out errors) and it begins to diverge from the correct

value at n=17 (which is a bit more than 48 bits for the integer).

Interestingly, if I switch to gamma(), instead of exp(lgamma()), it

doesn't diverge until n=23, which corresponds to a 75 bit number.

(Presumably there are a lot of zeros at the bottom of a factorial.)

So, that would work if you were in C and restricted to 64 bit long

longs.  But, as Fateman points out, with that restriction you might as

well keep a short table.

Of course, in Python we expect thousands of bits to work

transparently, so I would definitely avoid converting from lgamma to

an int.

BTW, I don't understand the "far superior" implementation of fact

later in the posting.  When I try it, I just get regular linear

recursion.  Presumably there is a typo in my translation or in the

original posting.

[Richard Fateman]

Gee, this is getting long.

Here's the deal on the improved factorial.  Perhaps you just haven't
gotten large enough, or your multiplications are too slow, even for small numbers.
Or there is something else odd about your program that I don't see. Certainly n=20 is way too small
to be interesting.  You haven't even gotten  to get to places where "fast" methods of integer multiplication
are better than naive methods.

  If you read the post by Peter L. it will explain more, and you might find it interesting
that to get much better in computing fact(n), his best method ends up factoring the integer n, first.  At least
that's what I recall.

So the question is, if that 2-argument factorial still does linear recursion, what's the payoff?

Here's the payoff.
multiplying  a  (small) integer j by a  (long, multi-word) arbitrary precision integer  k takes time
essentially  O(size(k)).  It gets to your goal faster if the small integer is as large as possible
and still a small integer.

Do you want to do

 big2= 12* small
big3= 13* big2
big4 =14* big3
big 100 =  110*  big99      at a cost of  100  small X big multiplies?

or do you want to do
 small2= 12* 13
small3 = small2*14
small4= small3* 14
....   mostly small arithmetic for a while...

and then do big ones for a while.    at a cost of  N small multiplies, and   fewer big multiplies.




.....    etc

Have fun.

RJF

[Rathmann]

Right, balancing the multiplication tree can be a win, for the reasons you give.

But, I don't think your code snippet is doing any of that.  If I run a version (attached) that prints out the multiplies it evaluates, (fact 100) gives:

(2 . 1) 

(3 . 2) 

(4 . 6) 

(5 . 24) 

(6 . 120) 

(7 . 720) 

(8 . 5040) 

. . .

(100

 . 933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000)

[Richard Fateman]

You are right!  So sorry!  I copied the wrong program into my note.

Here is a correct version.   (Again, Peter's article is fun to read...)

 (defun ff(n m) (if (<= n m) n (*(ff n (+ m m))(ff (- n m) (+ m m)))))

For this one,  (ff 10 1) computes 10! and
does the following multiplications.

 (ff 10 1)

(* 10 2)
 (* 20 6)
 (* 8 4)
 (* 120 32)
 (* 9 1)
 (* 9 5)
 (* 7 3)
(* 45 21)
 (* 3840 945)

3628800

The effect is far more pronounced for 100!.  There are other fun hacks though.
I hope you have the time and interest to try this on python.
RJF

[Rathmann]

Thanks -- this one makes sense.  (It is shuffles the multiplications into a balanced tree so that the top-level multiplication is the product of all the odds (<=n) times the product of the evens.)

Sympy itself uses prime swing.