The pivoted Cholesky decomposition and its application to stochastic PDEs

Helmut Harbrecht, Uni Stuttgart

Abstract: The present talk is dedicated to the application of the pivoted Cholesky decomposition to compute low-rank approximations of dense, positive semi-definite matrices. Such matrices appear in the solution of stochastic partial differential equations when two-point correlation functions are discretized, e.g. in order to compute Karhunen-Loeve expansions. The approximation error of the pivoted Cholesky decomposition is rigorously controlled in terms of the trace norm. Exponential convergence rates are proved under the assumption that thes eigenvalues of the matrix under consideration exhibit a sufficiently fast exponential decay.
By numerical experiments it is demonstrated that the pivoted Cholesky decomposition leads to very efficient algorithms to separate the variables of bi-variate functions.