Image analysis using multigrid relaxation methods

Image analysis problems, posed mathematically as variational principles or as partial differential equations, are amenable to numerical solution by relaxation algorithms that are local, iterative, and often parallel. Although they are well suited structurally for implementation on massively parallel, locally interconnected computational architectures, such distributed algorithms are seriously handi capped by an inherent inefficiency at propagating constraints between widely separated processing elements. Hence, they converge extremely slowly when confronted by the large representations of early vision. Application of multigrid methods can overcome this drawback, as we showed in previous work on 3-D surface reconstruction. In this paper, we develop multiresolution iterative algorithms for computing lightness, shape-from-shading, and optical flow, and we examine the efficiency of these algorithms using synthetic image inputs. The multigrid methodology that we describe is broadly applicable in early vision. Notably, it is an appealing strategy to use in conjunction with regularization analysis for the efficient solution of a wide range of ill-posed image analysis problems.     

Theoretical analysis of some spectral multigrid methods

We develop a theoretical analysis of a multigrid algorithm applied to spectral element discretization of linear elliptic problems. For a 1-D problem with non-constant coefficients we prove essentially the independence of the two-level convergence factor with respect to both the degree of the polynomial approximation and the number of spectral elements. We also sketch some ideas for the analysis of the 2-D case when only one spectral element is involved.     

Schwarz waveform relaxation methods for parabolic equations in space-frequency domain

Some Schwarz waveform relaxation algorithms based on frequency domain analysis for parabolic equations are proposed and analyzed. In this paper we mainly study an overlapping process with Dirichlet transmission conditions and a non-overlapping process with Robin transmission conditions. The convergence conditions for these algorithms are also obtained by our frequency domain analysis. Numerical experiments are given to illustrate effectiveness of the algorithms.     

Delay dependent estimates for waveform relaxation methods for neutral differential-functional systems

In this paper, the problem of delay dependent error estimates for waveform relaxation methods applied to Volterra type systems of functional-differential equations of neutral type including systems of differential-algebraic equations is discussed. Under a Lipschitz condition (with delay dependent right-hand side) imposed on the so-called splitting function it is shown how the error estimates depend on the character of delays and that for this reason they are better than the known error estimates for relaxation methods. It is proved that under some assumptions the exact solution can be obtained after a finite number of steps of the iterative process, i.e., we prove that the waveform relaxation methods have the same property as the classical method of steps for solving delay-differential equations with nonvanishing delays. We also show the convergence of the waveform relaxation method without assuming that the spectral radius of the corresponding matrix related to the Lipschitz coefficients for the neutral argument is less than one.     

Analysis of a multigrid method for a transport equation by numerical Fourier analysis

In this paper, we perform Fourier analysis for a multigrid method with two-cell μ-line relaxation for solving isotropic transport equations. Our numerical results show that the Fourier analysis prediction for convergence rates is more accurate than that previously found by matrix analysis.     

Convergence and comparisons of waveform relaxation methods for initial value problems of linearODE systems

In this paper we investigate waveform relaxation (WR) methods for solving initial value problems of linearODE systems. Some sufficient conditions for convergence are proposed. A class ofWR AOR, WR SOR, andWR JOR methods is defined and their convergence is discussed. The asymptotic rates of convergence of two differentWR methods are compared.     

Convergence analysis of geometrical multigrid methods for solving data-sparse boundary element equations

The convergence analysis of multigrid methods for boundary element equations arising from negative-order pseudo-differential operators is quite different from the usual finite element multigrid analysis for elliptic partial differential equations. In this paper, we study the convergence of geometrical multigrid methods for solving large-scale, data-sparse boundary element equations. In particular, we investigate multigrid methods for \(\mathcal{H}\)-matrices arising from the adaptive cross approximation to the single layer potential operator.     

Coupled algebraic multigrid methods for the Oseen problem

