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.

Hashing with linear probing dates back to the 1950s and is among the most studied algorithms for storing (key, value) pairs. In recent years it has become one of the most important hash table organizations since it uses the cache of modern computers very well. Unfortunately, previous analyses rely either on complicated and space consuming hash functions, or on the unrealistic assumption of free access to a hash function with random and independent function values. Carter and Wegman, in their seminal paper on universal hashing, raised the question of extending their analysis to linear probing. However, we show in this paper that linear probing using a 2-wise independent hash function may have expected logarithmic cost per operation. Recently, Păatraşcu and Thorup have shown that 3- and 4-wise independent hash functions may also give rise to logarithmic expected query time. On the positive side, we show that 5-wise independence is enough to ensure constant expected time per operation. This resolves the question of finding a space and time efficient hash function that provably ensures good performance for hashing with linear probing. [ABSTRACT FROM AUTHOR]

This paper is concerned with the convergence properties of iterative algorithms of conjugate gradient type applied to the computation of an extreme eigenvalue of a Hermitian operator via the optimization of the Rayleigh quotient functional. The algorithms in focus employ the line search for the extremum of the Rayleigh quotient functional in the direction that is a linear combination of the gradient and the previous search direction. An asymptotically explicit equation for the reduction in the eigenvalue error after the line search step as a function of the search direction is derived and applied to the analysis of the local convergence properties (i.e., the error reduction after an iteration) of the algorithms in question. The local (stepwise) asymptotic equivalence of various conjugate gradient algorithms and the generalized Davidson method is proved, and a new convergence estimate for conjugate gradient iterations is derived, showing the reduction in the eigenvalue error after any two consecutive iterations. The paper's analysis extensively employs remarkable properties of the operator of the so-called Jacobi orthogonal complement correction equation. [ABSTRACT FROM AUTHOR]

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]

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]

This paper is concerned with the development of well-balanced high order numerical schemes for systems of balance laws with a linear flux function, whose coefficients may be variable. First, well-balanced first order numerical schemes are obtained based on the use of exact solvers of Riemann problems that include both the flux and the source terms. Godunov's methods so obtained are extended to higher order schemes by using a technique of reconstruction of states. The main contribution of this paper is to introduce a reconstruction technique that preserves the well-balanced property of Godunov's methods. Some numerical experiments are presented to verify in practice the properties of the developed numerical schemes. [ABSTRACT FROM AUTHOR]

In this paper we consider the numerical solution of discrete boundary integral equations on polyhedral surfaces in three dimensions. When the solution contains typical edge singularities, highly stretched meshes are preferred to uniform meshes, since they reduce the number of degrees of freedom needed to obtain a fixed accuracy. The classical panel-clustering method can still be applied in the presence of such highly stretched meshes. However, we will show that the savings in computation time and storage become suboptimal because the nearfield matrix arising in the panel-clustering algorithm is no longer as sparse as it is in the case of uniform meshes. Hence, a natural question arises as to whether a new enhanced panel-clustering algorithm can be designed which performs efficiently even in the presence of highly stretched meshes. The main result of this paper is to formulate such an enhanced version of the panel-clustering algorithm. The key features of the algorithm are (i) the employment of partial analytic integration in the direction of stretching, yielding a new kernel function on a one-dimensional manifold where the influence of high aspect ratios in the stretched elements is removed, and (ii) the introduction of a generalized admissibility condition with respect to the partially integrated kernel, which ensures that certain stretched clusters which are inadmissible in the classical sense now become admissible. In the context of a model problem, we prove that our algorithm yields an accurate (up to the discretization error) matrix-vector multiplication which requires ...(NlogκN) operations, where N is the number of degrees of freedom and k is small and independent of the aspect ratio. The generalized admissibility condition can be viewed as an addition to the classical method which may be useful in general when stretched meshes are present. We also have performed a numerical experiment which shows that the sparsity of the nearfield matrix for the enhanced panel-clustering method is not negatively affected by stretched elements, and the method will perform optimally. [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]

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]

