Search

The Schwarz alternating method can be used to solve linear elliptic boundary value problems on domains which consist of two or more overlapping subdomains. The solution is approx- imated by an infinite sequence of functions which result from solving a sequence of elliptic boundary value problems in each of the subdomains. This paper considers four Schwarz alternating methods for the N-dimensional, steady, viscous, incompressible Navier­Stokes equations, N ≤ 4. It is shown that the Schwarz sequences converge to the true solution provided that the Reynolds number is sufficiently small. [ABSTRACT FROM AUTHOR]

The design of new quantum algorithms has proven to be an extremely difficult task. This paper considers a different approach to this task by studying the problem of quantum state generation. We motivate this problem by showing that the entire class of statistical zero knowledge, which contains natural candidates for efficient quantum algorithms such as graph isomorphism and lattice problems, can be reduced to the problem of quantum state generation. To study quantum state generation, we define a paradigm which we call adiabatic state generation (ASG) and which is based on adiabatic quantum computation. The ASG paradigm is not meant to replace the standard quantum circuit model or to improve on it in terms of computational complexity. Rather, our goal is to provide a natural theoretical framework, in which quantum state generation algorithms could be designed. The new paradigm seems interesting due to its intriguing links to a variety of different areas: the analysis of spectral gaps and ground-states of Hamiltonians in physics, rapidly mixing Markov chains, adiabatic computation, and approximate counting. To initiate the study of ASG, we prove several general lemmas that can serve as tools when using this paradigm. We demonstrate the application of the paradigm by using it to turn a variety of (classical) approximate counting algorithms into efficient quantum state generators of nontrivial quantum states, including, for example, the uniform superposition over all perfect matchings in a bipartite graph. [ABSTRACT FROM AUTHOR]

Let S be a set of n points in ℝ². Given an integer 1 ≤ k ≤ n, we wish to find a maximally separated subset I ⊆ S of size k; this is a subset for which the minimum among the (2k) pairwise distances between its points is as large as possible. The decision problem associated with this problem is to determine whether there exists I ⊆ S, ∣I∣ = k, so that all (2k) pairwise distances in I are at least 2. This problem can also be formulated in terms of disk-intersection graphs: Let D be the set of unit disks centered at the points of S. The disk-intersection graph G of D has as edges all pairs of disks with nonempty intersection. Any set I with the above properties is then the set of centers of disks that form an independent set in the graph G. This problem is known to be NP-complete if k is part of the input. In this paper we first present a linear-time e-approximation algorithm for any constant k. Next we give exact algorithms for the cases k = 3 and k = 4 that run in time O(n4/3polylog(n)). We also present a simpler nO(√k)-time exact algorithm (as compared with the recent algorithm in [J. Alber and J. Fiala, J. Algorithms, 52 (2004), pp. 134-151]) for arbitrary values of k. [ABSTRACT FROM AUTHOR]

Almost all of the most successful quantum algorithms discovered to date exploit the ability of the Fourier transform to recover subgroup structures of functions, especially periodicity. The fact that Fourier transforms can also be used to capture shift structure has received far less attention in the context of quantum computation. In this paper, we present three examples of ‘unknown shift’ problems that can be solved efficiently on a quantum computer using the quantum Fourier transform. For one of these problems, the shifted Legendre symbol problem, we give evidence that the problem is hard to solve classically, by showing a reduction from breaking algebraically homomorphic cryptosystems. We also define the hidden coset problem, which generalizes the hidden shift problem and the hidden subgroup problem. This framework provides a unified way of viewing the ability of the Fourier transform to capture subgroup and shift structure. [ABSTRACT FROM AUTHOR]

A successive continuation method for locating connecting orbits in parametrized systems of autonomous ODEs was considered in [Numer. Algorithms, 14 (1997), pp. 103­124]. In this paper we present an improved algorithm for locating and continuing connecting orbits, which includes a new algorithm for the continuation of invariant subspaces. The latter algorithm is of independent interest and can be used in contexts different than the present one. [ABSTRACT FROM AUTHOR]

Fast Marching Methods are numerical schemes for computing solutions to the nonlinear Eikonal equation and related static. Hamilton­Jacobi equations. Based on entropy-satisfying upwind schemes and fast sorting techniques, they yield consistent, accurate, and highly efficient algorithms. They are optimal in the sense that the computational complexity of the algorithms is O(N log N), where N is the total number of points in the domain. The schemes are of use in a variety of applications, including problems in shape offsetting, computing distance from compiles curves and surfaces, shape-from-shading, photolithographic development, computing first arrivals in seismic travel times, construction of shortest geodesies on surfaces, optimal path planning around obstacles, and visibility and reflection calculations. In this paper, were review the development of these techniques, including the theoretical and numerical underpinnings; provide details of the computational schemes, including higher order versions; and demonstrate the techniques in a collection of different areas. [ABSTRACT FROM AUTHOR]

