Search

The article highlights two papers published within the issue titled "Divide-and-Conquer: A Proportional, Minimal-Envy Cake-Cutting Algorithm," by Steven Brams, Michael Jones and Christian Klamler, and "Impossibility of Fast Stable Approximation of Analytic Functions from Equispaced Samples," by Rodrigo Platte, Lloyd Trefethen and Arno Kuijlaars. The first paper discussed the mathematical problem of proportional division. The second one talked about potential theory, matrix iterations in the form of Krylov space methods and quadrature formulae.

The paper concerns numerical algorithms for solving the Beltrami equation fz¯(z) = μ(z)fz(z) for a compactly supported μ. First, we study an efficient algorithm that has been proposed in [P. Daripa, J. Comput. Phys., 106 (1993), pp. 355-365] and [P. Daripa and D. Mashat, Numer. Algorithms, 18 (1998), pp. 133-157] and present its rigorous justification. We then propose a different scheme for solving the Beltrami equation which has a comparable speed and accuracy, but has the virtue of easier implementation by avoiding the use of the Hilbert transform. The present paper can also be viewed as a prologue to one important application of the Beltrami equation: it provides a detailed description of the algorithm that has been used in [D. Gaidashev, Nonlinearity, 20 (1998), pp. 713-741] and [D. Gaidashev and M. Yampolsky, Experiment. Math., 16 (2007), pp. 215-226] to address an important issue in complex dynamics-conjectural universality for Siegel disks. [ABSTRACT FROM AUTHOR]

Local mesh-refining algorithms known from adaptive finite element methods are adopted for locally conservative and monotone finite volume discretizations of boundary value problems for steady-state convection-diffusion-reaction equations. The paper establishes residual-type explicit error estimators and averaging techniques for a posteriori finite volume error control with and without upwind in global H1- and L2-norms. Reliability and efficiency are verified theoretically and confirmed empirically with experimental support for the superiority of the suggested adaptive mesh-refining algorithms over uniform mesh refining. A discussion of adaptive computations in the simulation of contaminant concentration in a nonhomogeneous water reservoir concludes the paper. [ABSTRACT FROM AUTHOR]

A new fully variational approach is studied for elliptic grid generation (EGG). It is based on a general algorithm developed in a companion paper [A. L. Codd, T. A. Manteuffel, and S. F. McCormick, SIAM I Numer. Anal., 41 (2003), pp. 2197-2209] that involves using Newton's method to linearize an appropriate equivalent first-order system, first-order system least squares (FOSLS) to formulate and discretize the Newton step, and algebraic multigrid (AMG) to solve the resulting matrix equation. The approach is coupled with nested iteration to provide an accurate initial guess for finer levels using coarse-level computation. The present paper verifies the assumptions of the companion work and confirms the overall efficiency of the scheme with numerical experiments. [ABSTRACT FROM AUTHOR]

In the first part of the paper, we introduce an overlapping mortar finite element method for solving two-dimensional elliptic problems discretized on overlapping nonmatching grids. We prove an optimal error bound and estimate the condition numbers of certain overlapping Schwarz preconditioned systems for the two-subdomain case. We show that the error bound is independent of the size of the overlap and the ratio of the mesh parameters. In the second part, we introduce three additive Schwarz preconditioned conjugate gradient algorithms based on the trivial and harmonic extensions. We provide estimates for the spectral bounds on the condition numbers of the preconditioned operators. We show that although the error bound is independent of the size of the overlap, the condition number does depend on it. Numerical examples are presented to support our theory. [ABSTRACT FROM AUTHOR]

The QR algorithm is still one of the most important methods for computing eigenvalues and eigenvectors of matrices. Most discussions of the QR algorithm begin with a very basic version and move by steps toward the versions of the algorithm that are actually used. This paper outlines a pedagogical path that leads directly to the implicit multishift QR algorithms that are used in practice, bypassing the basic QR algorithm completely. [ABSTRACT FROM AUTHOR]

