Search

The Lloyd algorithm originated in the context of optimal quantization and represents a fixed point iteration for computing an optimal quantizer. Reducing average distortion at every step, it constructs a Voronoi partition of the domain and replaces each generator with the centroid of the corresponding Voronoi cell. Optimal quantization is obtained in the case of a centroidal Voronoi tessellation (CVT), which is a special Voronoi tessellation of a domain Ω ϵ ℝd having the property that the generators of the Voronoi diagram are also the centers of mass, with respect to a given density function ? ⩾ 0, of the corresponding Voronoi cells. The Lloyd iteration is currently the most popular and elegant algorithm for computing CVTs and optimal quantizers, but many questions remain about its convergence, especially in d-dimensional spaces (d > 1). In this paper, we prove that any limit point of the Lloyd iteration in any dimensional spaces is nondegenerate provided that Ω is a convex and bounded set and ? belongs to L¹(Ω) and is positive almost everywhere. This ensures that the fixed point map remains closed and hence the standard theory of descent methods guarantees weak global convergence of the Lloyd iteration to the set of nondegenerate fixed point quantizers. While previously only conjectured, the convergence properties of the Lloyd iteration are rigorously justified under such minimal regularity assumptions on the density functional. The results presented in this paper go beyond existing convergence theories for CVTs and optimal quantization related algorithms and should be of interest to both the mathematical and engineering communities. [ABSTRACT FROM AUTHOR]

In this paper, an efficient and stable numerical algorithm for computing multiple saddle points with symmetries is developed by modifying the local minimax method established in [Y. Li and J. Zhou, SIAM J. Sci. Comput. 23 (2001), pp. 840--865; Y. Li and J. Zhou, SIAM J. Sci. Comput., 24 (2002), pp. 840--865]. First an invariant space is defined in a more general sense and a principle of invariant criticality is proved for the generalization. Then the orthogonal projection to the invariant space is used to preserve the invariance and to reduce computational error across iterations. Simple averaging formulas are used for the orthogonal projections. Numerical computations of examples with various symmetries, of which some can and others cannot be characterized by a compact group of linear isomorphisms, are carried out to confirm the theory and to illustrate applications. The mathematical features of various problems demonstrated in these examples fall into two categories: nodal solutions of saddle-point type with large Morse indices and nonradial positive solutions via symmetry breaking in radially symmetric elliptic problems. The new numerical algorithm generates these rather unstable solutions in an efficient and stable way. The existence of many unstable solutions and their behavior found in this paper remain to be investigated. [ABSTRACT FROM AUTHOR]

The Lloyd algorithm originated in the context of optimal quantization and represents a fixed point iteration for computing an optimal quantizer. Reducing average distortion at every step, it constructs a Voronoi partition of the domain and replaces each generator with the centroid of the corresponding Voronoi cell. Optimal quantization is obtained in the case of a centroidal Voronoi tessellation (CVT), which is a special Voronoi tessellation of a domain Ω ϵ ℝd having the property that the generators of the Voronoi diagram are also the centers of mass, with respect to a given density function ? ⩾ 0, of the corresponding Voronoi cells. The Lloyd iteration is currently the most popular and elegant algorithm for computing CVTs and optimal quantizers, but many questions remain about its convergence, especially in d-dimensional spaces (d > 1). In this paper, we prove that any limit point of the Lloyd iteration in any dimensional spaces is nondegenerate provided that Ω is a convex and bounded set and ? belongs to L¹(Ω) and is positive almost everywhere. This ensures that the fixed point map remains closed and hence the standard theory of descent methods guarantees weak global convergence of the Lloyd iteration to the set of nondegenerate fixed point quantizers. While previously only conjectured, the convergence properties of the Lloyd iteration are rigorously justified under such minimal regularity assumptions on the density functional. The results presented in this paper go beyond existing convergence theories for CVTs and optimal quantization related algorithms and should be of interest to both the mathematical and engineering communities. [ABSTRACT FROM AUTHOR]