Computational convex analysis algorithms have been rediscovered several times in the past by researchers from different fields. To further communications between practitioners, we review the field of computational convex analysis, which focuses on the numerical computation of fundamental transforms arising from convex analysis. Current models use symbolic, numeric, and hybrid symbolic-numeric algorithms. Our objective is to disseminate widely the most efficient numerical algorithms useful for applications in image processing (computing the distance transform, the generalized distance transform, and mathematical morphology operators), partial differential equations (solving Hamilton--Jacobi equations and using differential equations numerical schemes to compute the convex envelope), max-plus algebra (computing the equivalent of the fast Fourier transform), multifractal analysis, etc. The fields of applications include, among others, computer vision, robot navigation, thermodynamics, electrical networks, medical imaging, and network communication [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 present a method for creating large two-dimensional graded Delaunay meshes on parallel machines. The method decouples the mesh generation procedure for each subdomain and thus eliminates the communication between processors, while the final mesh is of the same guaranteed quality as in the sequential case. This work extends our previous result on the uniform Delaunay decoupling method [L. Linardakis and N. Chrisochoides, SIAM J. Sci. Comput., 27 (2006), pp. 1394- 1423], by allowing the element size to be governed by a sizing function, or a background mesh. The graded Delaunay decoupling method can produce in parallel very large graded meshes efficiently, demonstrating high speedup and scalability. Ten billion elements can be created in five minutes with small overrefinement (about 2%). The decoupling parallelization approach is effective, using off-the-shelf, well-tested, and fine-tuned sequential mesh generation libraries without modification. [ABSTRACT FROM AUTHOR]

The problem of variational data assimilation for a nonlinear evolution model is formulated as an optimal control problem to find the initial condition function (analysis). The equation for the analysis error is derived through the errors of the input data (background and observation errors). This equation is used to show that in a nonlinear case the analysis error covariance operator can be approximated by the inverse Hessian of an auxiliary data assimilation problem which involves the tangent linear model constraints. The inverse Hessian is constructed by the quasi-Newton BFGS algorithm when solving the auxiliary data assimilation problem. A fully nonlinear ensemble procedure is developed to verify the accuracy of the proposed algorithm. Numerical examples are presented. [ABSTRACT FROM AUTHOR]

We present an algorithm to enumerate the pointed pseudotriangulations of a given point set, based on the greedy flip algorithm of Pocchiola and Vegter [Discrete Comput. Geom. 16 (1996), pp. 419-453]. Our two independent implementations agree and allow us to experimentally verify or disprove conjectures on the numbers of pointed pseudotriangulations and triangulations of a given point set. (For example, we establish that the number of triangulations is bounded by the number of pointed pseudotriangulations for all sets of up to 10 points.) [ABSTRACT FROM AUTHOR]

In many optimization problems, one seeks to allocate a limited set of resources to a set of individuals with demands. Thus, such allocations can naturally be viewed as vectors, with one coordinate representing each individual. Motivated by work in network routing and bandwidth assignment, we consider the problem of producing solutions that simultaneously approximate all feasible allocations in a coordinate-wise sense. This is a very strong type of ‘global’ approximation guarantee, and we explore its consequences in a wide range of discrete optimization problems, including facility location, scheduling, and bandwidth assignment in networks. A fundamental issue—one not encountered in the traditional design of approximation algorithms—is that good approximations in this global sense need not exist for every problem instance; there is no a priori reason why there should be an allocation that simultaneously approximates all others. As a result, the existential questions concerning such good allocations lead to a new perspective on a number of fundamental problems in resource allocation, and on the structure of their feasible solutions. [ABSTRACT FROM AUTHOR]

Jackson and Wormald conjecture that if G is a 3-connected n-vertex graph with maximum degree d ≥ 4, then G has a cycle of length Ω(nlogd-1 ²). We show that this conjecture holds when d - 1 is replaced by max{64, 4d + 1}. Our proof implies a cubic algorithm for finding such a cycle. [ABSTRACT FROM AUTHOR]

A propagating interface can develop corners and discontinuities as it advances. Level set algorithms have been extensively applied for the problems in which the solution has advancing fronts. One of the most popular level set algorithms is the so-called fast marching method (FMM), which requires total O(N log2 N) operations, where N is the number of grid points. The article is concerned with the development of an O(N) level set algorithm called the group marching method (GMM). The new method is based on the narrow band approach as in the FMM. However, it is incorporating a correction-by-iteration strategy to advance a group of grid points at a time, rather than sorting the solution in the narrow band to march forward a single grid point. After selecting a group of grid points appropriately, the GMM advances the group in two iterations for the cost of slightly larger than one iteration. Numerical results are presented to show the efficiency of the method, applied to the eikonal equation in two and three dimensions. [ABSTRACT FROM AUTHOR]