This paper deals with the inverse problem of inferring the position of an electrically grounded conductor D from a single measurement of electric field (Cauchy data) on the boundary of a smooth domain ω⊂ R[SUPn], n = 2, 3, that contains D. We present new simple and real time algorithms for locating D with a rigorous mathematical verification. These location search techniques use a special property of the surface charge density of the electrically grounded conductor. The computations in these location search methods are very simple, so that the location of a moving grounded conductor can be detected in a instant even in three dimensions. [ABSTRACT FROM AUTHOR]

In this paper, we study the additive Schwarz method for the h-p version of the finite element method in three dimensions. The main idea is to treat separately the h-version (linear) components and the p-version (high-order) components by a vertex-based method. It can also be viewed as a three-level method with the level being the linear finite element approximation on the coarse mesh, the linear finite element approximation on the fine mesh, and the high-order finite element approximation on the fine mesh, respectively. The resulting algorithm can be implemented in parallel on the subdomain level for the h-version components and on the element level for the p-version components. The condition number is of order [This symbol cannot be presented in ASCII format](1 + ln Hipi/hi)⇔2, where Hi stands for the diameter of the subdomain Ωi, hi is the diameter of the elements in Ωi, and pi is the maximum of the polynomial degrees used in Ωi. [ABSTRACT FROM AUTHOR]

We study the uniform (Chebyshev) approximation of continuous and piecewise rsmooth (r ≥ 2) functions f : [0, T] → ℝ with a finite number of singular points. The approximation algorithms use only n function values at adaptively or nonadaptively chosen points. We construct a nonadaptive algorithm Anon r,n that, for the functions with at most one singular point, enjoys the best possible convergence rate n-r. This is in sharp contrast to results concerning discontinuous functions. For r ≥ 3, this optimal rate of convergence holds only in the asymptotic sense, i.e., it occurs only for sufficiently large n that depends on f in a way that is practically impossible to verify. However, it is enough to modify Anon r,n by using (r +1)⌊(r - 1)/2⌋ extra function evaluations to obtain an adaptive algorithm Aada r,n with error satisfying ∥ƒ - Aada r,n ƒ∥C ≤ CrTr∥ƒ(r)∥∞L n-r for all n ≥ n0 and n0 independent of f. This result cannot be achieved for functions with more than just one singular point. However, the convergence rate n-r can be recovered asymptotically by a nonadaptive algorithm A non r,n that is a slightly modified Anon r,n . Specifically, lim supn→∞ ∥ƒ -A non r,n ƒ∥C ∙ nr ≤ CrTr∥ƒ(r)∥∞L for all r-smooth functions f with finitely many singular points. [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]

In this paper we present a hyperbolic partial differential equation (PDE) in one space and one time dimension. This equation arose in a study of numerical schemes for simulating evolving river topographies. The solution of this PDE, whose initial data are specified along a characteristic, is very similar to that of the canonical diffusion equation. This interesting example provides insight into the solution of hyperbolic PDEs when data is specified in this pathological way as well as illustrating some connections between the parabolic and hyperbolic classes of evolution equations. [ABSTRACT FROM AUTHOR]

We study numerical methods for a coupled Navier-Stokes/Darcy model which describes a fluid flow filtrating through porous media. A decoupled and linearized two-grid algorithm is proposed. Numerical analysis and experiments are presented to show the efficiency and effectiveness of the decoupled and linearized algorithm. [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]

