Faster Algorithms via Approximation Theory

This monograph presents techniques to approximate real functions such as xs; x–1 and e–x by simpler functions and shows how these results can be used for the design of fast algorithms. The key lies in the fact that such results imply faster ways to approximate primitives such as Asv; A–1v and exp(–A)v, and to compute matrix eigenvalues and eigenvectors. Indeed, many fast algorithms reduce to the computation of such primitives, which have proved useful for speeding up several fundamental computations such as random walk simulation, graph partitioning and solving linear systems of equations.