Optimized partial semicoarsening multigrid algorithm for heat diffusion problems and anisotropic grids

The purpose of this work is to reduce the CPU time necessary to solve three two-dimensional linear diffusive problems governed by Laplace and Poisson equations, discretized with anisotropic grids. The Finite Difference Method is used to discretizate the differential equations with central differencing scheme. The systems of equations are solved with the lexicographic and red–black Gauss–Seidel methods associated to the geometric multigrid with correction scheme and V-cycle. The anisotropic grids considered have aspect ratios varying from 1/1024 up to 16,384. Four algorithms are compared: full coarsening, semicoarsening, full coarsening followed by semicoarsening and partial semicoarsening. Three new restriction schemes for anisotropic grids are proposed: geometric half weighting, geometric full weighting and partial weighting. Comparisons are made among these three new schemes and some restriction schemes presented in literature: injection, half weighting and full weighting. The prolongation process used is the bilinear interpolation. It is also investigated the effects on the CPU time caused by: the number of inner iterations of the smoother, the number of grids and the number of grid elements. It was verified that the partial semicoarsening algorithm is the fastest. This work also provides the optimum values of the multigrid components for this algorithm.     

波形松弛算法及其在计算流体力学中的应用

本文介绍求解线性常系数微分代数方程组的波形松弛算法, 基于Laplace积分变换得到该算法新的收敛理论. 进一步将波形松弛算法应用于求解非定常Stokes方程, 介绍并讨论了连续时间波形松弛算法CABSOR算法和离散时间波形松弛算法DABSOR算法.     

Sparse-grid finite-volume multigrid for 3D-problems

We introduce a multigrid algorithm for the solution of a second order elliptic equation in three dimensions. For the approximation of the solution we use a partially ordered hierarchy of finite-volume discretisations. We show that there is a relation with semicoarsening and approximation by more-dimensional Haar wavelets. By taking a proper subset of all possible meshes in the hierarchy, a sparse grid finite-volume discretisation can be constructed.The multigrid algorithm consists of a simple damped point-Jacobi relaxation as the smoothing procedure, while the coarse grid correction is made by interpolation from several coarser grid levels.The combination of sparse grids and multigrid with semi-coarsening leads to a relatively small number of degrees of freedom,N, to obtain an accurate approximation, together with anO(N) method for the solution. The algorithm is symmetric with respect to the three coordinate directions and it is fit for combination with adaptive techniques.To analyse the convergence of the multigrid algorithm we develop the necessary Fourier analysis tools. All techniques, designed for 3D-problems, can also be applied for the 2D case, and — for simplicity — we apply the tools to study the convergence behaviour for the anisotropic Poisson equation for this 2D case.     

Piecewise homotopy analysis method and convergence analysis for formally well-posed initial value problems

In this paper, we apply the Schwarz waveform relaxation (SWR) method to the one-dimensional Schrödinger equation with a general linear or a nonlinear potential. We propose a new algorithm for the Schrödinger equation with time-independent linear potential, which is robust and scalable up to 500 subdomains. It reduces significantly computation time compared with the classical algorithms. Concerning the case of time-dependent linear potential or the nonlinear potential, we use a preprocessed linear operator for the zero potential case as a preconditioner which leads to a preconditioned algorithm. This ensures high scalability. In addition, some newly constructed absorbing boundary conditions are used as the transmission conditions and compared numerically.     

Analysis of two new parareal algorithms based on the Dirichlet-Neumann/Neumann-Neumann waveform relaxation method for the heat equation

The Dirichlet-Neumann and Neumann-Neumann waveform relaxation methods are nonoverlapping spatial domain decomposition methods to solve evolution problems, while the parareal algorithm is in time parallel fashion. Based on the combinations of these space and time parallel strategies, we present and analyze two parareal algorithms based on the Dirichlet-Neumann and the Neumann-Neumann waveform relaxation method for the heat equation by choosing Dirichlet-Neumann/Neumann-Neumann waveform relaxation as two new kinds of fine propagators instead of the classical fine propagator. Both new proposed algorithms could be viewed as a space-time parallel algorithm, which increases the parallelism both in space and in time. We derive for the heat equation the convergence results for both algorithms in one spatial dimension. We also illustrate our theoretical results with numerical experiments finally.

     

Continuous-time accelerated block successive overrelaxation methods for time-dependent Stokes equations

