MATHEMATICA TUTORIAL

The Limits of Mathematica

In just one Mathematica command, you can easily specify a calculation that is far too complicated for any computer to do. For example, you could ask for Expand[(1+x)^(10^100)]. The result of this calculation would have terms—more than the total number of particles in the universe.

You should have no trouble working out Expand[(1+x)^100] on any computer that can run Mathematica. But as you increase the exponent of , the results you get will eventually become too big for your computer's memory to hold. Exactly at what point this happens depends not only on the total amount of memory your computer has, but often also on such details as what other jobs happen to be running on your computer when you try to do your calculation.

If your computer does run out of memory in the middle of a calculation, most versions of Mathematica have no choice but to stop immediately. As a result, it is important to plan your calculations so that they never need more memory than your computer has.

Even if the result of an algebraic calculation is quite simple, the intermediate expressions that you generate in the course of the calculation can be very complicated. This means that even if the final result is small, the intermediate parts of a calculation can be too big for your computer to handle. If this happens, you can usually break your calculation into pieces, and succeed in doing each piece on its own. You should know that the internal scheme that Mathematica uses for memory management is such that once part of a calculation is finished, the memory used to store intermediate expressions that arose is immediately made available for new expressions.

Memory space is the most common limiting factor in Mathematica calculations. Time can also, however, be a limiting factor. You will usually be prepared to wait a second, or even a minute, for the result of a calculation. But you will less often be prepared to wait an hour or a day, and you will almost never be able to wait a year.

The internal code of Mathematica uses highly efficient and optimized algorithms. But there are some tasks for which the best known algorithms always eventually take a large amount of time. A typical issue is that the time required by the algorithm may increase almost exponentially with the size of the input. A classic case is integer factorization—where the best known algorithms require times that grow almost exponentially with the number of digits. In practice, you will find that FactorInteger[k] will give a result almost immediately when has fewer than about 40 digits. But if has more than 70 digits, FactorInteger[k] can start taking an unmanageably long time.

In some cases, there is progressive improvement in the algorithms that are known, so that successive versions of Mathematica can perform particular computations progressively faster. But ideas from the theory of computation strongly suggest that many computations will always in effect require an irreducible amount of computational work—so that no fast algorithm for them will ever be found.

Whether or not the only algorithms involve exponentially increasing amounts of time, there will always come a point where a computation is too large or time-consuming to do on your particular computer system. As you work with Mathematica, you should develop some feeling for the limits on the kinds of calculations you can do in your particular application area.

• Doing arithmetic with numbers containing a few hundred million digits.
• Generating a few million digits of numbers like and .
• Expanding out a polynomial that gives a million terms.
• Factoring a polynomial in four variables with a hundred thousand terms.
• Reducing a system of quadratic inequalities to a few thousand independent components.
• Finding integer roots of a sparse polynomial with degree one million.
• Applying a recursive rule a million times.
• Calculating all the primes up to ten million.
• Finding the numerical inverse of a 1000×1000 dense matrix.
• Solving a million-variable sparse linear system with several million nonzero coefficients.
• Finding the determinant of a 250×250 integer matrix.
• Finding the determinant of a 10×10 symbolic matrix.
• Finding numerical roots of a polynomial of degree 200.
• Solving a sparse linear programming problem with a few hundred thousand variables.
• Drawing a network with tens of thousands of vertices and hundreds of thousands of edges
automatically.
• Finding the Fourier transform of a list with a hundred million elements.
• Rendering a million graphics primitives.
• Sorting a list of ten million elements.
• Searching a string that is ten million characters long.
• Importing a few tens of megabytes of numerical data.
• Formatting a few hundred pages of TraditionalForm output.

Some operations that typically take no more than a few seconds on a 2006-vintage PC.

New to Mathematica? Find your learning path »
Have a question? Ask support »