A well-known generalization of Shannon's sampling theorem states that a bandlimited function can be reconstructed from its periodic nonuniformly spaced samples if the effective sampling rate is at least the Nyquist rate. Analogous to Shannon's sampling theorem this generalization requires that an infinite number of samples be available, which, however, is never the case in practice. Most existing reconstruction methods for periodic nonuniform sampling yield very low order (often not even first order) accuracy when only a finite number of samples is given. In this paper we propose a fast, numerically robust, root-exponential accurate reconstruction method. The efficiency and accuracy of the algorithm is obtained by fully exploiting the sampling structure and utilizing localized Fourier analysis. We discuss applications in analog-to-digital conversion where nonuniform periodic sampling arises in various situations. Finally, we demonstrate the performance of our algorithm by numerical examples. [ABSTRACT FROM AUTHOR]

We present and study a nonconforming domain decomposition method for the discretization of the three-dimensional Stokes problem in the velocity-pressure formulation. The approximation is based on some local mixed finite elements for nonmatching tetrahedral grids. The aim pursued is a systematic construction of the mortared discrete velocity space, the pressure being not subjected to any matching constraints across the interfaces. Using the bubble stabilization techniques, applied in Brezzi and Marini's paper to the three fields method [Math. Cornp., 70 (2001), pp. 911-934], allows us to define an algorithm which is easy to implement. The numerical analysis relies on the pressure-splitting argument of Boland and Nicolaides and allows us to establish an inf-sup condition with a constant that does not depend on the mesh size or on the total number of the subdomains. Then, by the Berger-Scott-Strang lemma written down for our saddle point system we derive optimal accuracy results. [ABSTRACT FROM AUTHOR]

In this paper, we propose a nonoverlapping domain decomposition method for solving the three-dimensional Maxwell equations, based on the edge element discretization. For the Schur complement system on the interface, we construct an efficient preconditioner by introducing two special coarse subspaces defined on the nonoverlapping sub domains. It is shown that the condition number of the preconditioned system grows only polylogarithmically with the ratio between the subdomain diameter and the finite element mesh size but possibly depends on the jumps of the coefficients. [ABSTRACT FROM AUTHOR]

In this paper we show that the lagged diffusivity fixed point algorithm introduced by Vogel and Oman in [SIAM J. Sci. Comput., 17 (1996), pp. 227­238] to solve the problem of total variation denoising, proposed by Rudin, Osher, and Fatemi in [Phys. D, 60 (1992), pp. 259­268], is a particular instance of a class of algorithms introduced by Voss and Eckhardt in [Computing, 25 (1980), pp. 243­251], whose origins can be traced back to Weiszfeld's original work for minimizing a sum of Euclidean lengths [Tôhoku Math. J., 43 (1937), pp. 355­386]. There have recently appeared several proofs for the convergence of this algorithm [G. Aubert et al., Technical report 94-01, Informatique, Signaux et Systèmes de Sophia Antipolis, 1994], [A. Chambolle and P.-L. Lions, Technical report 9509, CEREMADE, 1995], and [D. C. Dobson and C. R. Vogel, SIAM J. Numer. Anal., 34 (1997), pp. 1779­1791]. Here we present a proof of the global and linear convergence using the framework introduced in [H. Voss and U. Eckhart, Computing, 25 (1980), pp. 243­251] and give a bound for the convergence rate of the fixed point iteration that agrees with our experimental results. These results are also valid for suitable generalizations of the fixed point algorithm. [ABSTRACT FROM AUTHOR]

This paper is concerned with a classical denoising and deblurring problem in image recovery. Our approach is based on a variational method. By using the Legendre­Fenchel transform, we show how the nonquadratic criterion to be minimized can be split into a sequence of half-quadratic problems easier to solve numerically. First we prove an existence and uniqueness result, and then we describe the algorithm for computing the solution and we give a proof of convergence. Finally, we present some experimental results for synthetic and real images. [ABSTRACT FROM AUTHOR]

