Narrow Results

This paper develops sharp convergence rate estimates of the Schwarz alternating procedure. We do this for a model Poisson problem in one and two dimensions with multiple subdomains We then use these estimates to assess the serial and parallel complexity of the optimal Schwarz algorithm. We finish with a comparison of this optimal algorithm, using multigrid as the subdomain solver, and multigrid by itself, without domain decomposition.

Four totally parallel algorithms for the solution of a sparse linear system have common characteristics which become quite apparent when they are implemented on a highly parallel hypercube such as the CM2. These four algorithms are Parallel Superconvergent Multigrid (PSMG) of Frederickson and McBryan, Robust Multigrid (RMG) of Hackbusch, the FFT based Spectral Algorithm, and Parallel Cyclic Reduction. In fact, all four can be formulated as particular cases of the same totally parallel multilevel algorithm, which we will refer to as TPMA. In certain cases the spectral radius of TPMA is zero, and it is recognized to be a direct algorithm. In many other cases the spectral radius, although not zero, is small enough that a single iteration per timestep keeps the local error within the required tolerance.

We develop an analytical model of grid communication on the connection machine for arbitrary grid geometries over exact power-of-two distances. There is excellent agreement between the model and the measured performance of the CM2. We propose some conceptually simple enhancements to the virtual processor mechanism and to the grid communication microcode which could lead to substantial performance improvements for several important numerical algorithms.

Multigrid is a fast and popular iterative method used to solve linear partial differential equations. However, because the solution of very small problems is inherent in the multigrid iteration, it is difficult to implement efficiently on a massively parallel computer. In this paper, we present a model for the efficiency of multigrid on a parallel computer that depends only on the efficiency of the smoother at each level. This model can be used to verify that it is indeed difficult to obtain extremely high efficiencies (>95%), but that it is relatively easy to obtain moderately high. efficiencies (70% to 85%). The model also indicates that moderately high efficiencies can still be achieved as the number of dimensions in the partial differential equation increases. We also present an implementation of the multigrid v-cycle that has achieved 84% efficiency on the 1,024-processor NCUBE/ten.

This paper uses a hierarchical transformation to re-interpret and restructure the fast adaptive composite grid method (FAC) and to provide a foundation for higher order extrapolation. Numerical experiments on model problems compare the performance characteristics of conventional multigrid and FAC both with and without extrapolation.

We compare standard parallel algorithms for solving linear parabolic partial differential equations. The comparison is based on the combined effect of their numerical properties and their parallel performance. We discuss the classical explicit methods (forward Euler, Heun and DuFort-Frankel), the standard implicit methods (BDF₁, BDF₂ and Crank-Nicolson), the line Hopscotch technique and the ADI formula of McKee and Mitchell. Timing results obtained on a 16-processor Intel hypercube are given. It is shown that parallelism does not alter the ranking of the methods unless the number of grid points per processor is very small.

We discuss blockspins for staggered fermions, i. e. averaging and interpolation procedures which are needed in a real space renormalization group approach to gauge theories with staggered fermions and in a multigrid approach to the computation of gauge covariant propagators. The discussion starts from the requirement that the symmetries of the free action should be preserved by the blocking procedure in the limit of a pure gauge. A definition of an averaging kernel as a solution of a gauge covariant eigenvalue equation is proposed, and the properties of a corresponding interpolation kernel are examined in the light of general criteria for good choices of blockspins. Some results of multigrid computations of bosonic propagators in an SU(2) gauge field in 4 dimensions are also presented.

I discuss a multigrid algorithm for calculating fermionic propagators in the lattice gauge theories. In order to preserve the infrared physics on the coarse lattice the coarse grid operators are obtained by an approximate real-space renormalization-group transformation, namely the Migdal-Kadanoff transformation. The resulting projection and the interpolation operators have a simple interpretation in terms a path integral for a fermionic particle on the lattice. The method was tested in two-dimensions in the presence of U(1) gauge-field, where it reduces the critical slowing down for the large values of β. The algorithm was implemented on the Connection-Machine.

