We present an efficient matrix-free geometric multigrid method for the elastic Helmholtz equation, and a suitable discretization. Many discretization methods had been considered in the literature for the Helmholtz equations, as well as many solvers and preconditioners, some of which are adapted for the elastic version of the equation. However, there is very little work considering the reciprocity of discretization and a solver. In this work, we aim to bridge this gap. By choosing an appropriate stencil for re-discretization of the equation on the coarse grid, we develop a multigrid method that can be easily implemented as matrix-free, relying on stencils rather than sparse matrices. This is crucial for efficient implementation on modern hardware. Using two-grid local Fourier analysis, we validate the compatibility of our discretization with our solver, and tune a choice of weights for the stencil for which the convergence rate of the multigrid cycle is optimal. It results in a scalable multigrid preconditioner that can tackle large real-world 3D scenarios.
相關內容
We present a novel combination of dynamic embedded topic models and change-point detection to explore diachronic change of lexical semantic modality in classical and early Christian Latin. We demonstrate several methods for finding and characterizing patterns in the output, and relating them to traditional scholarship in Comparative Literature and Classics. This simple approach to unsupervised models of semantic change can be applied to any suitable corpus, and we conclude with future directions and refinements aiming to allow noisier, less-curated materials to meet that threshold.
The problem of straggler mitigation in distributed matrix multiplication (DMM) is considered for a large number of worker nodes and a fixed small finite field. Polynomial codes and matdot codes are generalized by making use of algebraic function fields (i.e., algebraic functions over an algebraic curve) over a finite field. The construction of optimal solutions is translated to a combinatorial problem on the Weierstrass semigroups of the corresponding algebraic curves. Optimal or almost optimal solutions are provided. These have the same computational complexity per worker as classical polynomial and matdot codes, and their recovery thresholds are almost optimal in the asymptotic regime (growing number of workers and a fixed finite field).
The celebrated Kleene fixed point theorem is crucial in the mathematical modelling of recursive specifications in Denotational Semantics. In this paper we discuss whether the hypothesis of the aforementioned result can be weakened. An affirmative answer to the aforesaid inquiry is provided so that a characterization of those properties that a self-mapping must satisfy in order to guarantee that its set of fixed points is non-empty when no notion of completeness are assumed to be satisfied by the partially ordered set. Moreover, the case in which the partially ordered set is coming from a quasi-metric space is treated in depth. Finally, an application of the exposed theory is obtained. Concretely, a mathematical method to discuss the asymptotic complexity of those algorithms whose running time of computing fulfills a recurrence equation is presented. Moreover, the aforesaid method retrieves the fixed point based methods that appear in the literature for asymptotic complexity analysis of algorithms. However, our new method improves the aforesaid methods because it imposes fewer requirements than those that have been assumed in the literature and, in addition, it allows to state simultaneously upper and lower asymptotic bounds for the running time computing.
We study the sharp interface limit of the stochastic Cahn-Hilliard equation with cubic double-well potential and additive space-time white noise $\epsilon^{\sigma}\dot{W}$ where $\epsilon>0$ is an interfacial width parameter. We prove that, for sufficiently large scaling constant $\sigma >0$, the stochastic Cahn-Hilliard equation converges to the deterministic Mullins-Sekerka/Hele-Shaw problem for $\epsilon\rightarrow 0$. The convergence is shown in suitable fractional Sobolev norms as well as in the $L^p$-norm for $p\in (2, 4]$ in spatial dimension $d=2,3$. This generalizes the existing result for the space-time white noise to dimension $d=3$ and improves the existing results for smooth noise, which were so far limited to $p\in \left(2, \frac{2d+8}{d+2}\right]$ in spatial dimension $d=2,3$. As a byproduct of the analysis of the stochastic problem with space-time white noise, we identify minimal regularity requirements on the noise which allow convergence to the sharp interface limit in the $\mathbb{H}^1$-norm and also provide improved convergence estimates for the sharp interface limit of the deterministic problem.
In this paper we develop a classical algorithm of complexity $O(2^n)$ to simulate parametrized quantum circuits (PQCs) of $n$ qubits. The algorithm is developed by finding $2$-sparse unitary matrices of order $2^n$ explicitly corresponding to any single-qubit and two-qubit control gates in an $n$-qubit system. Finally, we determine analytical expression of Hamiltonians for any such gate and consequently a local Hamiltonian decomposition of any PQC is obtained. All results are validated with numerical simulations.
We propose a framework where Fer and Wilcox expansions for the solution of differential equations are derived from two particular choices for the initial transformation that seeds the product expansion. In this scheme intermediate expansions can also be envisaged. Recurrence formulas are developed. A new lower bound for the convergence of the Wilcox expansion is provided as well as some applications of the results. In particular, two examples are worked out up to high order of approximation to illustrate the behavior of the Wilcox expansion.
We propose a new stabilised finite element method for the classical Kolmogorov equation. The latter serves as a basic model problem for large classes of kinetic-type equations and, crucially, is characterised by degenerate diffusion. The stabilisation is constructed so that the resulting method admits a \emph{numerical hypocoercivity} property, analogous to the corresponding property of the PDE problem. More specifically, the stabilisation is constructed so that spectral gap is possible in the resulting ``stronger-than-energy'' stabilisation norm, despite the degenerate nature of the diffusion in Kolmogorov, thereby the method has a provably robust behaviour as the ``time'' variable goes to infinity. We consider both a spatially discrete version of the stabilised finite element method and a fully discrete version, with the time discretisation realised by discontinuous Galerkin timestepping. Both stability and a priori error bounds are proven in all cases. Numerical experiments verify the theoretical findings.
This work proposes a novel variational approximation of partial differential equations on moving geometries determined by explicit boundary representations. The benefits of the proposed formulation are the ability to handle large displacements of explicitly represented domain boundaries without generating body-fitted meshes and remeshing techniques. For the space discretization, we use a background mesh and an unfitted method that relies on integration on cut cells only. We perform this intersection by using clipping algorithms. To deal with the mesh movement, we pullback the equations to a reference configuration (the spatial mesh at the initial time slab times the time interval) that is constant in time. This way, the geometrical intersection algorithm is only required in 3D, another key property of the proposed scheme. At the end of the time slab, we compute the deformed mesh, intersect the deformed boundary with the background mesh, and consider an exact transfer operator between meshes to compute jump terms in the time discontinuous Galerkin integration. The transfer is also computed using geometrical intersection algorithms. We demonstrate the applicability of the method to fluid problems around rotating (2D and 3D) geometries described by oriented boundary meshes. We also provide a set of numerical experiments that show the optimal convergence of the method.
It is well known that for singular inconsistent range-symmetric linear systems, the generalized minimal residual (GMRES) method determines a least squares solution without breakdown. The reached least squares solution may be or not be the pseudoinverse solution. We show that a lift strategy can be used to obtain the pseudoinverse solution. In addition, we propose a new iterative method named RSMAR (minimum $\mathbf A$-residual) for range-symmetric linear systems $\mathbf A\mathbf x=\mathbf b$. At step $k$ RSMAR minimizes $\|\mathbf A\mathbf r_k\|$ in the $k$th Krylov subspace generated with $\{\mathbf A, \mathbf r_0\}$ rather than $\|\mathbf r_k\|$, where $\mathbf r_k$ is the $k$th residual vector and $\|\cdot\|$ denotes the Euclidean vector norm. We show that RSMAR and GMRES terminate with the same least squares solution when applied to range-symmetric linear systems. We provide two implementations for RSMAR. Our numerical experiments show that RSMAR is the most suitable method among GMRES-type methods for singular inconsistent range-symmetric linear systems.
We consider the generalized Newton method (GNM) for the absolute value equation (AVE) $Ax-|x|=b$. The method has finite termination property whenever it is convergent, no matter whether the AVE has a unique solution. We prove that GNM is convergent whenever $\rho(|A^{-1}|)<1/3$. We also present new results for the case where $A-I$ is a nonsingular $M$-matrix or an irreducible singular $M$-matrix. When $A-I$ is an irreducible singular $M$-matrix, the AVE may have infinitely many solutions. In this case, we show that GNM always terminates with a uniquely identifiable solution, as long as the initial guess has at least one nonpositive component.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191