30
$\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.)

$\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$ 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$ 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$ 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
    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$ Jun 22, 2011 at 7:45

6 Answers 6

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.

$\endgroup$
6
  • 2
    $\begingroup$ Matlab's $/$ and $\backslash$ operators are sort of an example of this. $\endgroup$ 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$ 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$ 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$ 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$ May 15, 2011 at 17:43
9
$\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.
$\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)}}$

$\endgroup$
4
$\begingroup$

My favorite trick in experimental mathematics is to prove things.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.