Why is arithmetic faster for inexact arithmetic?

I have been trying to compute eigenvalues of a rather sizable matrix A, about $500 \times 500$ (but sparse). I asked Mathematica to compute Eigenvalues[A], and left it to work. After a night of computation, Mathematica still failed to produce the answer. Just out of curiousity, I tried to see what happens if I replace A by it's numeric approximation (before, A had integer entries, hence exact). (I didn't quite expect it to make a difference, but I was trying some random things). Much to my surprise, the answer appeared immediately. Hence my question: How does it happen that Mathematica produces the answer so much faster for inexact input? To what extent can this output be trusted?

• A simple answer is that inexact values make use of built-in hardware support for arithmetic. – image_doctor May 7 '13 at 7:28
• For a matrix that large, it is often infeasible to ask for exact solutions. "To what extent can this output be trusted?" - I don't trust output entirely, but there is the procedure of using Mathematica's arbitrary-precision capabilities, asking for the eigenvalues to 20 digits (Eigenvalues[N[A, 20]]), 30 digits, ... and so on. If there is some agreement between these results, then I trust the results a little bit more. – J. M. will be back soon May 7 '13 at 7:42
• In addition to the complexity of solving roots, manipulation of exact values, in general, is time-consuming. On efficiently vectorized code of machine-precision arithmetic, a CPU may perform up to something like 16 basic arithmetic operations per a clock cycle, thanks to direct machine representation of data. With exact non-integer values, cost of a single arithmetic operation probably starts at low dozens of clock cycles. So, unless you specifically require exact symbolic results, avoid them. Often finding them is even infeasible. Sometimes tools such as RootApproximant may save you though. – kirma May 7 '13 at 9:03
• Try a simple experiment. Do these computations on a smaller matrix, one for which the exact computation finishes in reasonable time. Then look at the results. Look very hard at the results. They will give a clue as to why one takes hugely longer than the other. – Daniel Lichtblau May 7 '13 at 14:00