Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
14  
Should this be community wiki? –  Federico Poloni May 15 '11 at 12:37
1  
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
1  
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
1  
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
1  
@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
show 7 more comments

6 Answers

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.

share|improve this answer
add comment

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.
share|improve this answer
add comment

My favorite trick in experimental mathematics is to prove things.

share|improve this answer
add 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)}}$

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
1  
Matlab's $/$ and $\backslash$ operators are sort of an example of this. –  Nate Eldredge May 15 '11 at 12:42
2  
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
5  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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