This paper presents the Cholesky factor-alternating direction implicit (CF-ADI) algorithm, which generates a low-rank approximation to the solution X of the Lyapunov equation AX + XAT = -BBT. The coefficient matrix A is assumed to be large, and the rank of the right-hand side -BBT is assumed to be much smaller than the size of A. The CF-ADI algorithm requires only matrix-vector products and matrix-vector solves by shifts of A. Hence, it enables one to take advantage of any sparsity or structure in A. This paper also discusses the approximation of the dominant invariant subspace of the solution X. We characterize a group of spanning sets for the range of X. A connection is made between the approximation of the dominant invariant subspace of X and the generation of various low-order Krylov and rational Krylov subspaces. It is shown by numerical examples that the rational Krylov subspace generated by the CF-ADI algorithm, where the shifts are obtained as the solution of a rational minimax problem, often gives the best approximation to the dominant invariant subspace of X. [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]

This paper discusses convergence behavior of the nonlinear inexact Uzawa algorithm for solving saddle-point problems presented in a recent paper of Bramble, Pasciak, and Vassilev (SIAM J. Numer. Anal., 34 (1997), pp. 1072­1092). It is shown that this algorithm converges under a condition weaker than that stated in their paper. Key words: saddle-point problems; nonlinear inexact Uzawa algorithm; convergence behavior [ABSTRACT FROM AUTHOR]

Low-rank matrix approximations, such as the truncated singular value decomposition and the rank-revealing QR decomposition, play a central role in data analysis and scientific computing. This work surveys and extends recent research which demonstrates that randomization offers a powerful tool for performing low-rank matrix approximation. These techniques exploit modern computational architectures more fully than classical methods and open the possibility of dealing with truly massive data sets. This paper presents a modular framework for constructing randomized algorithms that compute partial matrix decompositions. These methods use random sampling to identify a subspace that captures most of the action of a matrix. The input matrix is then compressed--either explicitly or implicitly--to this subspace, and the reduced matrix is manipulated deterministically to obtain the desired low-rank factorization. In many cases, this approach beats its classical competitors in terms of accuracy, robustness, and/or speed. These claims are supported by extensive numerical experiments and a detailed error analysis. The specific benefits of randomized techniques depend on the computational environment. Consider the model problem of finding the k dominant components of the singular value decomposition of an m x n matrix, (i) For a dense input matrix, randomized algorithms require O(mn log (k)) floating-point operations (flops) in contrast to O(mnk) for classical algorithms, (ii) For a sparse input matrix, the flop count matches classical Krylov subspace methods, but the randomized approach is more robust and can easily be reorganized to exploit multiprocessor architectures, (iii) For a matrix that is too large to fit in fast memory, the randomized techniques require only a constant number of passes over the data, as opposed to O(k) passes for classical algorithms. In fact, it is sometimes possible to perform matrix approximation with a single pass over the data. [ABSTRACT FROM AUTHOR]

Compressed sensing (CS) seeks to recover an unknown vector with N entries by making far fewer than N measurements; it posits that the number of CS measurements should be comparable to the information content of tile vector, not simply N. CS combines directly the important task of compression with the measurement task. Since its introduction in 2004 there have been hundreds of papers on CS, a large fraction of which develop algorithms to recover a signal from its compressed measurements. Because of the paradoxical nature of CS--exact reconstruction from seemingly undersampled measurements--it is crucial for acceptance of an algorithm that rigorous analyses verify the degree of undersampling the algorithm permits. The restricted isometry property (RIP) has become the dominant tool used for the analysis in such cases. We present here an asymmetric form of RIP that gives tighter bounds than the usual symmetric one. We give the best known bounds on the RIP constants for matrices from the Gaussian ensemble. Our derivations illustrate the way in which the combinatorial nature of CS is controlled. Our quantitative bounds on the RIP allow precise statements as to how aggressively a signal can be undersampled, the essential question for practitioners. We also document the extent to which RIP gives precise information about the true performance limits of CS, by comparison with approaches from high-dimensional geometry. [ABSTRACT FROM AUTHOR]

