Faster Algorithms via Approximation Theory

Approximation Theory and Fast Algorithms illustrates how classical and modern results from approximation theory play a crucial role in obtaining results that are relevant to the emerging theory of fast algorithms today. For example, it shows how to compute good approximations to matrix-vector products such as Asv; A-1v and exp(-A)v for any matrix A and a vector v.6. It also shows how to speed up algorithms that compute the top few eigenvalues and eigenvectors of a symmetric matrix A. Such primitives are useful for performing several fundamental computations quickly, such as random walk simulation, graph partitioning, solving linear system of equations, and combinatorial approaches to solving semi-definite programs. The algorithms for computing these primitives perform calculations of the form Bu where B is a matrix closely related to A (often A itself) and u is some vector. A key feature of these algorithms is that if the matrix-vector product for A can be computed quickly, e.g., when A is sparse, then Bu can also be computed in essentially the same time. This makes such algorithms particularly relevant for handling the problem of big data. Such matrices capture either numerical data or large graphs, and it is inconceivable to be able to compute much more than a few matrix-vector products on matrices of this size.