We provide a concept combining techniques known from geometric multigrid methods for saddle point problems (such as smoothing iterations of Braess- or Vanka-type) and from algebraic multigrid (AMG) methods for scalar problems (such as the construction of coarse levels) to a coupled algebraic multigrid solver. Coupled here is meant in contrast to methods, where pressure and velocity equations are iteratively decoupled (pressure correction methods) and standard AMG is used for the solution of the resulting scalar problems. To prove the efficiency of our solver experimentally, it is applied to finite element discretizations of real life industrial problems.     

Accuracy assessment and waveform analysis of CryoSat-2 SARIn mode data over Antarctica

ABSTRACT

The new synthetic aperture radar interferometric (SARIn) measurement mode of CryoSat-2 provides better performance on the rough topography of the ice sheet margins than that of conventional radar altimetry. We assess the accuracy of CryoSat-2 SARIn mode data from Baseline C product of the European Space Agency (ESA), through comparison with two airborne laser altimeters on NASA IceBridge missions. The time difference between two compared data was limited to 30 days resulting in a reduction in the random error of ~0.3 m. We also assess the sensitivity of ESA retracker to surface slope, roughness and firn density using the mean waveform and retracked bin derived from CryoSat-2 Level 1B and Level 2i product. The ESA retracker appears to be sensitive to the surface slope and roughness according to the different leading edge shape and the retracked bin locations, however, not sensitive to the different firn density over four ice shelves. The modelled echo waveforms as SARIn are also used to analyse the impacts of surface characteristics (slope, roughness, and penetration depth) on echo waveform shape. It illustrates that the processes for ESA product fail to differentiate the changes in near-surface dielectric properties and determine radar-signal-penetration depth.     

On monotone including nonlinear multigrid methods and applications

In recent years, some work has been devoted to construct multigrid methods for solving nonlinear systems which compute monotone including convergent sequences of sub- and supersolutions. Mainly with regard to the numerical solution of quasilinear partial differential equations we improve and generalize some of the existing results. In this paper we show that the monotone enclosure of the multigrid method follows from the monotone enclosure of the smoother. The theoretical results are confirmed by examples of realistic problems.     

Convergence analysis of multigrid methods with collective point smoothers for optimal control problems

In this paper we consider multigrid methods for solving saddle point problems. The choice of an appropriate smoothing strategy is a key issue in this case. Here we focus on the widely used class of collective point smoothers. These methods are constructed by a point-wise grouping of the unknowns leading to, e.g., collective Richardson, Jacobi or Gauss-Seidel relaxation methods. Their smoothing properties are well-understood for scalar problems in the symmetric and positive definite case. In this work the analysis of these methods is extended to a special class of saddle point problems, namely to the optimality system of optimal control problems. For elliptic distributed control problems we show that the convergence rates of multigrid methods with collective point smoothers are bounded independent of the grid size and the regularization (or cost) parameter.     

A parallel Aitken-additive Schwarz waveform relaxation suitable for the grid

The objective of this paper is to describe a grid-efficient parallel implementation of the Aitken–Schwarz waveform relaxation method for the heat equation problem. This new parallel domain decomposition algorithm, introduced by Garbey [M. Garbey, A direct solver for the heat equation with domain decomposition in space and time, in: Springer Ulrich Langer et al. (Ed.), Domain Decomposition in Science and Engineering XVII, vol. 60, 2007, pp. 501–508], generalizes the Aitken-like acceleration method of the additive Schwarz algorithm for elliptic problems. Although the standard Schwarz waveform relaxation algorithm has a linear rate of convergence and low numerical efficiency, it can be easily optimized with respect to cache memory access and it scales well on a parallel system as the number of subdomains increases. The Aitken-like acceleration method transforms the Schwarz algorithm into a direct solver for the parabolic problem when one knows a priori the eigenvectors of the trace transfer operator. A standard example is the linear three dimensional heat equation problem discretized with a seven point scheme on a regular Cartesian grid. The core idea of the method is to postprocess the sequence of interfaces generated by the additive Schwarz wave relaxation solver. The parallel implementation of the domain decomposition algorithm presented here is capable of achieving robustness and scalability in heterogeneous distributed computing environments and it is also naturally fault tolerant. All these features make such a numerical solver ideal for computational grid environments. This paper presents experimental results with a few loosely coupled parallel systems, remotely connected through the internet, located in Europe, Russia and the USA.     

