In this work, we propose a runtime-data-driven enhancement preconditioner for improving the convergence of a preconditioned conjugate gradient method for solving a sequence of symmetric positive definite linear systems of equations. The methodology is designed for the situation where a subset of the systems has been solved and the convergence is considered too slow. In such a situation, data generated from the solved problems (residual vectors, intermediate solution vectors, approximate error vectors) are first analyzed by an unsupervised learning algorithm as a 3-step process: (1) dimension reduction; (2) classification of the slow features; (3) construction of projections to each of the feature subspaces. Based on the results of the analysis, one or more enhancement preconditioners are constructed using projection matrices corresponding to the features extracted from the slow convergence subspaces. The enhancement preconditioners are additively incorporated into the existing preconditioners and are employed to solve other systems in the sequence. The enhancement preconditioner can be further enhanced when necessary by repeating this process. Numerical experiments for time-dependent problems, including parabolic and hyperbolic equations, and stochastic elliptic equations demonstrate that the proposed approach improves the convergence considerably for other systems in the sequence when classical preconditioners are insufficient.

TBC

We introduce a new spanning tree model which we call Random Spanning Trees in Random Environment (RSTRE), which was introduced independently by A. Kúsz. As the inverse temperature beta varies in the underlying Gibbs measure, it interpolates between the uniform spanning tree and the minimum spanning tree. On the complete graph with n vertices, we show that with high probability, the diameter of the random spanning tree is of order n^1/2 when β=o(n/log n), and is of order n^1/3 when β > n^4/3 log n. We conjecture that the diameter exponent linearly interpolates between these two regimes as the power exponent of beta varies. Based on joint work with L. Makowiec and M. Salvi.