In the theory for domain decomposition algorithms of the iterative substructuring family, each subdomain is typically assumed to be the union of a few coarse triangles or tetrahedra. This is an unrealistic assumption, in particular if the subdomains result from the use of a mesh partitioner, in which case they might not even have uniformly Lipschitz continuous boundaries. The purpose of this study is to derive bounds for the condition number of these preconditioned conjugate gradient methods which depend only on a parameter in an isoperimetric inequality, two geometric parameters characterizing John and uniform domains, and the maximum number of edges of any subdomain. A related purpose is to explore to what extent well-known technical tools previously developed for quite regular subdomains can be extended to much more irregular subdomains. Some of these results are valid for any John domain, while an extension theorem, which is needed in this study, requires that the subdomains have complements which are uniform. The results, so far, are complete only for problems in two dimensions. Details are worked out for a FETI-DP algorithm and numerical results support the findings. Some of the numerical experiments illustrate that care must be taken when selecting the scaling of the preconditioners in the case of irregular subdomains. [ABSTRACT FROM AUTHOR]

We propose efficient preconditioning algorithms for an eigenvalue problem arising in quantum physics, namely, the computation of a few interior eigenvalues and their associated eigenvectors for large-scale sparse real and symmetric indefinite matrices of the Anderson model of localization. We compare the Lanczos algorithm in the 1987 implementation by Cullum and Willoughby with the shift-and-invert techniques in the implicitly restarted Lanczos method and in the Jacobi-Davidson method. Our preconditioning approaches for the shift-and-invert symmetric indefinite linear system are based on maximum weighted matchings and algebraic multilevel incomplete LDLT factorizations. These techniques can be seen as a complement to the alternative idea of using more complete pivoting techniques for the highly ill-conditioned symmetric indefinite Anderson matrices. We demonstrate the effectiveness and the numerical accuracy of these algorithms. Our numerical examples reveal that recent algebraic multilevel preconditioning solvers can accelerate the computation of a large-scale eigenvalue problem corresponding to the Anderson model of localization by several orders of magnitude. [ABSTRACT FROM AUTHOR]

The FETI method with a natural coarse grid is combined with recently proposed optimal algorithms for the solution of bound and/or equality constrained quadratic programming problems in order to develop a scalable solver for elliptic boundary variational inequalities such as those describing equilibrium of a system of bodies in mutual contact. A discretized model problem is first reduced by the duality theory of convex optimization to the quadratic programming problem with bound and equality constraints. The latter is then modified by means of orthogonal projectors to the natural coarse grid introduced by Farhat, Mandel, and Roux [Comput. Methods Appl. Mech. Engrg., 115 (1994), pp. 365-385]. Finally, the classical results on linear scalability for linear problems are extended to boundary variational inequalities. The results are validated by numerical experiments. The experiments also confirm that the algorithm enjoys the same parallel scalability as its linear counterpart. [ABSTRACT FROM AUTHOR]

Barycentric interpolation is a variant of Lagrange polynomial interpolation that is fast and stable. It deserves to be known as the standard method of polynomial interpolation. [ABSTRACT FROM AUTHOR]

We consider a nonuniformly elliptic double obstacle problem arising from "convexifying" and regularizing a minimization of a functional with total variation in the set of characteristic functions. We derive a posteriori estimators for the discretization error with linear finite elements, which are uniform in the regularization, incorporate computable and local information on the conditioning, vanish in the intersection of discrete and exact contact sets, and are not affected by possible nonuniqueness. Moreover, we integrate these estimators in an adaptive algorithm and illustrate their properties by various numerical experiments. [ABSTRACT FROM AUTHOR]

We describe an algorithm for the numerical computation of the rank-one convex envelope of a function f : Mm×n → R. We prove its convergence and an error estimate in L∞. [ABSTRACT FROM AUTHOR]

A new set of tools for verifying smoothness of surfaces generated by stationary subdivision algorithms is presented. The main challenge here is the verification of injectivity of the characteristic map. The tools are sufficiently versatile and easy to wield to allow, as an application, a full analysis of algorithms generalizing biquadratic and bicubic B-spline subdivision. In the case of generalized biquadratic subdivision the analysis yields a hitherto unknown sharp bound strictly less than 1 on the second largest eigenvalue of any smoothly converging subdivision. [ABSTRACT FROM AUTHOR]