31
$\begingroup$

There are a few computational tricks which are useful in experimental mathematics. These tricks are mostly very elementary and often only given as exercices in books. A typical example is the following:

Suppose that a sequence $s_0,s_1,s_2,\dots$ converges exponentially fast. Then the sequence $t_i=s_i-\frac{(s_{i+1}-s_i)^2}{s_{i+2}-2s_{i+1}+s_{i}}$ converges (generally) faster and has the same limit. Having only access to a few initial terms of a sequence which seems to converge quickly, this trick improves thus guesses concerning the limit.

This suggests two questions:

  1. Is there a nice book/article containing a list of useful tricks "ready for use"?

  2. What tricks are useful for you?

For clarity let me state that I do not count Euclid's algorithm, LLL or such things as tricks. they are already implemented and ready for use in computer-algebra systems. (A nice book concerning tricks might have however also ulterior chapters mentioning such useful algorithms and describing them very briefly.)

Improve this question
$\endgroup$
10
  • $\begingroup$ Doron Zeilberger teaches a class called "experimental mathematics" which has seen several iterations: some of his material might be useful (math.rutgers.edu/~zeilberg/teaching.html). $\endgroup$
    – Qiaochu Yuan
    Commented May 15, 2011 at 12:21
  • $\begingroup$ The Aitken $\Delta^2$ process you mention for accelerating the convergence of linearly convergent sequences can be generalized to the so-called "Shanks transformation"; see math.stackexchange.com/questions/35980/36066#36066 where I used the Shanks transformation and Richardson extrapolation to determine the numerical plausibility of a purported limit. $\endgroup$
    – J. M. isn't a mathematician
    Commented May 15, 2011 at 14:06
  • 1
    $\begingroup$ P.S. Mathematica is able to do the Aitken "trick", but the function does not seem to be explicitly advertised. Try SequenceLimit[(*sequence*), Method -> {"WynnEpsilon", "Degree" -> 1}] $\endgroup$
    – J. M. isn't a mathematician
    Commented May 15, 2011 at 14:12
  • 1
    $\begingroup$ I am disappointed with this question after reading the title. I would much prefer this being about how to gain insight into a non-trivial mathematical fact by doing an "experiment" than how to evaluate expressions numerically (there are huge books about this). E.g. how do I spot the prime number theorem by staring at a table of primes? $\endgroup$
    – Helge
    Commented Jun 21, 2011 at 18:35
  • 1
    $\begingroup$ @Helge: I fear (or hope) that there is no method for doing such a thing: If the discovery of an interesting mathematical fact were entirely algorithmic (or based on few useful tricks), it would be much less fun. $\endgroup$
    – Roland Bacher
    Commented Jun 22, 2011 at 7:45

6 Answers 6

Reset to default
11
$\begingroup$

I am not sure what counts as a trick and what doesn't, but I'd like to suggest

Don't invert matrices!

In nearly all practical applications, solving a linear system is faster and more accurate than computing the inverse entry-by-entry.

Unfortunately, I know no computer algebra system that takes advantage of this bit of wisdom and implements inversion as returning a proxy.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ Matlab's $/$ and $\backslash$ operators are sort of an example of this. $\endgroup$
    – Nate Eldredge
    Commented May 15, 2011 at 12:42
  • 2
    $\begingroup$ Uh, that's not the same thing. For instance, if I have to solve two linear systems with the same matrix, A\b;A\c is inefficient because it computes the LU factorization twice. On the other hand, if inv(A) computed an LU factorization and returned a proxy, then inv(A)*b and inv(A)*c would be both solved with the superior method, without hassle. And you wouldn't have to teach the engineers not to use inv(A). $\endgroup$
    – Federico Poloni
    Commented May 15, 2011 at 13:15
  • $\begingroup$ Federico is right; presumably Moler and company had enough sense to have "backslash" perform a decomposition as opposed to an explicit inversion. $\endgroup$
    – J. M. isn't a mathematician
    Commented May 15, 2011 at 14:24
  • $\begingroup$ Sorry, small mistake: if inv returned a proxy, then one would have to write T=inv(A);T*b;T*c in order to solve two systems with one LU factorization. inv(A)*b;inv(A)*c doesn't work since the function inv is called twice. $\endgroup$
    – Federico Poloni
    Commented May 15, 2011 at 14:30
  • 7
    $\begingroup$ As a matter of course: Mathematica 's LinearSolve[] (at least in the new versions) accepts a square matrix as the only argument, returning a LinearSolveFunction[] object that can then be applied to various vectors (as expected, a compactly stored LU decomposition is embedded within the object)... $\endgroup$
    – J. M. isn't a mathematician
    Commented May 15, 2011 at 17:43
10
$\begingroup$

The tricks I regularly use:

  • Create more examples. Always.
  • As a corollary of the above, time is well spent on making algorithms that presents examples nicely.
  • The Online Encyclopedia of Integers (OEIS), is your friend.
  • Or, if that does not work, put your sequence or constant into WolframAlpha.
  • If the numerical data looks strange, redo! Some software do not warn when the precision is lost. Some software (Mahtmematica for example), do not consider $1/2$ and $0.5$ to be equal.
  • Take time to learn your software! You are more tempted to try new stuff, if it is easy to code.
Improve this answer
$\endgroup$
6
$\begingroup$

If you are attempting to guess the solution of a problem that is a number and the usual tricks (LLL or PSLQ) don't work, you can try to introduce an extra parameter in the problem, making the solution a function of that parameter. Then, you can study that function numerically. In some cases it is then possible to guess this function based on its behavior, which then solves the original problem.

E.g., for the critical percolation problem on a cylinder of circumference L, it had been conjectured using numerical work that the probability that a point is on a cluster that wraps around the cylinder has the asymptotic behavior of 0.81099753.... L^(-5/48), see here. Then guessing an analytic expression for the number 0.81099753.... was only possible when considering a generalized version of the original problem that has an extra parameter in it and then guessing the function of that parameter. That then led to this result from which the conjecture follows that $0.81099753\ldots = \frac{2^{23/72}}{3^{5/48}}\frac{\pi^{1/4}\exp\left(1/4 \zeta'(-1)\right)}{\sqrt{\Gamma\left(1/4\right)}}$

Improve this answer
$\endgroup$
4
$\begingroup$

My favorite trick in experimental mathematics is to prove things.

Improve this answer
$\endgroup$
2
$\begingroup$

I can't respond to Federico's comment directly but I want to point out that you could (in principle!) solve two (or more systems) as: blkdiag(A,A)\[b;c]. HOWEVER it seems that matlab doesn't know enough to exploit the block diagonal structure and this runs slower that precomputing the inv. However, it may have higher numerical accuracy (not sure).

% generate random large A,b,c
% A=sparse(A); % make things a bit more "fair"

>> tic;A\b;A\c;toc
Elapsed time is 0.035227 seconds.

>> A=blkdiag(A,A);
>> tic;A\[b;c];toc
Elapsed time is 0.060273 seconds.

One "trick" that I live by is: exploit Matrix structure. This means understanding the alphabet soup of factorization techniques and when to use each one and why.

Improve this answer
$\endgroup$
2
$\begingroup$

For the first question ("is there a nice book/article..."), I think the answer ie Yes: Sanjoy Mahajan's Street-Fighting Mathematics, which also exists in a free CC version, summarizes a good number of useful tricks and meta-tricks, some well-known, some less so.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .