I will talk about techniques to approximate real functions such as $x^s,$ $x^{-1}$ and $e^{-x}$ by simpler functions and how these results can be used in the design of fast algorithms. The key lies in the fact that such approximations imply faster ways to approximate primitives such as $A^sv,$ $A^{-1}v$ and $\exp({-A})v$, and in the computation of 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, solving linear systems of equations, and combinatorial approaches for solving semi-definite programs.

- All seminars.
- Seminars for 2014

Last updated: 24 Jun 2019