We study a block triangular preconditioner for finite element approximations of the linearized Navier-Stokes equations. The preconditioner is based on the augmented Lagrangian formulation of the problem and was introduced by the authors in [SIAM J. Sci. Comput., 28 (2006), pp. 2095-2113]. In this paper we prove field-of-values type estimates for the preconditioned system which lead to optimal convergence bounds for the GMRES algorithm applied to solve the system. Two variants of the preconditioner are considered: an ideal one based on exact solves for the velocity submatrix, and a more practical variant based on block triangular approximations of the velocity submatrix. [ABSTRACT FROM AUTHOR]

In this paper, we present a multigrid method and its implementation on parallel computers to solve the bidomain equation that appears in excitation propagation analysis of the human heart with the torso. The bidomain equation is discretized with the finite element method on a composite mesh composed of a fine voxel mesh around the heart and a coarse voxel mesh covering the torso. The extracellular potential problem on the torso is formulated as a variational problem with a constraint at the interface of the fine and coarse meshes. We show that this formulation naturally satisfies the conservation property of the electric currents and fits into the multilevel adaptive solution technique framework. We also present our special treatment of the Purkinje fiber network in the multigrid algorithm where it is modeled as multiway branching lines connected to the nodes in the voxel mesh of the heart. A parallel implementation of the proposed multigrid algorithm on distributed memory computers is presented and its performance is evaluated using real-life applications. [ABSTRACT FROM AUTHOR]

This paper is devoted to mathematical modeling in photoacoustic imaging of small absorbers. We propose a new method for reconstructing small absorbing regions inside a bounded domain from boundary measurements of the induced acoustic signal. We also show the focusing property of the back-propagated acoustic signal. Indeed, we provide two different methods for locating a targeted optical absorber from boundary measurements of the induced acoustic signal. The first method consists of a Multiple Signal Classification (MUSIC)-type algorithm and the second one uses a multifrequency approach. We also show results of computational experiments to demonstrate efficiency of the algorithms. [ABSTRACT FROM AUTHOR]

In this paper we develop boundary value methods for detecting Sacker-Sell spectra in discrete time dynamical systems. The algorithms are advancements of earlier methods for computing projectors of exponential dichotomies. The first method is based on the projector residual P² - P. If this residual is large, then the difference equation has no exponential dichotomy. Further criterions for detecting Sacker-Sell spectral intervals are the norm of end points and midpoints of the solution of a specific boundary value problem. Refined error estimates for the underlying approximation process are given, and the resulting algorithms are applied to an example with known continuous Sacker-Sell spectrum, as well as to the variational equation along orbits of Hénon's map. [ABSTRACT FROM AUTHOR]

The search for efficient image denoising methods is still a valid challenge at the crossing of functional analysis and statistics. In spite of the sophistication of the recently proposed methods, most algorithms have not yet attained a desirable level of applicability. All show an outstanding performance when the image model corresponds to the algorithm assumptions but fail in general and create artifacts or remove fine structures in images. The main focus of this paper is, first, to define a general mathematical and experimental methodology to compare and classify classical image denoising algorithms and, second, to propose a nonlocal means (NL-means) algorithm addressing the preservation of structure in a digital image. The mathematical analysis is based on the analysis of the "method noise," defined as the difference between a digital image and its denoised version. The NL-means algorithm is proven to be asymptotically optimal under a generic statistical image model. The denoising performance of all considered methods is compared in four ways; mathematical: asymptotic order of magnitude of the method noise under regularity assumptions; perceptual-mathematical: the algorithms artifacts and their explanation as a violation of the image model; quantitative experimental: by tables of L² distances of the denoised version to the original image. The fourth and perhaps most powerful evaluation method is, however, the visualization of the method noise on natural images. The more this method noise looks like a real white noise, the better the method. [ABSTRACT FROM AUTHOR]

Local methods for manifold learning generate a collection of local parameterizations which is then aligned to produce a global parameterization of the underlying manifold. The alignment procedure is carried out through the computation of a partial eigendecomposition of a so-called alignment matrix. In this paper, we present an analysis of the eigenstructure of the alignment matrix giving both necessary and sufficient conditions trader which the null space of the alignment matrix recovers the global parameterization. We show that the gap in the spectrum of the alignment matrix is proportional to the square of the size (the precise definition of the size is given in section 6) of the overlap of the local parameterizations, thus deriving a quantitative measure of how stably the null space can be computed numerically. We also give a perturbation analysis of the null space of the alignment matrix when the computation of the local parameterizations is subject to error. Our analysis provides insights into the behaviors and performance of local manifold learning algorithms. [ABSTRACT FROM AUTHOR]

