Search results for "multigrid"

Importance of quantiser design compared to optimal multigrid motion estimation in video coding

2000

Adaptive flow computation and DCT quantisation play complementary roles in motion compensated video coding schemes. Since the introduction of the intuitive entropy-constrained motion estimation of Dufaux et al. (1995), several optimal variable-size block matching algorithms have been proposed. Many of these approaches put forward their intrinsic optimality, but the corresponding visual effect has not been explored. The relative importance of optimal multigrid motion estimation with regard to quantisation is addressed in the context of MPEG-like coding. It is shown that while simpler (suboptimal) motion estimates give subjective results as good as the optimal motion estimates, small enhancem…

Poissonin yhtälön nopeat ratkaisijat

2016

Tutkielmassa esitellään Poissonin yhtälö sekä sen diskretointi. Lisäksi käydään läpi kaksi nopeaa numeerista menetelmää yhtälön ratkaisemiseksi. Yksinkertaisuuden vuoksi rajoitutaan kaksiulotteisiin tehtäviin, joissa on voimassa Dirichle’t reunaehto. Ensimmäinen menetelmistä on monihilamenetelmä, joka on iteratiivinen menetelmä, ja toisena syklinen reduktio, joka on suora menetelmä. Molemmat menetelmät ovat hyvin tehokkaita sekä helposti rinnakkaistuvia. In this thesis we introduce Poisson’s equation and its discretization. In addition we go through two fast numerical methods for solving the equation. The thesis is limited only to two-dimensional cases with Dirichlet boundary condition. The…

Multicanonical Monte Carlo simulations

1998

Canonical Monte Carlo simulations of disordered systems like spin glasses and systems undergoing first-order phase transitions are severely hampered by rare event states which lead to exponentially diverging autocorrelation times with increasing system size and hence to exponentially large statistical errors. One possibility to overcome this problem is the multicanonical reweighting method. Using standard local update algorithms it could be demonstrated that the dependence of autocorrelation times on the system size V is well described by a less divergent power law, τ∝Vα, with 1<α<3, depending on the system. After a brief review of the basic ideas, combinations of multicanonical reweighting…

Numerical Study of Two Sparse AMG-methods

2003

A sparse algebraic multigrid method is studied as a cheap and accurate way to compute approximations of Schur complements of matrices arising from the discretization of some symmetric and positive definite partial differential operators. The construction of such a multigrid is discussed and numerical experiments are used to verify the properties of the method.

Controllability method for the Helmholtz equation with higher-order discretizations

2007

We consider a controllability technique for the numerical solution of the Helmholtz equation. The original time-harmonic equation is represented as an exact controllability problem for the time-dependent wave equation. This problem is then formulated as a least-squares optimization problem, which is solved by the conjugate gradient method. Such an approach was first suggested and developed in the 1990s by French researchers and we introduce some improvements to its practical realization. We use higher-order spectral elements for spatial discretization, which leads to high accuracy and lumped mass matrices. Higher-order approximation reduces the pollution effect associated with finite elemen…

A graph-based multigrid with applications

2010

A Projected Algebraic Multigrid Method for Linear Complementarity Problems

2011

We present an algebraic version of an iterative multigrid method for obstacle problems, called projected algebraic multigrid (PAMG) here. We show that classical AMG algorithms can easily be extended to deal with this kind of problem. This paves the way for efficient multigrid solution of obstacle problems with partial differential equations arising, for example, in financial engineering.

Computation of a few smallest eigenvalues of elliptic operators using fast elliptic solvers

2001

The computation of a few smallest eigenvalues of generalized algebraic eigenvalue problems is studied. The considered problems are obtained by discretizing self-adjoint second-order elliptic partial differential eigenvalue problems in two- or three-dimensional domains. The standard Lanczos algorithm with the complete orthogonalization is used to compute some eigenvalues of the inverted eigenvalue problem. Under suitable assumptions, the number of Lanczos iterations is shown to be independent of the problem size. The arising linear problems are solved using some standard fast elliptic solver. Numerical experiments demonstrate that the inverted problem is much easier to solve with the Lanczos…

Deciding the fate of the false Mott transition in two dimensions by exact quantum Monte Carlo methods

2015

We present an algorithm for the computation of unbiased Green functions and self-energies for quantum lattice models, free from systematic errors and valid in the thermodynamic limit. The method combines direct lattice simulations using the Blankenbecler Scalapino-Sugar quantum Monte Carlo (BSS-QMC) approach with controlled multigrid extrapolation techniques. We show that the half-filled Hubbard model is insulating at low temperatures even in the weak-coupling regime; the previously claimed Mott transition at intermediate coupling does not exist.

(Approximate) Low-Mode Averaging with a new Multigrid Eigensolver

2015

We present a multigrid based eigensolver for computing low-modes of the Hermitian Wilson Dirac operator. For the non-Hermitian case multigrid methods have already replaced conventional Krylov subspace solvers in many lattice QCD computations. Since the $\gamma_5$-preserving aggregation based interpolation used in our multigrid method is valid for both, the Hermitian and the non-Hermitian case, inversions of very ill-conditioned shifted systems with the Hermitian operator become feasible. This enables the use of multigrid within shift-and-invert type eigensolvers. We show numerical results from our MPI-C implementation of a Rayleigh quotient iteration with multigrid. For state-of-the-art lat…