# Useful tricks in experimental mathematics

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.)

-
Should this be community wiki? –  Federico Poloni May 15 '11 at 12:37
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}] –  J. M. May 15 '11 at 14:12
Because the question has no single definite answer but rather a "big-list" style set of answers, it probably merits transition into the "community wisdom" mode... :-) –  Suvrit May 15 '11 at 14:13
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? –  Helge Jun 21 '11 at 18:35
@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. –  Roland Bacher Jun 22 '11 at 7:45

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.

-
Matlab's $/$ and $\backslash$ operators are sort of an example of this. –  Nate Eldredge May 15 '11 at 12:42
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). –  Federico Poloni May 15 '11 at 13:15
Federico is right; presumably Moler and company had enough sense to have "backslash" perform a decomposition as opposed to an explicit inversion. –  J. M. May 15 '11 at 14:24
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. –  Federico Poloni May 15 '11 at 14:30
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)... –  J. M. May 15 '11 at 17:43
show 1 more comment

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)}}$

-

My favorite trick in experimental mathematics is to prove things.

-

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.

-

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.
-