In order to solve the time-dependent Stokes equation, we follow the “Method of Lines” to obtain structured linear constant-coefficient differential–algebraic equations (DAEs). By taking advantage of the structure, we propose a class of waveform relaxation methods, called continuous-time accelerated block SOR (CABSOR) methods, for solving the obtained DAEs. The new methods are theoretically analyzed. The theory is applied to a two-dimensional time-dependent Stokes equation and verified by numerical experiments.     

The Frequency Decomposition Multilevel Method: A robust additive hierarchical basis preconditioner

Hackbusch's frequency decomposition multilevel method is characterized by the application of three additional coarse-grid corrections in parallel to the standard one. Each coarse-grid correction was designed to damp errors from a different part of the frequency spectrum. In this paper, we introduce a cheap variant of this method, partly based on semicoarsening, which demands fewer recursive calls than the original version. Using the theory of the additive Schwarz methods, we will prove robustness of our method as a preconditioner applied to anisotropic equations.

     

Absorbing boundary conditions for the wave equation and parallel computing

Absorbing boundary conditions have been developed for various types of problems to truncate infinite domains in order to perform computations. But absorbing boundary conditions have a second, recent and important application: parallel computing. We show that absorbing boundary conditions are essential for a good performance of the Schwarz waveform relaxation algorithm applied to the wave equation. In turn this application gives the idea of introducing a layer close to the truncation boundary which leads to a new way of optimizing absorbing boundary conditions for truncating domains. We optimize the conditions in the case of straight boundaries and illustrate our analysis with numerical experiments both for truncating domains and the Schwarz waveform relaxation algorithm.

     

Preconditioning waveform relaxation iterations for differential systems

We discuss preconditioning and overlapping of waveform relaxation methods for sparse linear differential systems. It is demonstrated that these techniques significantly improve the speed of convergence of the waveform relaxation iterations resulting from application of various modes of block Gauss-Jacobi and block Gauss-Seidel methods to differential systems. Numerical results are presented for linear systems resulting from semi-discretization of the heat equation in one and two space variables. It turns out that overlapping is very effective for the system corresponding to the one-dimensional heat equation and preconditioning is very effective for the system corresponding to the two-dimensional case.The work of the second author was supported by the National Science Foundation under grant NSF DMS 92-08048.     

Spectral collocation and waveform relaxation methods for nonlinear delay partial differential equations

We investigate Chebyshev spectral collocation and waveform relaxation methods for nonlinear delay partial differential equations. Waveform relaxation methods allow to replace the system of nonlinear differential equations resulting from the application of spectral collocation methods by a sequence of linear problems which can be effectively integrated in a parallel computing environment by highly stable implicit methods. The effectiveness of this approach is illustrated by numerical experiments on the Hutchinson's equation. The boundedness of waveform relaxation iterations is proved for the Hutchinson's equation. This result is used in the proof of the superlinear convergence of the iterations.     

Convergence of discrete time waveform relaxation methods

Numerical Algorithms - This paper concerns the discrete time waveform relaxation (DWR) methods for ordinary differential equations (ODEs). We present a general algorithm of constructing the DWR...     

ON THE CONVERGENCE OF WAVEFORM RELAXATION METHODS FOR LINEAR INITIAL VALUE PROBLEMS

We study a class of blockwise waveform relaxation methods,and investigate its con-vergence properties in both asymptotic and monotone senses.In addition,the monotoneconvergence rates between different pointwise/blockwise waveform relaxation methods re-sulted from different matrix splittings,and those between the pointwise and blockwisewaveform relaxation methods are discussed in depth.     

Semi-discrete Schwarz waveform relaxation algorithms for reaction diffusion equations

For time dependent problems, the Schwarz waveform relaxation (SWR) algorithm can be analyzed both at the continuous and semi-discrete level. For consistent space discretizations, one would naturally expect that the semi-discrete algorithm performs as predicted by the continuous analysis. We show in this paper for the reaction diffusion equation that this is not always the case. We consider two space discretization methods—the 2nd-order central finite difference method and the 4th-order compact finite difference method, and for each method we show that the semi-discrete SWR algorithm with Dirichlet transmission condition performs as predicted by the continuous analysis. However, for Robin transmission condition the semi-discrete SWR algorithm performs worse than predicted by the continuous analysis. For each type of transmission conditions, we show that the convergence factors of the semi-discrete SWR algorithm using the two space discretization methods are (almost) equal. Numerical results are presented to validate our conclusions.     

Overlapping Schwarz waveform relaxation method for the solution of the reaction-diffusion equation