Radiosity and relaxation methods

To date, there has been some confusion in the computer graphics community about how the progressive radiosity (PR) method relates to standard numerical methods for solving linear systems of equations. We show that PR is actually equivalent to the combination of two numerical analysis techniques known as Southwell relaxation and Jacobi iteration. A new overshooting method similar to over relaxation can accelerate the convergence of the iterative radiosity methods     

Convergence conditions on waveform relaxation of general differential-algebraic equations

In the paper, we show some new convergence conditions on waveform relaxation (WR) for general differential-algebraic equations (DAEs). The main conclusion is that the convergence conditions on index r+1 can be derived from that of index r, in which the corresponding system is composed by ordinary differential equations if r=0. The approach of analysing relaxation process is novel for WR solutions of DAEs. It is also the first time to give the convergence conclusions for general index systems of DAEs in the WR field.     

On the convergence of spectral multigrid methods for solving periodic problems

The spectral multigrid method combines the efficiencies of the spectral method and the multigrid method. In this paper, we show that various spectral multigrid methods have constant convergence rates (independent of the number of unknowns in the linear system, to be solved) in their multilevel iterations for solving periodic problems.     

Alternating splitting waveform relaxation method and its successive overrelaxation acceleration

For the large sparse implicit linear initial value problem, we present a block successive overrelaxation scheme for the alternating direction implicit waveform relaxation method to further accelerate its convergence speed, and discuss the convergence property of the resulting iteration method in detail. Numerical implementations about several non-Hermitian implicit linear initial value problems show that the alternating direction implicit waveform relaxation method is very effective, and the block successive overrelaxation technique really accelerates its convergence speed.     

A mixed strategy of combining evolutionary algorithms with multigrid methods

Multigrid methods have been proven to be an efficient approach in accelerating the convergence rate of numerical algorithms for solving partial differential equations. This paper investigates whether multigrid methods are helpful to accelerate the convergence rate of evolutionary algorithms for solving global optimization problems. A novel multigrid evolutionary algorithm is proposed and its convergence is proven. The algorithm is tested on a set of 13 well-known benchmark functions. Experiment results demonstrate that multigrid methods can accelerate the convergence rate of evolutionary algorithms and improve their performance.     

Solution of piecewise-linear ordinary differential equations using waveform relaxation and Laplace transforms

Piecewise-linear (PWL) functions are frequently used to describe the nonlinear branch equations of nonlinear devices in LSI circuits. New techniques for the solution of the differential equations describing the behavior of piecewise-linear circuits will be presented. These techniques are based on the waveform relaxation method to decouple the system equations and Laplace transform techniques to solve the decoupled equations. Several desirable features of the resulting algorithm are discussed.     

Scalable implementation of multigrid methods using partial semi-aggregation of coarse grids

The Journal of Supercomputing - Multigrid methods are efficient and fast algorithms for solving elliptic equations. However, they suffer from the degradation of parallel efficiency on coarser...     

Fourier analysis of semi-discrete and space-time stabilized methods for the advective-diffusive-reactive equation: I. SUPG

The goal of this paper is twofold. One the one side, the most common transient Galerkin and SUPG methods are analyzed for the one-dimensional advection-diffusion-reaction equation. The methods analyzed include semi-discrete, time-discontinuous space-time stabilized finite element methods and several predictor multi-corrector versions of them. On the other hand, in the framework of explicit predictor multi-corrector algorithms a novel treatment of the source terms is proposed and analyzed. The technique consists of the diagonally implicit treatment of the negative or dissipative source terms. This technique increases dramatically the phase and damping accuracy of classical explicit methods and, at the same time, removes the source terms from stability considerations for low viscosity flows, thus, leading to very economic procedures.