A cell-centered finite volume method is proposed to approximate numerically the solution to the steady convection-diffusion equation on unstructured meshes of $d$-simplexes, where $d\geq 2$ is the spatial dimension. The method is formally second-order accurate by means of a piecewise linear reconstruction within each cell and at mesh vertices. An algorithm is provided to calculate nonnegative and bounded weights. Face gradients, required to discretize the diffusive fluxes, are defined by a nonlinear strategy that allows us to demonstrate the existence of a maximum principle. Finally, a set of numerical results documents the performance of the method in treating problems with internal layers and solutions with strong gradients. [ABSTRACT FROM AUTHOR]

Using Smolyak's construction [S. A. Smolyak, Dokl. Akad. Nauk SSSR, 4 (1963), pp. 240--243], we derive a new algorithm for approximating multivariate functions over bounded or unbounded regions in $\R^s$ with the error measured in a weighted L1-norm. We provide upper bounds for the algorithm's cost and error for a class of functions whose mixed first order partial derivatives are bounded in the L1-norm. In particular, we prove that the error and the cost (measured in terms of the number of function evaluations) satisfy the relation $$ error \le \frac{s\,\exp\big(\frac1{12(s-1)}\big)}{(s-1)\pi}\, \left(\frac{e\,\ln(\mbox{cost})}{(s-1)\sqrt{2}\ln(2)}\right)^{2(s-1)}\, \frac1{{cost}} $$ whenever the cost is sufficiently large relative to the number s of variables. More specifically, the inequality holds when $q\ge2(s-1)$, where q is a special parameter defining the refinement level in Smolyak's algorithm, and hence the number of function evaluations used by the algorithm. We also discuss extensions of the results to the spaces with the derivatives bounded in Lp-norms. [ABSTRACT FROM AUTHOR]

A BDDC (balancing domain decomposition by constraints) method is developed for elliptic equations, with discontinuous coefficients, discretized by mortar finite element methods for geometrically nonconforming partitions in both two and three space dimensions. The coarse component of the preconditioner is defined in terms of one mortar constraint for each edge/face, which is the intersection of the boundaries of a pair of subdomains. A condition number bound of the form C maxi{(1 + log(Hi/hi))2} is established under certain assumptions on the geometrically nonconforming subdomain partition in the three-dimensional case. Here Hi and hi are the subdomain diameters and the mesh sizes, respectively. In the geometrically conforming case and the geometrically nonconforming cases in two dimensions, no assumptions on the subdomain partition are required. This BDDC preconditioner is also shown to be closely related to the Neumann-Dirichlet version of the FETI-DP algorithm. The results are illustrated by numerical experiments which confirm the theoretical results. [ABSTRACT FROM AUTHOR]

We derive two reformulations of the C¹ Hermite subdivision scheme introduced by Merrien. One where we separate computation of values and derivatives and one based of refinement of a control polygon. We show that the latter leads to a subdivision matrix which is totally positive. Based on this we give algorithms for constructing subdivision curves that preserve positivity, monotonicity, and convexity. [ABSTRACT FROM AUTHOR]

We consider the behavior of certain adaptive timestepping methods, based upon embedded explicit Runge--Kutta pairs, when applied to dissipative ODEs. It has been observed numerically that the standard local error controls can impart desirable stability properties, but this has been rigorously verified only for very special, low-order, Runge--Kutta pairs. The rooted-tree expansion of a certain quadratic form, central to the stability theory of Runge--Kutta methods, is derived. This, together with key assumptions on the sequence of accepted time-steps and the local error estimate, provides a general explanation for the observed stability of such algorithms on dissipative problems. Under these assumptions, which are expected to hold for "typical" numerical trajectories, two different results are proved. First, for a large class of embedded Runge--Kutta pairs of order $(1,2)$, controlled on an error-per-unit-step basis, all such numerical trajectories will eventually enter a particular bounded set. This occurs for sufficiently small tolerances independent of the initial conditions. Second, for pairs of arbitrary orders $(p-1,p)$, operating under either error-per-step or error-per-unit-step control, similar results are obtained when an additional structural assumption (that should be valid for many cases of interest) is imposed on the dissipative vector field. Numerical results support both the analysis and the assumptions made. [ABSTRACT FROM AUTHOR]