The global macroscopic behavior of a dynamical system is encoded in the eigenfunctions of the associated Frobenius-Perron operator. For systems with low dimensional long term dynamics, efficient techniques exist for a numerical approximation of the most important eigenfunctions; cf. [M. Dellnitz and O. Junge, SIAM J. Numer. Anal., 36 (1999), pp. 491-515]. They are based on a projection of the operator onto a space of piecewise constant functions supported on a neighborhood of the attractor—Ulam's method. In this paper we develop a numerical technique which makes Ulam's approach applicable to systems with higher dimensional long term dynamics. It is based on ideas for the treatment of higher dimensional partial differential equations using sparse grids [C. Zenger, Sparse grids, in Parallel Algorithms for Partial Differential Equations (Kiel, 1990), Vieweg, Braunschweig, 1991, pp. 241-251; H.-J. Bungartz and M. Griebel, Acta Numer., 13 (2004), pp. 147-269]. Here, we use a sparse Haar tensor basis as the underlying approximation space. We develop the technique, establish statements about its complexity and convergence, and present two numerical examples. [ABSTRACT FROM AUTHOR]

This paper is concerned with the numerical minimization of energy functionals in Hilbert spaces involving convex constraints coinciding with a seminorm for a subspace. The optimization is realized by alternating minimizations of the functional on a sequence of orthogonal subspaces. On each subspace an iterative proximity-map algorithm is implemented via oblique thresholding, which is the main new tool introduced in this work. We provide convergence conditions for the algorithm in order to compute minimizers of the target energy. Analogous results are derived for a parallel variant of the algorithm. Applications are presented in domain decomposition methods for degenerate elliptic PDEs arising in total variation minimization and in accelerated sparse recovery algorithms based on l1-minimization. We include numerical examples which show efficient solutions to classical problems in signal and image processing. [ABSTRACT FROM AUTHOR]

In [Carlini, Falcone, Forcadel, and Monneau, SIAM J. Numer. Anal., 46 (2008), pp. 2920-2952], the authors have proposed a generalization of the classical fast marching method of Sethian for the eikonal equation in the case where the normal velocity depends on space and time and can change sign. The goal of this paper is to propose a modified version of the generalized fast marching method proposed in [Carlini, Falcone, Forcadel, and Monneau, SIAM J. Numer. Anal., 46 (2008), pp. 2920-2952] for which we state a general comparison principle. We also prove the convergence of the new algorithm. [ABSTRACT FROM AUTHOR]

In this paper, a new space-time discretization is proposed which is based on a modified mass matrix. The mass associated with a surface layer of elements is redistributed such that the inertia at the boundary is removed. This approach is motivated by the observation that standard space-time discretization schemes applied to dynamic contact problems yield spurious oscillations. A widely used approach for the numerical simulation of these problems is based on Lagrange multipliers which represent the contact stresses. But the algebraic contact conditions in combination with the inertia volume terms often yield nonphysical results for the contact stresses, and the stability of the algorithm can be lost. Our modified matrix is calculated via nonstandard quadrature formulas that require no extra computational effort. In addition, the conservation properties of the underlying algorithm are carried over to the modified method, and the standard optimal a priori estimates are still satisfied. Numerical examples confirm the optimality of the approach and its stabilization effect applied to contact problems. [ABSTRACT FROM AUTHOR]

In [Carlini, Falcone, Forcadel, and Monneau, SIAM J. Numer. Anal., 46 (2008), pp. 2920-2952], the authors have proposed a generalization of the classical fast marching method of Sethian for the eikonal equation in the case where the normal velocity depends on space and time and can change sign. The goal of this paper is to propose a modified version of the generalized fast marching method proposed in [Carlini, Falcone, Forcadel, and Monneau, SIAM J. Numer. Anal., 46 (2008), pp. 2920-2952] for which we state a general comparison principle. We also prove the convergence of the new algorithm. [ABSTRACT FROM AUTHOR]

