Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Multilevel Approach to Variance Reduction in the Stochastic Estimation of the Trace of a Matrix
100
0
0.0
(
0
)
Added by
Andreas Frommer
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We present a scalable block preconditioning strategy for the trace system coming from the high-order hybridized discontinuous Galerkin (HDG) discretization of incompressible resistive magnetohydrodynamics (MHD). We construct the block preconditioner with a least squares commutator (BFBT) approximation for the inverse of the Schur complement that segregates out the pressure unknowns of the trace system. The remaining velocity, magnetic field, and Lagrange multiplier unknowns form a coupled nodal unknown block (the upper block), for which a system algebraic multigrid (AMG) is used for the approximate inverse. The complexity of the MHD equations together with the algebraic nature of the statically condensed HDG trace system makes the choice of smoother in the system AMG part critical for the convergence and performance of the block preconditioner. Our numerical experiments show GMRES preconditioned by ILU(0) of overlap zero as a smoother inside system AMG performs best in terms of robustness, time per nonlinear iteration and memory requirements. With several transient test cases in 2D and 3D including the island coalescence problem at high Lundquist number we demonstrate the robustness and parallel scalability of the block preconditioner. Additionally for the upper block a preliminary study of an alternate nodal block system solver based on a multilevel approximate nested dissection is presented. On a 2D island coalescence problem the multilevel approximate nested dissection preconditioner shows better scalability with respect to mesh refinement than the system AMG, but is relatively less robust with respect to Lundquist number scaling.
The paper considers a class of parametric elliptic partial differential equations (PDEs), where the coefficients and the right-hand side function depend on infinitely many (uncertain) parameters. We introduce a two-level a posteriori estimator to control the energy error in multilevel stochastic Galerkin approximations for this class of PDE problems. We prove that the two-level estimator always provides a lower bound for the unknown approximation error, while the upper bound is equivalent to a saturation assumption. We propose and empirically compare three adaptive algorithms, where the structure of the estimator is exploited to perform spatial refinement as well as parametric enrichment. The paper also discusses implementation aspects of computing multilevel stochastic Galerkin approximations.
We consider the inverse problem of estimating the spatially varying pulse wave velocity in blood vessels in the brain from dynamic MRI data, as it appears in the recently proposed imaging technique of Magnetic Resonance Advection Imaging (MRAI). The problem is formulated as a linear operator equation with a noisy operator and solved using a conjugate gradient type approach. Numerical examples on experimental data show the usefulness and advantages of the developed algorithm in comparison to previously proposed methods.
We present a general approach for the treatment of parameterized geometries in projection-based model order reduction. During the offline stage, given (i) a family of parameterized domains ${ Omega_{mu}: mu in mathcal{P} } subset mathbb{R}^D$ where $mu in mathcal{P} subset mathbb{R}^P$ denotes a vector of parameters, (ii) a parameterized mapping ${Phi}_{mu}$ between a reference domain $Omega$ and the parameter-dependent domain $Omega_{mu}$, and (iii) a finite element triangulation of $Omega$, we resort to an empirical quadrature procedure to select a subset of the elements of the grid. During the online stage, we first use the mapping to move the nodes of the selected elements and then we use standard element-wise residual evaluation routines to evaluate the residual and possibly its Jacobian. We discuss how to devise an online-efficient reduced-order model and we discuss the differences with the more standard map-then-discretize approach (e.g., Rozza, Huynh, Patera, ACME, 2007); in particular, we show how the discretize-then-map framework greatly simplifies the implementation of the reduced-order model. We apply our approach to a two-dimensional potential flow problem past a parameterized airfoil, and to the two-dimensional RANS simulations of the flow past the Ahmed body.
Partial differential equations (PDEs) with inputs that depend on infinitely many parameters pose serious theoretical and computational challenges. Sophisticated numerical algorithms that automatically determine which parameters need to be activated in the approximation space in order to estimate a quantity of interest to a prescribed error tolerance are needed. For elliptic PDEs with parameter-dependent coefficients, stochastic Galerkin finite element methods (SGFEMs) have been well studied. Under certain assumptions, it can be shown that there exists a sequence of SGFEM approximation spaces for which the energy norm of the error decays to zero at a rate that is independent of the number of input parameters. However, it is not clear how to adaptively construct these spaces in a practical and computationally efficient way. We present a new adaptive SGFEM algorithm that tackles elliptic PDEs with parameter-dependent coefficients quickly and efficiently. We consider approximation spaces with a multilevel structure---where each solution mode is associated with a finite element space on a potentially different mesh---and use an implicit a posteriori error estimation strategy to steer the adaptive enrichment of the space. At each step, the components of the error estimator are used to assess the potential benefits of a variety of enrichment strategies, including whether or not to activate more parameters. No marking or tuning parameters are required. Numerical experiments for a selection of test problems demonstrate that the new method performs optimally in that it generates a sequence of approximations for which the estimated energy error decays to zero at the same rate as the error for the underlying finite element method applied to the associated parameter-free problem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