Practical modifications of deterministic multigrid and conventional relaxation algorithms are discussed. New parameters need not be tuned but are determined by the algorithms themselves. One modification can be thought of as “updating on a last layer consisting of a single site”. It eliminates critical slowing down in computations of bosonic and fermionic propagators in a fixed volume. Here critical slowing down means divergence of asymptotic relaxation times as the propagators approach criticality. A remaining volume dependence is weak enough in case of bosons so that conjugate gradient can be outperformed. However, no answer can be given yet if the same is true for staggered fermions on lattices of realizable sizes. Numerical results are presented for propagators of bosons and of staggered fermions in 4-dimensional SU(2) gauge fields.

We present evidence that multigrid works for wave equations in disordered systems, e.g. in the presence of gauge fields, no matter how strong the disorder, but one needs to introduce a "neural computations" point of view into large scale simulations: First, the system must learn how to do the simulations efficiently, then do the simulation (fast). The method can also be used to provide smooth interpolation kernels which are needed in multigrid Monte Carlo updates.

Multigrid methods were invented for the solution of discretized partial differential equations in order to overcome the slowness of traditional algorithms by updates on various length scales. In the present work generalizations of multigrid methods for propagators in gauge fields are investigated. Gauge fields are incorporated in algorithms in a covariant way. The kernel C of the restriction operator which averages from one grid to the next coarser grid is defined by projection on the ground-state of a local Hamiltonian. The idea behind this definition is that the appropriate notion of smoothness depends on the dynamics. The ground-state projection choice of C can be used in arbitrary dimension and for arbitrary gauge group. We discuss proper averaging operations for bosons and for staggered fermions. The kernels C can also be used in multigrid Monte Carlo simulations, and for the definition of block spins and blocked gauge fields in Monte Carlo renormalization group studies. Actual numerical computations are performed in four-dimensional SU(2) gauge fields. We prove that our proposals for block spins are “good”, using renormalization group arguments. A central result is that the multigrid method works in arbitrarily disordered gauge fields, in principle. It is proved that computations of propagators in gauge fields without critical slowing down are possible when one uses an ideal interpolation kernel. Unfortunately, the idealized algorithm is not practical, but it was important to answer questions of principle. Practical methods are able to outperform the conjugate gradient algorithm in case of bosons. The case of staggered fermions is harder. Multigrid methods give considerable speed-ups compared to conventional relaxation algorithms, but on lattices up to 18⁴ conjugate gradient is superior.

We show numerically that the lowest eigenmodes of the two-dimensional Laplace operator with SU(2) gauge couplings and periodic boundary conditions are strongly localized. A connection is drawn to the Anderson localization problem. A new multigrid algorithm, capable of dealing with these modes, shows no critical slowing down for this problem independent of the disorder.

The principle of indirect elimination states that an algorithm for solving discretized differential equations can be used to identify its own bad-converging modes. When the number of bad-converging modes of the algorithm is not too large, the modes thus identified can be used to strongly improve the convergence. The method presented here is applicable to any linear algorithm like relaxation or multigrid. An example from theoretical physics, the Dirac equation in the presence of almost-zero-modes arising from instantons, is studied. Using the principle, bad-converging modes are removed efficiently. It is sketched how the method can be used for a Conjugate Gradient algorithm. Applied locally, the principle is one of the main ingredients of the Iteratively Smoothing Unigrid algorithm.

We present a new multigrid method called neural multigrid which is based on joining multigrid ideas with concepts from neural nets. The main idea is to use the Greenbaum criterion as a cost functional for the neural net. The algorithm is able to learn efficient interpolation operators in the case of the ordered Laplace equation with only a very small critical slowing down and with a surprisingly small amount of work comparable to that of a Conjugate Gradient solver

In the case of the two-dimensional Laplace equation with SU(2) gauge fields at β = 0 the learning exhibits critical slowing down with an exponent of about z≈0.4. The algorithm is able to find quite good interpolation operators in this case as well. Thereby it is proven that a practical true multigrid algorithm exists even for a gauge theory. An improved algorithm using dynamical blocks that will hopefully overcome the critical slowing down completely is sketched.