We describe a class of logically rectangular quadrilateral and hexahedral grids for solving PDEs in circular and spherical domains, including grid mappings for the circle, the surface of the sphere, and the three-dimensional ball. The grids are logically rectangular and the computational domain is a single Cartesian grid. Compared to alternative approaches based on a multiblock data structure or unstructured triangulations, this approach simplifies the implementation of numerical methods and the use of adaptive refinement. A more general domain with a smooth boundary can be gridded by composing one of the mappings from this paper with another smooth mapping from the circle or sphere to the desired domain. Although these grids are highly nonorthogonal, we show that the high-resolution wave-propagation algorithm implemented in CLAWPACK can be used effectively to approximate hyperbolic problems on these grids. Since the ratio between the largest and smallest grids is below 2 for most of our grid mappings, explicit finite volume methods such as the wave-propagation algorithm do not suffer from the center or pole singularities that arise with polar or latitude-longitude grids. Numerical test calculations illustrate the potential use of these grids for a variety of applications including Euler equations, shallow water equations, and acoustics in a heterogeneous medium. Pattern formation from a reaction-diffusion equation on the sphere is also considered. All examples are implemented in the CLAWPACK software package and full source code is available on the web, along with MATLAB routines for the various mappings. [ABSTRACT FROM AUTHOR]

The problem of exact controllability of elastic strings has been extensively studied during the last years. We consider the problem of computing numerically the boundary control for a finite-dimensional system obtained by discretizing in space the 1 - d wave equation. More precisely, we analyze whether the controls of numerical approximation schemes converge to the control of the continuous wave equation as the mesh size tends to zero. It is by now well known that, due to high-frequency spurious oscillations, numerical instabilities occur and may lead to the failure of convergence of some apparently natural numerical algorithms. In other words, the classical convergence property of numerical schemes does not guarantee a stable and convergent approximation of controls. Several remedies have been proposed in the literature to compensate for this fact: Tychonoff regularization, Fourier filtering, and mixed finite elements. In this paper we prove that the two-grid method proposed by Glowinski in [J. Comput. Phys., 103 (1992), pp. 189-221] to numerically approximate the control of the wave equation converges in 1 - d. We prove this result in the context of the finite-element space semidiscretization. Our method of proof relies essentially on the particular properties of the Fourier representation of the initial data of the coarse mesh when projected into the fine one. The explicit representation formula of the solutions shows that the high-frequency components are modulated by some weights that diminish the effect of these spurious components. This fact, combined with discrete multipliers techniques, allows us to prove uniform observability inequalities. Classical arguments then allow proving the uniform boundedness of the controls and passing to the limit as the mesh size tends to zero. In this way we prove the convergence of the controls of the finite-element semidiscrete approximation of the 1 - d wave equation with a boundary control on one extreme. It is important to underline that the controls obtained by this two-grid algorithm are not exact in the sense that they only guarantee the controllability of the projection of the solutions into the coarse mesh. [ABSTRACT FROM AUTHOR]

We consider the incompressible Navier-Stokes equations where on a part of the boundary flow rate and mean pressure boundary conditions are prescribed. There are basically two strategies for solving these defective boundary problems: the variational approach (see J. Heywood, R. Rannacher, and S. Turek, Internat. J. Numer. Methods Fluids, 22 (1996), pp. 325-352) and the augmented formulation (see L. Formaggia, J. F. Gerbeau, F. Nobile, and A. Quarteroni, SIAM J. Numer. Anal., 40 (2002), pp. 376-401, and A. Veneziani and C. Vergara, Internat. J. Numer. Methods Fluids, 47 (2005), pp. 803-816). However, both of these approaches present some drawbacks. For the flow rate problem, the former resorts to nonstandard functional spaces, which are quite difficult to discretize. On the other hand, for the mean pressure problem, it yields exact solutions only in very special cases. The latter is applicable only to the flow rate problem, since for the mean pressure problem it provides unfeasible boundary conditions. In this paper, we propose a new strategy based on a reformulation of the problems at hand in terms of the minimization of an appropriate functional. This approach allows us to treat the two kinds of problems (flow rate and mean pressure) successfully within the same framework, which can be useful in view of a mixed problem where the two conditions are simultaneously prescribed on different artificial boundaries. Moreover, it is more versatile, being prone to be extended to other kinds of defective conditions. We analyze the problems obtained with this approach and propose some algorithms for their numerical solution. Several numerical results are presented supporting the effectiveness of our approach. [ABSTRACT FROM AUTHOR]

