Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSolving the 3D High-Frequency Helmholtz Equation using Contour Integration and Polynomial Preconditioning
74
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We propose an iterative solution method for the 3D high-frequency Helmholtz equation that exploits a contour integral formulation of spectral projectors. In this framework, the solution in certain invariant subspaces is approximated by solving complex-shifted linear systems, resulting in faster GMRES iterations due to the restricted spectrum. The shifted systems are solved by exploiting a polynomial fixed-point iteration, which is a robust scheme even if the magnitude of the shift is small. Numerical tests in 3D indicate that $O(n^{1/3})$ matrix-vector products are needed to solve a high-frequency problem with a matrix size $n$ with high accuracy. The method has a small storage requirement, can be applied to both dense and sparse linear systems, and is highly parallelizable.
rate research
Read More
We present a polynomial preconditioner for solving large systems of linear equations. The polynomial is derived from the minimum residual polynomial and is straightforward to compute and implement. It this paper, we study the polynomial preconditioner applied to GMRES; however it could be used with any Krylov solver. Stability control using added roots allows for high degree polynomials. We discuss the effectiveness and challenges of root-adding and give an additional check for stability. This polynomial preconditioning algorithm can dramatically improve convergence for difficult problems and can reduce dot products by an even greater margin.
Unless special conditions apply, the attempt to solve ill-conditioned systems of linear equations with standard numerical methods leads to uncontrollably high numerical error. Often, such systems arise from the discretization of operator equations with a large number of discrete variables. In this paper we show that the accuracy can be improved significantly if the equation is transformed before discretization, a process we call full operator preconditioning (FOP). It bears many similarities with traditional preconditioning for iterative methods but, crucially, transformations are applied at the operator level. We show that while condition-number improvements from traditional preconditioning generally do not improve the accuracy of the solution, FOP can. A number of topics in numerical analysis can be interpreted as implicitly employing FOP; we highlight (i) Chebyshev interpolation in polynomial approximation, and (ii) Olver-Townsends spectral method, both of which produce solutions of dramatically improved accuracy over a naive problem formulation. In addition, we propose a FOP preconditioner based on integration for the solution of fourth-order differential equations with the finite-element method, showing the resulting linear system is well-conditioned regardless of the discretization size, and demonstrate its error-reduction capabilities on several examples. This work shows that FOP can improve accuracy beyond the standard limit for both direct and iterative methods.
This paper analyses the following question: let $mathbf{A}_j$, $j=1,2,$ be the Galerkin matrices corresponding to finite-element discretisations of the exterior Dirichlet problem for the heterogeneous Helmholtz equations $ ablacdot (A_j abla u_j) + k^2 n_j u_j= -f$. How small must $|A_1 -A_2|_{L^q}$ and $|{n_1} - {n_2}|_{L^q}$ be (in terms of $k$-dependence) for GMRES applied to either $(mathbf{A}_1)^{-1}mathbf{A}_2$ or $mathbf{A}_2(mathbf{A}_1)^{-1}$ to converge in a $k$-independent number of iterations for arbitrarily large $k$? (In other words, for $mathbf{A}_1$ to be a good left- or right-preconditioner for $mathbf{A}_2$?). We prove results answering this question, give theoretical evidence for their sharpness, and give numerical experiments supporting the estimates. Our motivation for tackling this question comes from calculating quantities of interest for the Helmholtz equation with random coefficients $A$ and $n$. Such a calculation may require the solution of many deterministic Helmholtz problems, each with different $A$ and $n$, and the answer to the question above dictates to what extent a previously-calculated inverse of one of the Galerkin matrices can be used as a preconditioner for other Galerkin matrices.
Let V be a smooth equidimensional quasi-affine variety of dimension r over the complex numbers $C$ and let $F$ be a $(ptimes s)$-matrix of coordinate functions of $C[V]$, where $sge p+r$. The pair $(V,F)$ determines a vector bundle $E$ of rank $s-p$ over $W:={xin V:mathrm{rk} F(x)=p}$. We associate with $(V,F)$ a descending chain of degeneracy loci of E (the generic polar varieties of $V$ represent a typical example of this situation). The maximal degree of these degeneracy loci constitutes the essential ingredient for the uniform, bounded error probabilistic pseudo-polynomial time algorithm which we are going to design and which solves a series of computational elimination problems that can be formulated in this framework. We describe applications to polynomial equation solving over the reals and to the computation of a generic fiber of a dominant endomorphism of an affine space.
In this paper, we present a multiscale framework for solving the Helmholtz equation in heterogeneous media without scale separation and in the high frequency regime where the wavenumber $k$ can be large. The main innovation is that our methods achieve a nearly exponential rate of convergence with respect to the computational degrees of freedom, using a coarse grid of mesh size $O(1/k)$ without suffering from the well-known pollution effect. The key idea is a coarse-fine scale decomposition of the solution space that adapts to the media property and wavenumber; this decomposition is inspired by the multiscale finite element method. We show that the coarse part is of low complexity in the sense that it can be approximated with a nearly exponential rate of convergence via local basis functions, while the fine part is local such that it can be computed efficiently using the local information of the right hand side. The combination of the two parts yields the overall nearly exponential rate of convergence. We demonstrate the effectiveness of our methods theoretically and numerically; an exponential rate of convergence is consistently observed and confirmed. In addition, we observe the robustness of our methods regarding the high contrast in the media numerically.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
