Projection of diffusions on submanifolds: Application to mean force computation

We consider the problem of sampling a Boltzmann‐Gibbs probability distribution when this distribution is restricted (in some suitable sense) on a submanifold Σ of ?ⁿ implicitly defined by N constraints q₁(x) = ? = q_N(x) = 0 (N < n). This problem arises, for example, in systems subject to hard constraints or in the context of free energy calculations. We prove that the constrained stochastic differential equations (i.e., diffusions) proposed in [7, 13] are ergodic with respect to this restricted distribution. We also construct numerical schemes for the integration of the constrained diffusions. Finally, we show how these schemes can be used to compute the gradient of the free energy associated with the constraints. © 2007 Wiley Periodicals, Inc.     

Covering times of random walks on bounded degree trees and other graphs

The motivating problem for this paper is to find the expected covering time of a random walk on a balanced binary tree withn vertices. Previous upper bounds for general graphs ofO(|V| |E|)⁽¹⁾ andO(|V| |E|/d _min)⁽²⁾ imply an upper bound ofO(n ²). We show an upper bound on general graphs ofO( |E| log |V|), which implies an upper bound ofO(n log² n). The previous lower bound was (|V| log |V|) for trees.⁽²⁾ In our main result, we show a lower bound of (|V| (log _{d max} |V|)²) for trees, which yields a lower bound of (n log² n). We also extend our techniques to show an upper bound for general graphs ofO(max{E T_i} log |V|).     

Euclidean minimum spanning trees and bichromatic closest pairs

