A greedy algorithm for the optimal basis problem

The following problem is considered. Givenm+1 points {x _i }₀ ^m inR ⁿ which generate anm-dimensional linear manifold, construct for this manifold a maximally linearly independent basis that consists of vectors of the formx _i −x _j . This problem is present in, e.g., stable variants of the secant and interpolation methods, where it is required to approximate the Jacobian matrixf′ of a nonlinear mappingf by using values off computed atm+1 points. In this case, it is also desirable to have a combination of finite differences with maximal linear independence. As a natural measure of linear independence, we consider the hadamard condition number which is minimized to find an optimal combination ofm pairs {x _i ,x _j }. We show that the problem is not NP-hard, but can be reduced to the minimum spanning tree problem, which is solved by the greedy algorithm inO(m ²) time. The complexity of this reduction is equivalent to onem×n matrix-matrix multiplication, and according to the Coppersmith-Winograd estimate, is belowO(n ^2.376) form=n. Applications of the algorithm to interpolation methods are discussed. Part of the work was done while the author was visiting DIMACS, an NSF Science and Technology Center funded under contract STC-91-19999; DIMACS is a cooperative project of Rutgers University, Princeton University, AT&T Bell Laboratories and Bellcore, NJ, USA.     

One-step Taylor–Galerkin methods for convection–diffusion problems

Third and fourth order Taylor–Galerkin schemes have shown to be efficient finite element schemes for the numerical simulation of time-dependent convective transport problems. By contrast, the application of higher-order Taylor–Galerkin schemes to mixed problems describing transient transport by both convection and diffusion appears to be much more difficult. In this paper we develop two new Taylor–Galerkin schemes maintaining the accuracy properties and improving the stability restrictions in convection–diffusion. We also present an efficient algorithm for solving the resulting system of the finite element method. Finally we present two numerical simulations that confirm the properties of the methods.     

Continued fractions and numeration in the Fibonacci base

Let φ be the golden ratio. We define and study a continued φ-fraction algorithm, inspired by Euclid's algorithm. We show that any non-negative element of Q(φ) has a finite continued φ-fraction.     

Robust Approximate Zeros in Banach Space

We extend Smale’s concept of approximate zeros of an analytic function on a Banach space to two computational models that account for errors in the computation: first, the weak model where the computations are done with a fixed precision; and second, the strong model where the computations are done with varying precision. For both models, we develop a notion of robust approximate zero and derive a corresponding robust point estimate. A useful specialization of an analytic function on a Banach space is a system of integer polynomials. Given such a zero-dimensional system, we bound the complexity of computing an absolute approximation to a root of the system using the strong model variant of Newton’s method initiated from a robust approximate zero. The bound is expressed in terms of the condition number of the system and is a generalization of a well-known bound of Brent to higher dimensions.      

Variance bounds and existence results for randomly shifted lattice rules

We study the convergence of the variance for randomly shifted lattice rules for numerical multiple integration over the unit hypercube in an arbitrary number of dimensions. We consider integrands that are square integrable but whose Fourier series are not necessarily absolutely convergent. For such integrands, a bound on the variance is expressed through a certain type of weighted discrepancy. We prove existence and construction results for randomly shifted lattice rules such that the variance bounds are almost O(n^−α)$O\left(n^{-\alpha }\right)$, where n$n$ is the number of function evaluations and α>1$\alpha >1$ depends on our assumptions on the convergence speed of the Fourier coefficients. These results hold for general weights, arbitrary n$n$, and any dimension. With additional conditions on the weights, we obtain a convergence that holds uniformly in the dimension, and this provides sufficient conditions for strong tractability of the integration problem. We also show that lattice rules that satisfy these bounds are not difficult to construct explicitly and we provide numerical illustrations of the behaviour of construction algorithms.     

Arithmetic of the Ramanujan-Göllnitz-Gordon continued fraction

Text