Not only in the field of high-performance computing (HPC), field programmable gate arrays (FPGAs) are a soaringly popular accelerator technology. However, they use a completely different programming paradigm and tool set compared to central processing units (CPUs) or even graphics processing units (GPUs), adding extra development steps and requiring special knowledge, hindering widespread use in scientific computing. To bridge this programmability gap, domain-specific languages (DSLs) are a popular choice to generate low-level implementations from an abstract algorithm description. In this work, we demonstrate our approach for the generation of numerical solver implementations based on the multigrid method for FPGAs from the same code base that is also used to generate code for CPUs using a hybrid parallelization of MPI and OpenMP. Our approach yields in a hardware design that can compute up to 11 V-cycles per second with an input grid size of 4096$\times$4096 and solution on the coarsest using the conjugate gradient (CG) method on a mid-range FPGA, beating vectorized, multi-threaded execution on an Intel Xeon processor.

A new so-called truncation error reduction method (TERM) is developed in this work. This is an iterative process which initially uses a coarse grid (2h) to estimate the truncation error and then reduces the error on the original grid (h). The purpose of this method is to use multigrid technique to achieve high-order accuracy on simple stencils.

This paper gives a solution to an open problem concerning the performance of various multilevel preconditioners for the linear finite element approximation of second-order elliptic boundary value problems with strongly discontinuous coefficients. By analyzing the eigenvalue distribution of the BPX preconditioner and multigrid V-cycle preconditioner, we prove that only a small number of eigenvalues may deteriorate with respect to the discontinuous jump or meshsize, and we prove that all the other eigenvalues are bounded below and above nearly uniformly with respect to the jump and meshsize. As a result, we prove that the convergence rate of the preconditioned conjugate gradient methods is uniform with respect to the large jump and meshsize. We also present some numerical experiments to demonstrate the theoretical results.

In this work we consider agglomeration-based physical frame discontinuous Galerkin (dG) discretization as an effective way to increase the flexibility of high-order finite element methods. The mesh free concept is pursued in the following (broad) sense: the computational domain is still discretized using a mesh but the computational grid should not be a constraint for the finite element discretization. In particular the discrete space choice, its convergence properties, and even the complexity of solving the global system of equations resulting from the dG discretization should not be influenced by the grid choice. Physical frame dG discretization allows to obtain mesh-independent h-convergence rates. Thanks to mesh agglomeration, high-order accurate discretizations can be performed on arbitrarily coarse grids, without resorting to very high-order approximations of domain boundaries. Agglomeration-based h-multigrid techniques are the obvious choice to obtain fast and grid-independent solvers. These features (attractive for any mesh free discretization) are demonstrated in practice with numerical test cases.

It is shown how various ideas that are well established for the solution of Poisson's equation using plane wave and multigrid methods, can be combined with wavelet concepts. The combination of wavelet concepts and multigrid techniques turns out to be particularly fruitful. We propose a modified multigrid V cycle scheme that is not only much simpler, but also more efficient than the standard V cycle. Whereas in the traditional V cycle the residue is passed to the coarser grid levels, this new scheme does not require the calculation of a residue. Instead it works with copies of the charge density on the different grid levels that were obtained from the underlying charge density on the finest grid by wavelet transformations. This scheme is not limited to the pure wavelet setting, where it is faster than the preconditioned conjugate gradient method, but equally well applicable for finite difference discretizations.

Iterative multiscale methods for electronic structure calculations offer several advantages for large-scale problems. Here we examine a nonlinear full approximation scheme (FAS) multigrid method for solving fixed potential and self-consistent eigenvalue problems. In principle, the expensive orthogonalization and Ritz projection operations can be moved to coarse levels, thus substantially reducing the overall computational expense. Results of the nonlinear multiscale approach are presented for simple fixed potential problems and for self-consistent pseudopotential calculations on large molecules. It is shown that, while excellent efficiencies can be obtained for problems with small numbers of states or well-defined eigenvalue cluster structure, the algorithm in its original form stalls for large-molecule problems with tens of occupied levels. Work is in progress to attempt to alleviate those difficulties.