Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGeometric scaling: a simple preconditioner for certain linear systems with discontinuous coefficients
307
0
0.0
(
0
)
Added by
Dan Gordon
Publication date
2009
fields
Informatics Engineering
and research's language is
English
Authors
Dan Gordon
Ask ChatGPT about the research
No Arabic abstract
Linear systems with large differences between coefficients (discontinuous coefficients) arise in many cases in which partial differential equations(PDEs) model physical phenomena involving heterogeneous media. The standard approach to solving such problems is to use domain decomposition techniques, with domain boundaries conforming to the boundaries between the different media. This approach can be difficult to implement when the geometry of the domain boundaries is complicated or the grid is unstructured. This work examines the simple preconditioning technique of scaling the equations by dividing each equation by the Lp-norm of its coefficients. This preconditioning is called geometric scaling (GS). It has long been known that diagonal scaling can be useful in improving convergence, but there is no study on the general usefulness of this approach for discontinuous coefficients. GS was tested on several nonsymmetric linear systems with discontinuous coefficients derived from convection-diffusion elliptic PDEs with small to moderate convection terms. It is shown that GS improved the convergence properties of restarted GMRES and Bi-CGSTAB, with and without the ILUT preconditioner. GS was also shown to improve the distribution of the eigenvalues by reducing their concentration around the origin very significantly.
rate research
Read More
Based on the geometric {it Triangle Algorithm} for testing membership of a point in a convex set, we present a novel iterative algorithm for testing the solvability of a real linear system $Ax=b$, where $A$ is an $m times n$ matrix of arbitrary rank. Let $C_{A,r}$ be the ellipsoid determined as the image of the Euclidean ball of radius $r$ under the linear map $A$. The basic procedure in our algorithm computes a point in $C_{A,r}$ that is either within $varepsilon$ distance to $b$, or acts as a certificate proving $b ot in C_{A,r}$. Each iteration takes $O(mn)$ operations and when $b$ is well-situated in $C_{A,r}$, the number of iterations is proportional to $log{(1/varepsilon)}$. If $Ax=b$ is solvable the algorithm computes an approximate solution or the minimum-norm solution. Otherwise, it computes a certificate to unsolvability, or the minimum-norm least-squares solution. It is also applicable to complex input. In a computational comparison with the state-of-the-art algorithm BiCGSTAB ({it Bi-conjugate gradient method stabilized}), the Triangle Algorithm is very competitive. In fact, when the iterates of BiCGSTAB do not converge, our algorithm can verify $Ax=b$ is unsolvable and approximate the minimum-norm least-squares solution. The Triangle Algorithm is robust, simple to implement, and requires no preconditioner, making it attractive to practitioners, as well as researchers and educators.
We study the asymptotic behavior of solution of semi-linear PDEs. Neither periodicity nor ergodicity will be assumed. In return, we assume that the coefficients admit a limit in `{C}esaro sense. In such a case, the averaged coefficients could be discontinuous. We use probabilistic approach based on weak convergence for the associated backward stochastic differential equation in the S-topology to derive the averaged PDE. However, since the averaged coefficients are discontinuous, the classical viscosity solution is not defined for the averaged PDE. We then use the notion of $L^p-$viscosity solution introduced in cite{CCKS}. We use BSDEs techniques to establish the existence of $L^p-$viscosity solution for the averaged PDE. We establish weak continuity for the flow of the limit diffusion process and related the PDE limit to the backward stochastic differential equation via the representation of $L^p$-viscosity solution.
Computational implementations for solving systems of linear equations often rely on a one-size-fits-all approach based on LU decomposition of dense matrices stored in column-major format. Such solvers are typically implemented with the aid of the xGESV set of functions available in the low-level LAPACK software, with the aim of reducing development time by taking advantage of well-tested routines. However, this straightforward approach does not take into account various matrix properties which can be exploited to reduce the computational effort and/or to increase numerical stability. Furthermore, direct use of LAPACK functions can be error-prone for non-expert users and results in source code that has little resemblance to originating mathematical expressions. We describe an adaptive solver that we have implemented inside rece
We give another proof, using tools from Geometric Invariant Theory, of a result due to S. Sam and A. Snowden in 2014, concerning the stability of Kro-necker coefficients. This result states that some sequences of Kronecker coefficients eventually stabilise, and our method gives a nice geometric bound from which the stabilisation occurs. We perform the explicit computation of such a bound on two examples, one being the classical case of Murnaghans stability. Moreover, we see that our techniques apply to other coefficients arising in Representation Theory: namely to some plethysm coefficients and in the case of the tensor product of representations of the hyperoctahedral group.
We consider a class of stochastic growth models on the integer lattice which includes various interesting examples such as the number of open paths in oriented percolation and the binary contact path process. Under some mild assumptions, we show that the total mass of the process grows exponentially in time whenever it survives. More precisely, we prove that there exists an open path, oriented in time, along which the mass grows exponentially fast.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