We extend the results of Chan and Huang [H.H. Chan, S.-S. Huang, On the Ramanujan-Göllnitz-Gordon continued fraction, Ramanujan J. 1 (1997) 75-90] and Vasuki, Srivatsa Kumar [K.R. Vasuki, B.R. Srivatsa Kumar, Certain identities for Ramanujan-Göllnitz-Gordon continued fraction, J. Comput. Appl. Math. 187 (2006) 87-95] to all odd primes p on the modular equations of the Ramanujan-Göllnitz-Gordon continued fraction v(τ) by computing the affine models of modular curves X(Γ) with Γ=Γ₁(8)∩Γ₀(16p). We then deduce the Kronecker congruence relations for these modular equations. Further, by showing that v(τ) is a modular unit over Z we give a new proof of the fact that the singular values of v(τ) are units at all imaginary quadratic arguments and obtain that they generate ray class fields modulo 8 over imaginary quadratic fields.

Video

For a video summary of this paper, please visit http://www.youtube.com/watch?v=FWdmYvdf5Jg.     

Orthogonal random vectors and the Hurwitz-Radon-Eckmann theorem

In several different aspects of algebra and topology the following problem is of interest: find the maximal number of unitary antisymmetric operatorsU _i inH = ℝ ⁿ with the propertyU _i U _j = −U _j U _i (i≠j). The solution of this problem is given by the Hurwitz-Radon-Eckmann formula. We generalize this formula in two directions: all the operatorsU _i must commute with a given arbitrary self-adjoint operator andH can be infinite-dimensional. Our second main result deals with the conditions for almost sure orthogonality of two random vectors taking values in a finite or infinite-dimensional Hilbert spaceH. Finally, both results are used to get the formula for the maximal number of pairwise almost surely orthogonal random vectors inH with the same covariance operator and each pair having a linear support inH⊕H. The paper is based on the results obtained jointly with N.P. Kandelaki (see [1,2,3]).     

The exponential integrator scheme for stochastic partial differential equations: Pathwise error bounds

We present an error analysis for the pathwise approximation of a general semilinear stochastic evolution equation in d dimensions. We discretise in space by a Galerkin method and in time by using a stochastic exponential integrator. We show that for spatially regular (smooth) noise the number of nodes needed for the noise can be reduced and that the rate of convergence degrades as the regularity of the noise reduces (and the noise becomes rougher).     

Improved lower bounds on the length of Davenport-Schinzel sequences

We derive lower bounds on the maximal length _s(n) of (n, s) Davenport Schinzel sequences. These bounds have the form _2s=1(n)=(n^s(n)), where(n) is the extremely slowly growing functional inverse of the Ackermann function. These bounds extend the nonlinear lower bound ₃ (n)=(n(n)) due to Hart and Sharir [5], and are obtained by an inductive construction based upon the construction given in [5].Work on this paper has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation.     

Error expansion for the discretization of backward stochastic differential equations

We study the error induced by the time discretization of decoupled forward–backward stochastic differential equations (X,Y,Z)$(X,Y,Z)$. The forward component X$X$ is the solution of a Brownian stochastic differential equation and is approximated by a Euler scheme X^N$X^N$ with N$N$ time steps. The backward component is approximated by a backward scheme. Firstly, we prove that the errors (Y^N−Y,Z^N−Z)$(Y^N-Y,Z^N-Z)$ measured in the strong _Lp$L_p$-sense (p≥1$p\ge 1$) are of order N^−1/2$N^{-1/2}$ (this generalizes the results by Zhang [J. Zhang, A numerical scheme for BSDEs, The Annals of Applied Probability 14 (1) (2004) 459–488]). Secondly, an error expansion is derived: surprisingly, the first term is proportional to X^N−X$X^N-X$ while residual terms are of order N⁻¹$N^{-1}$.     

A note on an inverse problem for lattice points

Let K⊆R² be a compact set such that K+Z²=R² and let K−K={a−b|a,b∈K}. We prove, via Algebraic Topology, that the integer points of the difference set of K, (K−K)∩Z², is not contained on the coordinate axes, Z×{0}∪{0}×Z. This result implies the negative answer to the inverse problem posed by M.B. Nathanson (2010) [5].     