This paper presents a new algorithm for conductivity imaging. Our idea is to extract more information about the conductivity distribution from data that have been enriched by coupling impedance electrical measurements to localized elastic perturbations. Using asymptotics of the fields in the presence of small volume inclusions, we relate the pointwise values of the energy density to the measured data through a nonlinear PDE. Our algorithm is based on this PDE and takes full advantage of the enriched data. We give numerical examples that illustrate the performance and the accuracy of our approach. [ABSTRACT FROM AUTHOR]

This paper addresses the question of how to efficiently adapt the conjugate gradient (CG) method to the computation of several leftmost or rightmost eigenvalues and corresponding eigenvectors of Hermitian problems. A generic block CG algorithm instantiated by some available block CG algorithms is considered whereby the new approximate eigenpairs are computed by applying the Rayleigh-Ritz procedure in the trial subspace spanning current approximate eigenvectors and the search direction vectors, each of the latter being a linear combination of the respective gradient of the Rayleigh quotient and all search directions from the previous iteration. An approach related to the so-called Jacobi orthogonal complement correction equation is exploited in the local convergence analysis of this CG algorithm. Based on theoretical considerations, a new block conjugation scheme (a way to compute search directions) is suggested that enjoys a certain kind of optimality and has proved to be competitive in practical eigenvalue computation. [ABSTRACT FROM AUTHOR]

In this paper, a FETI-DP formulation for three dimensional elasticity on nonmatching grids over geometrically nonconforming subdomain partitions is considered. To resolve the nonconformity of the finite elements, a mortar matching condition is imposed on the subdomain interfaces (faces). A FETI-DP algorithm is then built by enforcing the mortar matching condition in dual and primal ways. In order to make the FETI-DP algorithm scalable, a set of primal constraints, which include average and momentum constraints over interfaces, are selected from the mortar matching condition. A condition number bound, C(1 + log(H/h))², is then proved for the FETI-DP formulation for the elasticity problems with discontinuous material parameters. Only some faces need to be chosen as primal faces on which the average and momentum constraints are imposed. Numerical results are included. [ABSTRACT FROM AUTHOR]

In this paper, we study the Legendre-Galerkin spectral approximation for a constrained optimal control problem. We first derive a priori error estimates for the spectral approximation of optimal control problems. Then a posteriori error estimates are obtained for both the state and the control approximation. A preconditioning projection algorithm is proposed with some numerical tests. [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]

Discontinuous Galerkin (DG) and mixed finite element (MFE) methods are two popular methods that possess local mass conservation. In this paper we investigate DG-DG and DG-MFE domain decomposition couplings using mortar finite elements to impose weak continuity of fluxes and pressures on the interface. The subdomain grids need not match, and the mortar grid may be much coarser, giving a two-scale method. Convergence results in terms of the fine subdomain scale h and the coarse mortar scale H are established for both types of couplings. In addition, a nonoverlapping parallel domain decomposition algorithm is developed, which reduces the coupled system to an interface mortar problem. The properties of the interface operator are analyzed. [ABSTRACT FROM AUTHOR]

This paper proposes a macroscopic fluid dynamic model dealing with the flows of information on a telecommunication network with sources and destinations. The model consists of a conservation law for the packet density and a semilinear equation for traffic distribution functions, i.e., functions describing packet paths. We describe methods to solve Riemann problems at junctions assigning different traffic distribution functions and two "routing algorithms." Moreover, we prove the existence of solutions to Cauchy problems for small perturbations of network equilibria. [ABSTRACT FROM AUTHOR]

