Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA posteriori superlinear convergence bounds for block conjugate gradient
75
0
0.0
(
0
)
Added by
Christian Schaerer
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper, we extend to the block case, the a posteriori bound showing superlinear convergence of Conjugate Gradients developed in [J. Comput. Applied Math., 48 (1993), pp. 327- 341], that is, we obtain similar bounds, but now for block Conjugate Gradients. We also present a series of computational experiments, illustrating the validity of the bound developed here, as well as the bound from [SIAM Review, 47 (2005), pp. 247-272] using angles between subspaces. Using these bounds, we make some observations on the onset of superlinearity, and how this onset depends on the eigenvalue distribution and the block size.
rate research
Read More
This paper presents a posteriori error estimates for conforming numerical approximations of eigenvalue clusters of second-order self-adjoint elliptic linear operators with compact resolvent. Given a cluster of eigenvalues, we estimate the error in the sum of the eigenvalues, as well as the error in the eigenvectors represented through the density matrix, i.e., the orthogonal projector on the associated eigenspace. This allows us to deal with degenerate (multiple) eigenvalues within the framework. All the bounds are valid under the only assumption that the cluster is separated from the surrounding smaller and larger eigenvalues; we show how this assumption can be numerically checked. Our bounds are guaranteed and converge with the same speed as the exact errors. They can be turned into fully computable bounds as soon as an estimate on the dual norm of the residual is available, which is presented in two particular cases: the Laplace eigenvalue problem discretized with conforming finite elements, and a Schr{o}dinger operator with periodic boundary conditions of the form $--$Delta$ + V$ discretized with planewaves. For these two cases, numerical illustrations are provided on a set of test problems.
We consider best approximation problems in a nonlinear subset $mathcal{M}$ of a Banach space of functions $(mathcal{V},|bullet|)$. The norm is assumed to be a generalization of the $L^2$-norm for which only a weighted Monte Carlo estimate $|bullet|_n$ can be computed. The objective is to obtain an approximation $vinmathcal{M}$ of an unknown function $u in mathcal{V}$ by minimizing the empirical norm $|u-v|_n$. We consider this problem for general nonlinear subsets and establish error bounds for the empirical best approximation error. Our results are based on a restricted isometry property (RIP) which holds in probability and is independent of the nonlinear least squares setting. Several model classes are examined where analytical statements can be made about the RIP and the results are compared to existing sample complexity bounds from the literature. We find that for well-studied model classes our general bound is weaker but exhibits many of the same properties as these specialized bounds. Notably, we demonstrate the advantage of an optimal sampling density (as known for linear spaces) for sets of functions with sparse representations.
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.
This work considers the problem of computing the CANDECOMP/PARAFAC (CP) decomposition of large tensors. One popular way is to translate the problem into a sequence of overdetermined least squares subproblems with Khatri-Rao product (KRP) structure. In this work, for tensor with different levels of importance in each fiber, combining stochastic optimization with randomized sampling, we present a mini-batch stochastic gradient descent algorithm with importance sampling for those special least squares subproblems. Four different sampling strategies are provided. They can avoid forming the full KRP or corresponding probabilities and sample the desired fibers from the original tensor directly. Moreover, a more practical algorithm with adaptive step size is also given. For the proposed algorithms, we present their convergence properties and numerical performance. The results on synthetic data show that our algorithms outperform the existing algorithms in terms of accuracy or the number of iterations.
The Richards equation is commonly used to model the flow of water and air through soil, and it serves as a gateway equation for multiphase flows through porous media. It is a nonlinear advection-reaction-diffusion equation that exhibits both parabolic-hyperbolic and parabolic-elliptic kinds of degeneracies. In this study, we provide reliable, fully computable, and locally space-time efficient a posteriori error bounds for numerical approximations of the fully degenerate Richards equation. For showing global reliability, a nonlocal-in-time error estimate is derived individually for the time-integrated $H^1(H^{-1})$, $L^2(L^2)$, and the $L^2(H^1)$ errors. A maximum principle and a degeneracy estimator are employed for the last one. Global and local space-time efficiency error bounds are then obtained in a standard $H^1(H^{-1})cap L^2(H^1)$ norm. The reliability and efficiency norms employed coincide when there is no nonlinearity. Moreover, error contributors such as flux nonconformity, time discretization, quadrature, linearization, and data oscillation are identified and separated. The estimates are also valid in a setting where iterative linearization with inexact solvers is considered. Numerical tests are conducted for nondegenerate and degenerate cases having exact solutions, as well as for a realistic case. It is shown that the estimators correctly identify the errors up to a factor of the order of unity.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