Tight bounds for minimax grid matching with applications to the average case analysis of algorithms

The minimax grid matching problem is a fundamental combinatorial problem associated with the average case analysis of algorithms. The problem has arisen in a number of interesting and seemingly unrelated areas, including wafer-scale integration of systolic arrays, two-dimensional discrepancy problems, and testing pseudorandom number generators. However, the minimax grid matching problem is best known for its application to the maximum up-right matching problem. The maximum up-right matching problem was originally defined by Karp, Luby and Marchetti-Spaccamela in association with algorithms for 2-dimensional bin packing. More recently, the up-right matching problem has arisen in the average case analysis of on-line algorithms for 1-dimen-sional bin packing and dynamic allocation.In this paper, we solve both the minimax grid matching problem and the maximum up-right matching problem. As a direct result, we obtain tight upper bounds on the average case behavior of the best algorithms known for 2-dimensional bin packing, 1-dimensional on-line bin packing and on-line dynamic allocation. The results also solve a long-open question in mathematical statistics.This research was supported by Air Force Contracts AFOSR-82-0326 and AFOSR-86-0078, NSF Grant 8120790, and DARPA contract N00014-80-C-0326. In addition, Tom Leighton was supported by an NSF Presidential Young Investigator Award with matching funds from Xerox and IBM.     

An inverse first-passage problem for one-dimensional diffusions with random starting point

We consider an inverse first-passage time (FPT) problem for a homogeneous one-dimensional diffusion X(t), starting from a random position η. Let S(t) be an assigned boundary, such that P(η≥S(0))=1, and F an assigned distribution function. The problem consists of finding the distribution of η such that the FPT of X(t) below S(t) has distribution F. We obtain some generalizations of the results of Jackson et al., 2009, which refer to the case when X(t) is Brownian motion and S(t) is a straight line across the origin.     

Some upper and lower bounds on the coupon collector problem

The classical coupon collector problem is closely related to probabilistic-packet-marking (PPM) schemes for IP traceback problem in the Internet. In this paper, we study the classical coupon collector problem, and derive some upper and lower bounds of the complementary cumulative distribution function (ccdf) of the number of objects (coupons) that one has to check in order to detect a set of different objects. The derived bounds require much less computation than the exact formula. We numerically find that the proposed bounds are very close to the actual ccdf when detecting probabilities are set to the values common to the PPM schemes.     

Newton’s method and high-order algorithms for the nth root computation

Two modifications of Newton’s method to accelerate the convergence of the n$n$th root computation of a strictly positive real number are revisited. Both modifications lead to methods with prefixed order of convergence p∈N,p≥2$p\in \mathbb{N},p\ge 2$. We consider affine combinations of the two modified p$p$th-order methods which lead to a family of methods of order p$p$ with arbitrarily small asymptotic constants. Moreover the methods are of order p+1$p+1$ for some specific values of a parameter. Then we consider affine combinations of the three methods of order p+1$p+1$ to get methods of order p+1$p+1$ again with arbitrarily small asymptotic constants. The methods can be of order p+2$p+2$ with arbitrarily small asymptotic constants, and also of order p+3$p+3$ for some specific values of the parameters of the affine combination. It is shown that infinitely many p$p$th-order methods exist for the n$n$th root computation of a strictly positive real number for any p≥3$p\ge 3$.     

The missing boundary problem for smooth manifolds of dimension greater than or equal to six

Let M be a non-compact differentiable manifold of dimension ?6. Suppose both M and ?M are 1-ended spaces. We give necessary and sufficient conditions for M to be diffeomorphic to the complement of a compact subset of the boundary of a compact manifold. There are four conditions: two geometric conditions and two algebraic obstructions. We give examples to show that these obstructions are not always trivial. In particular, an example of a manifold is constructed which does not have a completion but any tubular neighborhood of codimension ?3 has a completion. We also classify the different ways to complete a given manifold.