In this paper we provide a framework for constructing general complex geometrical optics solutions for several systems of two variables that can be reduced to a system with the Laplacian as the leading order term. We apply these special solutions to the problem of reconstructing inclusions inside a domain filled with known conductivity from local boundary measurements. Computational results demonstrate the versatility of these solutions to determine electrical inclusions. [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]

Differential repetitive processes are a distinct class of continuous-discrete two-dimensional linear systems of both systems theoretic and applications interest. These processes complete a series of sweeps termed passes through a set of dynamics defined over a finite duration known as the pass length, and once the end is reached the process is reset to its starting position before the next pass begins. Moreover the output or pass profile produced on each pass explicitly contributes to the dynamics of the next one. Applications areas include iterative learning control and iterative solution algorithms, for classes of dynamic nonlinear optimal control problems based on the maximum principle, and the modeling of numerous industrial processes such as metal rolling, long-wall cutting, etc. In this paper we develop substantial new results on optimal control of these processes in the presence of constraints where the cost function and constraints are motivated by practical application of iterative learning control to robotic manipulators and other electromechanical systems. The analysis is based on generalizing the well-known maximum and ϵ-maximum principles to them. [ABSTRACT FROM AUTHOR]

It is well known that the nonlinear filtering problem has important applications in both military and commercial industries. The central problem of nonlinear filtering is to solve the Duncan—Mortensen—Zakai (DMZ) equation in real time and in a memoryless manner. The purpose of this paper is to show that, under very mild conditions (which essentially say that the growth of the observation ∣h∣ is greater than the growth of the drift ∣f∣), the DMZ equation admits a unique nonnegative weak solution u which can be approximated by a solution uR of the DMZ equation on the ball BR with uR ∣∂BR = 0. The error of this approximation is bounded by a function of R which tends to zero as R goes to infinity. The solution uR can in turn be approximated efficiently by an algorithm depending only on solving the observation-independent Kolmogorov equation on BR. In theory, our algorithm can solve basically all engineering problems in real time. Specifically, we show that the solution obtained from our algorithms converges to the solution of the DMZ equation in the L¹ sense. Equally important, we have a precise error estimate of this convergence, which is important in numerical computation. [ABSTRACT FROM AUTHOR]

In this paper, we give explicit constructions of point sets in the s-dimensional unit cube yielding quasi-Monte Carlo algorithms which achieve the optimal rate of convergence of the worst-case error for numerically integrating high-dimensional periodic functions. In the classical measure Pα of the worst-case error introduced by Korobov, the convergence, for every even integer α ⁥ 1, is of …(N-min(α,d) (log N)sα-2), where d is a parameter of the construction which can be chosen arbitrarily large and N is the number of quadrature points. This convergence rate is known to be the best possible up to some log N factors. We prove the result for the deterministic and also a randomized setting. The construction is based on a suitable extension of digital (t, m, s)-nets over the finite field …b. [ABSTRACT FROM AUTHOR]

This paper is devoted to the incorporation of topological derivativelike expansions into level set methods for perimeter-regularized geometric inverse problems. The expansions are done up to the second order with respect to the Lebesgue measure of the symmetric difference. They provide simpler shape functionals, still including the perimeter, and therefore allow the construction of steepest descent- and Newton-type algorithms to force topology changes during the level set evolution. Numerous numerical examples are provided that show the strong and also the weak points of the newly developed algorithms. [ABSTRACT FROM AUTHOR]

In this paper, the authors present two formulations for the Stokes problem which make use of the existing H(div) elements of the Raviart-Thomas type originally developed for the second-order elliptic problems. In addition, two new H(div) elements are constructed and analyzed particularly for the new formulations. Optimal-order error estimates are established for the corresponding finite element solutions in various Sobolev norms. The finite element solutions feature a full satisfaction of the continuity equation when existing Raviart-Thomas-type elements are employed in the numerical scheme. [ABSTRACT FROM AUTHOR]

