The trace of a matrix function f(A), most notably of the matrix inverse, can be estimated stochastically using samples< x,f(A)x> if the components of the random vectors x obey an appropriate probability distribution. However such a Monte-Carlo sampling suffers from the fact that the accuracy depends quadratically of the samples to use, thus making higher precision estimation very costly. In this paper we suggest and investigate a multilevel Monte-Carlo approach which uses a multigrid hierarchy to stochastically estimate the trace. This results in a substantial reduction of the variance, so that higher precision can be obtained at much less effort. We illustrate this for the trace of the inverse using three different classes of matrices.
翻译:矩阵函数f(A)的痕量,特别是矩阵反比,如果随机矢量x的成分遵守适当的概率分布,则使用样本 < x,f(A)x > 就可以对矩阵函数f(A)的痕量进行随机估计,但蒙特-卡洛的采样却由于样品的准确性取决于要使用的样品的四边形,从而导致更精确的估计成本很高。在本文中,我们建议并调查一种多层次的蒙特-卡洛方法,该方法使用多网格等级来对痕量进行随机估计。这可以大幅缩小差异,从而以更少的努力获得更高的精确度。我们用三种不同的矩阵来说明反向的痕量。