We are interested in solving time dependent problems using domain decomposition methods. In the classical approach, one discretizes first the time dimension and then one solves a sequence of steady problems by a domain decomposition method. In this article, we treat directly the time dependent problem and we study a Schwarz waveform relaxation algorithm for the convection diffusion equation. We study the convergence of the overlapping Schwarz waveform relaxation method for solving the reaction-diffusion equation over multi-overlapped subdomains. Also we will show that the method converges linearly and superlinearly over long and short time intervals, and the convergence depends on the size of overlap. Numerical results are presented from solutions of a specific model problems to demonstrate the convergence, linear and superlinear, and the role of the overlap size.     

Analysis of a new parareal algorithm based on waveform relaxation method for time-periodic problems

We present a new parallel algorithm for time-periodic problems by combining the waveform relaxation method and the parareal algorithm, which performs the parallelism both in sub-systems and in time. In the new algorithm, the waveform relaxation propagator is chosen as a new fine propagator instead of the classical fine propagator. And because of the characteristic of time-periodic problems, the new parareal waveform relaxation algorithm needs to solve a periodic coarse problem at the coarse level in each iteration. The new algorithm is proved to converge linearly at most. Then the theoretic parallel efficiency of the new algorithm is also considered. Numerical experiments confirm our analysis finally.     

Overlapping Schwarz Waveform Relaxation for the Heat Equation in N Dimensions

We analyze overlapping Schwarz waveform relaxation for the heat equation in n spatial dimensions. We prove linear convergence of the algorithm on unbounded time intervals and superlinear convergence on bounded time intervals. In both cases the convergence rates are shown to depend on the size of the overlap. The linear convergence result depends also on the number of subdomains because it is limited by the classical steady state result of overlapping Schwarz for elliptic problems. However the superlinear convergence result is independent of the number of subdomains. Thus overlapping Schwarz waveform relaxation does not need a coarse space for robust convergence independent of the number of subdomains, if the algorithm is in the superlinear convergence regime. Numerical experiments confirm our analysis. We also briefly describe how our results can be extended to more general parabolic problems.     

Anisotropic Total Variation Filtering

Total variation regularization and anisotropic filtering have been established as standard methods for image denoising because of their ability to detect and keep prominent edges in the data. Both methods, however, introduce artifacts: In the case of anisotropic filtering, the preservation of edges comes at the cost of the creation of additional structures out of noise; total variation regularization, on the other hand, suffers from the stair-casing effect, which leads to gradual contrast changes in homogeneous objects, especially near curved edges and corners. In order to circumvent these drawbacks, we propose to combine the two regularization techniques. To that end we replace the isotropic TV semi-norm by an anisotropic term that mirrors the directional structure of either the noisy original data or the smoothed image. We provide a detailed existence theory for our regularization method by using the concept of relaxation. The numerical examples concluding the paper show that the proposed introduction of an anisotropy to TV regularization indeed leads to improved denoising: the stair-casing effect is reduced while at the same time the creation of artifacts is suppressed.     

一类求解反应扩散方程的Newton波形松弛方法

对反应扩散方程提出一种新型的Newton波形松弛方法,并给出此方法的误差估计式.通过与传统的波形松弛方法比较,这种Newton波形松弛方法有更快的收敛性,且收敛速度不随网格加密而减慢.这种方法可以保持传统波形松弛方法可并行的特点.最后通过数值算例验证这种方法的有效性.     

An efficient algorithm for the parallel solution of high-dimensional differential equations

The study of high-dimensional differential equations is challenging and difficult due to the analytical and computational intractability. Here, we improve the speed of waveform relaxation (WR), a method to simulate high-dimensional differential-algebraic equations. This new method termed adaptive waveform relaxation (AWR) is tested on a communication network example. Further, we propose different heuristics for computing graph partitions tailored to adaptive waveform relaxation. We find that AWR coupled with appropriate graph partitioning methods provides a speedup by a factor between 3 and 16.     

High performance parallel numerical methods for Volterra equations with weakly singular kernels

Non-stationary discrete time waveform relaxation methods for Abel systems of Volterra integral equations using fractional linear multistep formulae are introduced. Fully parallel discrete waveform relaxation methods having an optimal convergence rate are constructed. A significant expression of the error is proved, which allows us to estimate the number of iterations needed to satisfy a prescribed tolerance and allows us to identify the problems where the optimal methods offer the best performance. The numerical experiments confirm the theoretical expectations.