We study in this paper a new class of waveform relaxation algorithms for large systems of ordinary differential equations arising from discretizations of partial differential equations of advection reaction diffusion type. We show that the transmission conditions between the subsystems have a tremendous influence on the convergence speed of the waveform relaxation algorithms, and we identify transmission conditions with optimal performance. Since these optimal transmission conditions are expensive to use, we introduce a class of local transmission conditions of Robin type, which approximate the optimal ones and can be used at the same cost as the classical transmission conditions. We determine the transmission conditions in this class with the best performance of the associated waveform relaxation algorithm. We show that the new algorithm is well posed and converges much faster than the classical one. We illustrate our analysis with numerical experiments. [ABSTRACT FROM AUTHOR]

In this paper, some two-scale Boolean Galerkin discretizations are proposed and analyzed for a class of Fredholm integral equations of the second kind in multidimensions. It is shown by both theory and numerics that this type of multiscale discretization algorithm not only significantly reduces the number of degrees of freedom but also produces very accurate approximations. [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]

In this paper, we study the dynamics of rotating Bose-Einstein condensates (BEC) based on the Gross-Pitaevskii equation (GPE) with an angular momentum rotation term and present an efficient and accurate algorithm for numerical simulations. We examine the conservation of the angular momentum expectation and the condensate width and analyze the dynamics of a stationary state with a shift in its center. By formulating the equation in either the two-dimensional polar coordinate system or the three-dimensional cylindrical coordinate system, the angular momentum rotation term becomes a term with constant coefficients. This allows us to develop an efficient time-splitting method which is time reversible, unconditionally stable, efficient, and accurate for the problem. Moreover, it conserves the position density. We also apply the numerical method to study issues such as the stability of central vortex states and the quantized vortex lattice dynamics in rotating BEC. [ABSTRACT FROM AUTHOR]

Centroidal Voronoi tessellations (CVTs) are Voronoi tessellations of a bounded geometric domain such that the generating points of the tessellations are also the centroids (mass centers) of the corresponding Voronoi regions with respect to a given density function. Centroidal Voronoi tessellations may also be defined in more abstract and more general settings. Due to the natural optimization properties enjoyed by CVTs, they have many applications in diverse fields. The Lloyd algorithm is one of the most popular iterative schemes for computing the CVTs but its theoretical analysis is far from complete. In this paper, some new analytical results on the local and global convergence of the Lloyd algorithm are presented. These results are derived through careful utilization of the optimization properties shared by CVTs. Numerical experiments are also provided to substantiate the theoretical analysis. [ABSTRACT FROM AUTHOR]

We consider two-dimensional elliptic problems with discontinuous coefficients discretized by the finite element method on geometrically conforming nonmatching triangulations across the interface using the mortar technique. The resulting discrete problem is solved by a dual-primal FETI method. In this paper we introduce and analyze a preconditioner with a special scaling of coefficients and step parameters and establish convergence bounds. We show that the preconditioner is almost optimal with constants independent of the jumps of coefficients and step parameters. Extensive computational evidence is presented that illustrates an almost optimal convergence for a variety of situations (distribution of subregions, grid assignment, grid ratios, number of subregions) for both continuous and discontinuous problems. [ABSTRACT FROM AUTHOR]

Multigrid algorithms for Co interior penalty methods for fourth order elliptic boundary value problems on polygonal domains are studied in this paper. It is shown that V -cycle, F-cycle and W-cycle algorithms are contractions if the number of smoothing steps is sufficiently large. The contraction numbers of these algorithms are bounded by Cm-α, where m is the number of presmoothing (and postsmoothing) steps, α is the index of elliptic regularity, and the positive constant C is mesh-independent. These estimates are established for a smoothing scheme that uses a Poisson solve as a preconditioner, which can be easily implemented because the Co finite element spaces are standard spaces for second order problems. Furthermore the variable V -cycle algorithm is also shown to be an optimal preconditioner. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of testing whether a large matrix X has a prescribed structure by looking at the magnitude of a displacement matrix D(X) associated with the structure. We provide parameters on the basis of which one can judge whether the problem is well-conditioned or ill-conditioned. It turns out that even for very general structures it is the minimal eigenvalues of positive definite and banded Toeplitz matrices that are the most important of these parameters. [ABSTRACT FROM AUTHOR]