Sushant Sachdeva and Nisheeth K. Vishnoi (2014), "Faster Algorithms via Approximation Theory", Foundations and Trends® in Theoretical Computer Science: Vol. 9: No. 2, pp 125-210. http://dx.doi.org/10.1561/0400000065

© 2014 S. Sachdeva and N. K. Vishnoi

Design and analysis of algorithms, Computational aspects of combinatorics and graph theory, Spectral methods

Download article
**In this article:**

1. Uniform Approximations

2. Chebyshev Polynomials

3. Approximating Monomials

4. Approximating the Exponential

5. Lower Bounds for Polynomial Approximations

6. Approximating the Exponential using Rational Functions

7. Rational Approximations to the Exponential with Negative Poles

8. Simulating Random Walks

9. Solving Linear Equations via the Conjugate Gradient Method

10. Computing Eigenvalues via the Lanczos Method

11. Computing the Matrix Exponential

12. Matrix Inversion via Exponentiation

References

This monograph presents techniques to approximate real functions such as
*x*^{
s
}; *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 *A*^{
s
}*v*;
*A*^{–1}*v* 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.

1. Uniform Approximations

2. Chebyshev Polynomials

3. Approximating Monomials

4. Approximating the Exponential

5. Lower Bounds for Polynomial Approximations

6. Approximating the Exponential using Rational Functions

7. Rational Approximations to the Exponential with Negative Poles

8. Simulating Random Walks

9. Solving Linear Equations via the Conjugate Gradient Method

10. Computing Eigenvalues via the Lanczos Method

11. Computing the Matrix Exponential

12. Matrix Inversion via Exponentiation

References

*Faster Algorithms via Approximation Theory* illustrates how
classical and modern techniques from approximation theory play a crucial role in
obtaining results that are relevant to the emerging theory of fast algorithms.
The key lies in the fact that such results imply faster ways to approximate
primitives such as products of matrix functions with vectors, and to compute
matrix eigenvalues and eigenvectors, which are fundamental to many
spectral algorithms.

The first half of the book is devoted to the ideas and results from approximation theory that are central, elegant, and may have wider applicability in theoretical computer science. These include not only techniques relating to polynomial approximations but also those relating to approximations by rational functions and beyond. The remaining half illustrates a variety of ways that these results can be used to design fast algorithms.

*Faster Algorithms via Approximation Theory* is self-contained and
should be of interest to researchers and students in theoretical computer science,
numerical linear algebra, and related areas.