We introduce a nonoverlapping variant of the Schwarz waveform relaxation algorithm for wave propagation problems with variable coefficients in one spatial dimension. We derive transmission conditions which lead to convergence of the algorithm in a number of iterations equal to the number of sub domains, independently of the length of the time interval. These optimal transmission conditions are in general nonlocal, but we show that the nonlocality depends on the time interval under consideration, and we introduce time windows to obtain optimal performance of the algorithm with local transmission conditions in the case of piecewise constant wave speed. We show that convergence in two iterations can be achieved independently of the number of subdomains in that case. The algorithm thus scales optimally with the number of sub domains, provided the time windows are chosen appropriately. For continuously varying coefficients we prove convergence of the algorithm with local transmission conditions using energy estimates. We then introduce a finite volume discretization which permits computations on nonmatching grids, and we prove convergence of the fully discrete Schwarz waveform relaxation algorithm. We finally illustrate our analysis with numerical experiments. [ABSTRACT FROM AUTHOR]

It has been shown recently that optimization-based nonoverlapping domain decom- position algorithms are connected to many well-known algorithms. Using a gradient-type iterative strategy for the optimization problem, we present further discussion on how to develop various algo- rithms that can integrate subdomain solvers into a solver for the problem in the whole domain. In particular, the algorithms we discuss can be used to develop efficient solvers of multidisciplinary prob- lems which are constructed using existing subdomain solvers without the need for making changes in the latter. [ABSTRACT FROM AUTHOR]

The iterative substructuring methods, also known as Schur complement methods, form one of two important families of domain decomposition algorithms. They are based on a partitioning of a given region, on which the partial differential equation is defined, into nonoverlapping substructures. The preconditioners of these conjugate gradient methods are then given in terms of local problems, defined on individual substructures and pairs of substructures, and, in addition, a global problem of low dimension. An iterative method of this kind is introduced for the lowest order Raviart­Thomas finite elements in three dimensions and it is shown that the condition number of the relevant operator is independent of the number of substructures and grows only as the square of the logarithm of the number of unknowns associated with an individual substructure. The theoretical bounds are confirmed by a series of numerical experiments. [ABSTRACT FROM AUTHOR]

Problems with singular perturbations exhibit solutions with strong boundary layers and other types of local behavior. Such features lend themselves to adaptive solution methods. The quality of any adaptive algorithm ultimately rests on the reliability and robustness of the a posteriori error control. An estimator that has proved to be one of the most reliable is the equilibrated residual method. The main property of the estimator is that it bounds the true error from above. However, the method is not robust in the singularly perturbed limit. The current work generalizes the error estimator based on the equilibrated residuals and coincides with the standard method in the unperturbed limit. It is shown that the new method is robust in the singularly perturbed limit while maintaining reliability, yielding a guaranteed upper bound on the true error. Finally, the application of the estimator to the problem of controlling the spatial error in Rothe's method for the time discretization of a simple parabolic problem is included. [ABSTRACT FROM AUTHOR]

An iterative method is proposed to solve the Schrödinger eigenvalue problem in a wavelet framework. Orthonormal wavelets are used to represent the corresponding operator as a sparse band matrix. This representation, called the nonstandard (NS) form, is obtained by means of the Beylkin­Coifman­Rokhlin (BCR) algorithm and simplifies the numerical calculations. Problems due to the one-dimensional mathematical model and to the discretization process receive special attention. [ABSTRACT FROM AUTHOR]