We present an algorithm to compute a Euclidean minimum spanning tree of a given setS ofN points inE ^d in timeO(F _d (N,N) log ^d N), whereF _d (n,m) is the time required to compute a bichromatic closest pair amongn red andm green points inE ^d . IfF _d (N,N)=Ω(N ^1+ε), for some fixed ɛ>0, then the running time improves toO(F _d (N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected timeO((nm logn logm)^2/3+m log² n+n log² m) inE ₃, which yields anO(N ^4/3 log^4/3 N) expected time, algorithm for computing a Euclidean minimum spanning tree ofN points inE ³. Ind≥4 dimensions we obtain expected timeO((nm)^{1−1/([d/2]+1)+ε}+m logn+n logm) for the bichromatic closest pair problem andO(N ^{2−2/([d/2]+1)ε}) for the Euclidean minimum spanning tree problem, for any positive ɛ. The first, second, and fourth authors acknowledge support from the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center under NSF Grant STC 88-09648. The second author's work was supported by the National Science Foundation under Grant CCR-8714565. The third author's work was supported by the Deutsche Forschungsgemeinschaft under Grant A1 253/1-3, Schwerpunktprogramm “Datenstrukturen und effiziente Algorithmen”. The last two authors' work was also partially supported by the ESPRIT II Basic Research Action of the EC under Contract No. 3075 (project ALCOM).     

A mixed‐type Galerkin variational formulation and fast algorithms for variable‐coefficient fractional diffusion equations

We consider the variable‐coefficient fractional diffusion equations with two‐sided fractional derivative. By introducing an intermediate variable, we propose a mixed‐type Galerkin variational formulation and prove the existence and uniqueness of the variational solution over . On the basis of the formulation, we develop a mixed‐type finite element procedure on commonly used finite element spaces and derive the solvability of the finite element solution and the error bounds for the unknown and the intermediate variable. For the Toeplitz‐like linear system generated by discretization, we design a fast conjugate gradient normal residual method to reduce the storage from O(N²) to O(N) and the computing cost from O(N³) to O(NlogN). Numerical experiments are included to verify our theoretical findings. Copyright © 2017 John Wiley & Sons, Ltd.     

Two-Grid Solution of Symm's Integral Equation

We propose two-grid iteration methods for Symm's integral equation discretized by quadrature-collocation or quadrature methods. Asymptotically the optimal order of error estimate is achieved already on the first iteration, for some modifications on the second iteration. This enables us to introduce some solvers which are of the optimal convergence order and cheap in a practical implementation; the cost varies between O(N²) and O(N log N) arithmetic operations. Numerical experiments confirm the approximation properties of the schemes.     

Character table of a controlling association scheme defined by the general orthogonal groupO(3,q).

LetN _m (q) be the set of nonisotropic lines in the vector space of dimensionm over a finite field of orderq. In a paper by Bannai, Hao, Song and Wei, it was shown that the association scheme character tableP(Sp(2n, q),N _2n (q)), withn 3 andq odd, is controlled byP(Sp(4,q),N ₄(q)) which is in turn controlled byP(O(3,q),O(3,q)/O ⁺ (2,q)). Our purpose in this paper is to compute the entries in the character tableP(O(3,q), O(3,q)/O ⁺ (2,q)) explicitly, which is left open in that paper.     

A Richardson scheme of the decomposition method for solving singularly perturbed parabolic reaction-diffusion equation

For the one-dimensional singularly perturbed parabolic reaction-diffusion equation with a perturbation parameter ɛ, where ɛ ∈ (0, 1], the grid approximation of the Dirichlet problem on a rectangular domain in the (x, t)-plane is examined. For small ɛ, a parabolic boundary layer emerges in a neighborhood of the lateral part of the boundary of this domain. A new approach to the construction of ɛ-uniformly converging difference schemes of higher accuracy is developed for initial boundary value problems. The asymptotic construction technique is used to design the base decomposition scheme within which the regular and singular components of the grid solution are solutions to grid subproblems defined on uniform grids. The base scheme converges ɛ-uniformly in the maximum norm at the rate of O(N ⁻²ln² N + N ₀⁻¹), where N + 1 and N ₀ + 1 are the numbers of nodes in the space and time meshes, respectively. An application of the Richardson extrapolation technique to the base scheme yields a higher order scheme called the Richardson decomposition scheme. This higher order scheme convergesɛ-uniformly at the rate of O(N ⁻⁴ln⁴ N + N ₀⁻²). For fixed values of the parameter, the convergence rate is O(N ⁻⁴ + N ₀⁻²).     

Improved approximations of the solution and derivatives to a singularly perturbed reaction-diffusion equation based on the solution decomposition method

In the case of the Dirichlet problem for a singularly perturbed ordinary differential reaction-diffusion equation, a new approach is used to the construction of finite difference schemes such that their solutions and their normalized first- and second-order derivatives converge in the maximum norm uniformly with respect to a perturbation parameter ɛ ∈(0, 1]; the normalized derivatives are ɛ-uniformly bounded. The key idea of this approach to the construction of ɛ-uniformly convergent finite difference schemes is the use of uniform grids for solving grid subproblems for the regular and singular components of the grid solution. Based on the asymptotic construction technique, a scheme of the solution decomposition method is constructed such that its solution and its normalized first- and second-order derivatives converge ɛ-uniformly at the rate of O(N ⁻²ln² N), where N + 1 is the number of points in the uniform grids. Using the Richardson technique, an improved scheme of the solution decomposition method is constructed such that its solution and its normalized first and second derivatives converge ɛ-uniformly in the maximum norm at the same rate of O(N ⁻⁴ln⁴ N).     

Central limit theorems for the ergodic adding machine

In this paper we find a second class of sequences of random numbers (x _n ) _n=1 ^∞ (the orbit of the ergodic adding machine) such that the corresponding sequences of zeros and ones 1_[0,y](x _n) (n=1,2,...,N) satisfy Central Limit Theorems with extremely small standard deviationσ _N=O(√logN), instead ofO(√N), asN → ∞. Dedicated to Professor Benjamin Weiss on the occasion of his 60^th birthday.     

The negative discrete spectrum of the operator (-τ) l -αV inL 2(R d ) ford even and 2l≥dinL 2(R d ) ford even and 2l≥d

We study the asymptotic behaviour ofN(α)—the number of negative eigenvalues of the operator (-τ) ^l -αV inL ₂(R ^d ) for an evend and2l≥d. This is the only case where the previously known results were far from being complete. In order to describe our results we introduce an auxiliary ordinary differential operator (system) on the semiaxis. Depending on the spectral properties of this operator we can distinguish between three cases whereN(α) is of the Weyl-type,N(α) is of the Weyl-order but not the Weyl-type coefficient and finally whereN(α)=O(α^q) withq>d/2l.     

Discrete fourier transform computation using prime Ramanujan numbers

Ramanujan numbers were introduced in [2] to implement discrete fourier transform (DFT) without using any multiplication operation. Ramanujan numbers are related to π and integers which are powers of 2. If the transform sizeN, is a Ramanujan number, then the computational complexity of the algorithms used for computing isO(N ²) addition and shift operations, and no multiplications. In these algorithms, the transform can be computed sequentially with a single adder inO(N ²) addition times. Parallel implementation of the algorithm can be executed inO(N) addition times, withO(N) number of adders. Some of these Ramanujan numbers of order-2 are related to the Biblical and Babylonian values of π [1]. In this paper, we analytically obtain upper bounds on the degree of approximation in the computation of DFT if JV is a prime Ramanujan number.     

On the Hopfield model at the critical temperature

We study the Hopfield model at temperature 1, when thenumber M(N) of patterns grows a bit slower than N. We reach a goodunderstanding of the model whenever M(N)≤N/(log N)¹¹. For example, we show that if M(N)→∞, for two typical configurations σ ¹, σ ², (∑ _{i ≤ N} σ¹ _i σ² _i )² is close to NM(N). Received: 15 December 1999 / Revised version: 8 December 2000 / Published online: 23 August 2001     

Linear bounds for levels of stable rationality

Let G be one of the groups SL _n (ℂ), Sp_2n (ℂ), SO _m (ℂ), O _m (ℂ), or G ₂. For a generically free G-representation V, we say that N is a level of stable rationality for V/G if V/G × ℙ ^N is rational. In this paper we improve known bounds for the levels of stable rationality for the quotients V/G. In particular, their growth as functions of the rank of the group is linear for G being one of the classical groups.     

A higher order richardson scheme for a singularly perturbed semilinear elliptic convection-diffusion equation

The Dirichlet problem on a vertical strip is examined for a singularly perturbed semilinear elliptic convection-diffusion equation. For this problem, the basic nonlinear difference scheme based on the classical approximations on piecewise uniform grids condensing in the vicinity of boundary layers converges ɛ-uniformly with an order at most almost one. The Richardson technique is used to construct a nonlinear scheme that converges ɛ-uniformly with an improved order, namely, at the rate O(N ₁⁻²ln² N ₁ + N ₂⁻²), where N ₁ + 1 and N ₂ + 1 are the number of grid nodes along the x ₁-axis and per unit interval of the x ₂-axis, respectively. This nonlinear basic scheme underlies the linearized iterative scheme, in which the nonlinear term is calculated using the values of the sought function found at the preceding iteration step. The latter scheme is used to construct a linearized iterative Richardson scheme converging ɛ-uniformly with an improved order. Both the basic and improved iterative schemes converge ɛ-uniformly at the rate of a geometric progression as the number of iteration steps grows. The upper and lower solutions to the iterative Richardson schemes are used as indicators, which makes it possible to determine the iteration step at which the same ɛ-uniform accuracy is attained as that of the non-iterative nonlinear Richardson scheme. It is shown that no Richardson schemes exist for the convection-diffusion boundary value problem converging ɛ-uniformly with an order greater than two. Principles are discussed on which the construction of schemes of order greater than two can be based.     

A result on resolutions of Veronese embeddings

This paper deals with syzygies of the ideals of the Veronese embeddings. By Green’s Theorem we know thatO _P ⁿ (d) satisfies Green-Lazarsfeld’s PropertyN _p ∀d≥p, ∀n. By Ottaviani-Paoletti’s theorem ifn≥2, d≥3 and 3d−2≤p thenO _P ⁿ (d) does not satisfy PropertyN _p. The casesn≥3, d≥3, d<p<3d−2 are still open (exceptn=d=3). Here we deal with one of these cases, namely we prove thatO _P ⁿ (3) satisfies PropertyN ₄ ∀n. Besides we prove thatO _P ⁿ (d) satisfiesN _p ∀n≥p iffO _P ⁿ (d) satisfiesN _p.

---

Sunto L’argomento di questo articolo sono le sizigie degli ideali delle varietà di Veronese. Per il teorema di Green sappiamo cheO _P ⁿ (d) soddisfa la proprietàN _p di Green-Lazarsfeld ∀d≥p, ∀n. Per il teorema di Ottaviani-Paoletti sen≥2, d≥3 and 3d−2≤p alloraO _P ⁿ (d) non soddisfa la ProprietàN _p. I casin≥3, d≥3, d<p<3d−2 sono ancora aperti (eccetton=d=3). Qui consideriamo uno di tali casi, precisamente proviamo cheO _P ⁿ (3) soddisfa la ProprietàN ₄ ∀n. Inoltre proviamo cheO _P ⁿ (d) soddisfaN _p ∀n≥p se e solo seO _P ^p (d) satisfiesN _p.

     

Solving the equation −uxx − ϵuyy = f(x,y, u) by an O(h4) finite difference method

The semi‐linear equation −u_xx − ϵu_yy = f(x, y, u) with Dirichlet boundary conditions is solved by an O(h⁴) finite difference method, which has local truncation error O(h²) at the mesh points neighboring the boundary and O(h⁴) at most interior mesh points. It is proved that the finite difference method is O(h⁴) uniformly convergent as h → 0. The method is considered in the form of a system of algebraic equations with a nine diagonal sparse matrix. The system of algebraic equations is solved by an implicit iterative method combined with Gauss elimination. A Mathematica module is designed for the purpose of testing and using the method. To illustrate the method, the equation of twisting a springy rod is solved. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 395–407, 2000     

A fast algorithm for the evaluation of heat potentials

Numerical methods for solving the heat equation via potential theory have been hampered by the high cost of evaluating heat potentials. When M points are used in the discretization of the boundary and N time steps are computed, an amount of work of the order O(N²M²) has traditionally been required. In this paper, we present an algorithm which requires an amount of work of the order O(NM), and we observe speedups of five orders of magnitude for large-scale problems. Thus, the method makes it possible to solve the heat equation by potential theory in practical situations.     

Bose-Mesner Algebras Associated with Four-Weight Spin Models

It is known that for each matrix W _i and it's transpose ^t W _i in any four-weight spin model (X, W ₁, W ₂, W ₃, W ₄; D), there is attached the Bose-Mesner algebra of an association scheme, which we call Nomura algebra. They are denoted by N(W _i ) and N( ^t W _i ) = N′(W _i ) respectively. H. Guo and T. Huang showed that some of them coincide with a self-dual Bose-Mesner algebra, that is, N(W ₁) = N′(W ₁) = N(W ₃) = N′(W ₃) holds. In this paper we show that all of them coincide, that is, N(W _i ), N′(W _i ), i=1, 2, 3, 4, are the same self-dual Bose-Mesner algebra. Received: June 17, 1999 Final version received: Januray 17, 2000     

On a proposed divide-and-conquer minimal spanning tree algorithm

In a recent paper published in this journal, R. Chang and R. Lee purport to devise anO(N logN) time minimal spanning tree algorithm forN points in the plane that is based on a divide-and-conquer strategy using Voronoi diagrams. In this brief note, we present families of problem instances to show that the Chang-Lee worst-case timing analysis is incorrect, resulting in a time bound ofO(N ² logN). Since it is known that alternate, trulyO(N logN) time algorithms are available anyway, the general utility of the Chang-Lee algorithm is questionable.This author's research is supported in part by the Washington State Technology Center and by the National Science Foundation under grants ECS-8403859 and MIP-8603879.