Multiple point evaluation on combined tensor product supports

We consider the multiple point evaluation problem for an n-dimensional space of functions [???1,1[ ^d ?? spanned by d-variate basis functions that are the restrictions of simple (say linear) functions to tensor product domains. For arbitrary evaluation points this task is faced in the context of (semi-)Lagrangian schemes using adaptive sparse tensor approximation spaces for boundary value problems in moderately high dimensions. We devise a fast algorithm for performing m?≥?n point evaluations of a function in this space with computational cost O(mlog ^d n). We resort to nested segment tree data structures built in a preprocessing stage with an asymptotic effort of O(nlog ^d???1 n).     

Eigenvalues and invariants of tensors

A tensor is represented by a supermatrix under a co-ordinate system. In this paper, we define E-eigenvalues and E-eigenvectors for tensors and supermatrices. By the resultant theory, we define the E-characteristic polynomial of a tensor. An E-eigenvalue of a tensor is a root of the E-characteristic polynomial. In the regular case, a complex number is an E-eigenvalue if and only if it is a root of the E-characteristic polynomial. We convert the E-characteristic polynomial of a tensor to a monic polynomial and show that the coefficients of that monic polynomial are invariants of that tensor, i.e., they are invariant under co-ordinate system changes. We call them principal invariants of that tensor. The maximum number of principal invariants of mth order n-dimensional tensors is a function of m and n. We denote it by d(m,n) and show that d(1,n)=1, d(2,n)=n, d(m,2)=m for m?3 and d(m,n)?mn−1+?+m for m,n?3. We also define the rank of a tensor. All real eigenvectors associated with nonzero E-eigenvalues are in a subspace with dimension equal to its rank.     

The measure problem for rectangular ranges in d-space

Klee recently posed the question: find an efficient algorithm for computing the measure of a set of n intervals on the line, and the analog for n hyperrectangles (ranges) in d-space. The one-dimensional case is easily solved in O(n log n) and Bentley has proved an O(n^d?1log n) algorithm for dimension d ≥ 2. We present an algorithm for Klee's measure problem that has a worst-case running time of only O(n^d?1) for d?3. While Bentley's algorithm is based on segment trees and requires only linear storage for any dimension, the new method is based on quad-trees and requires quadratic storage for d > 2.     

Some open problems concerning the star-discrepancy

We discuss open problems on the minimal star-discrepancy of an n-point set in the d-dimensional unit cube [0,1]^d. We emphasize the aspect of dimension dependence and of simultaneous dependence on n and d.     

Fast and accurate tensor approximation of a multivariate convolution with linear scaling in dimension

In the present paper we present the tensor-product approximation of a multidimensional convolution transform discretized via a collocation-projection scheme on uniform or composite refined grids. Examples of convolving kernels are provided by the classical Newton, Slater (exponential) and Yukawa potentials, 1/‖x‖, and with x∈R^d. For piecewise constant elements on the uniform grid of size n^d, we prove quadratic convergence O(h²) in the mesh parameter h=1/n, and then justify the Richardson extrapolation method on a sequence of grids that improves the order of approximation up to O(h³). A fast algorithm of complexity O(dR₁R₂nlogn) is described for tensor-product convolution on uniform/composite grids of size n^d, where R₁,R₂ are tensor ranks of convolving functions. We also present the tensor-product convolution scheme in the two-level Tucker canonical format and discuss the consequent rank reduction strategy. Finally, we give numerical illustrations confirming: (a) the approximation theory for convolution schemes of order O(h²) and O(h³); (b) linear-logarithmic scaling of 1D discrete convolution on composite grids; (c) linear-logarithmic scaling in n of our tensor-product convolution method on an n×n×n grid in the range n≤16384.     

Tensor-Structured Preconditioners and Approximate Inverse of Elliptic Operators in ℝ d

In the present paper we analyze a class of tensor-structured preconditioners for the multidimensional second-order elliptic operators in ? ^d , d≥2. For equations in a bounded domain, the construction is based on the rank-R tensor-product approximation of the elliptic resolvent ? _R ≈(??λ I)^?1, where ? is the sum of univariate elliptic operators. We prove the explicit estimate on the tensor rank R that ensures the spectral equivalence. For equations in an unbounded domain, one can utilize the tensor-structured approximation of Green’s kernel for the shifted Laplacian in ? ^d , which is well developed in the case of nonoscillatory potentials. For the oscillating kernels e ^{?i κ‖x‖}/‖x‖, x∈? ^d , κ∈?₊, we give constructive proof of the rank-O(κ) separable approximation. This leads to the tensor representation for the discretized 3D Helmholtz kernel on an n×n×n grid that requires only O(κ?|log?ε|²? n) reals for storage. Such representations can be applied to both the 3D volume and boundary calculations with sublinear cost O(n ²), even in the case κ=O(n). Numerical illustrations demonstrate the efficiency of low tensor-rank approximation for Green’s kernels e ^?λ‖x‖/‖x‖, x∈?³, in the case of Newton (λ=0), Yukawa (λ∈?₊), and Helmholtz (λ=i κ,?κ∈?₊) potentials, as well as for the kernel functions 1/‖x‖ and 1/‖x‖ ^d?2, x∈? ^d , in higher dimensions d>3. We present numerical results on the iterative calculation of the minimal eigenvalue for the d-dimensional finite difference Laplacian by the power method with the rank truncation and based on the approximate inverse ? _R ≈(?Δ)^?1, with 3≤d≤50.     

A note on maximally repeated sub-patterns of a point set

We answer a question raised by Brass on the number of maximally repeated sub-patterns in a set of n points in R^d. We show that this number, which was conjectured to be polynomial, is in fact Θ(2^n/2) in the worst case, regardless of the dimension d.     

On the notion of canonical dimension for algebraic groups

We define and study a numerical invariant of an algebraic group action which we call the canonical dimension. We then apply the resulting theory to the problem of computing the minimal number of parameters required to define a generic hypersurface of degree d in P^n-1.     

Two-scale sparse finite element approximations

To reduce computational cost,we study some two-scale finite element approximations on sparse grids for elliptic partial differential equations of second order in a general setting.Over any tensor product domain ?R~d with d = 2,3,we construct the two-scale finite element approximations for both boundary value and eigenvalue problems by using a Boolean sum of some existing finite element approximations on a coarse grid and some univariate fine grids and hence they are cheaper approximations.As applications,we obtain some new efficient finite element discretizations for the two classes of problem:The new two-scale finite element approximation on a sparse grid not only has the less degrees of freedom but also achieves a good accuracy of approximation.     

A bound on the dimension of interval orders

We make use of the partially ordered set (I(0, n), <) consisting of all closed intervals of real numbers with integer endpoints (including the degenerate intervals with the same right- and left-hand endpoints), ordered by [a, b] < [c, d] if b < c, to show that there is no bound on the order dimension of interval orders. We then turn to the problem of computing the dimension of I(0, n), showing that I(0, 10) has dimension 3 but I(0, 11) has dimension 4. We use these results as initial conditions in obtaining an upper bound on the dimension of I(0, n) as a logarithmic function of n. It is our belief that this example is a “canonical” example for interval orders, so that the computation of its dimension should have significant impact on the problem of computing the dimension of interval orders in general.     

Norm expansion along a zero variety

The reproducing kernel function of a weighted Bergman space over domains in Cd is known explicitly in only a small number of instances. Here, we introduce a process of orthogonal norm expansion along a subvariety of (complex) codimension 1, which also leads to a series expansion of the reproducing kernel in terms of reproducing kernels defined on the subvariety. The problem of finding the reproducing kernel is thus reduced to the same kind of problem when one of the two entries is on the subvariety. A complete expansion of the reproducing kernel may be achieved in this manner. We carry this out in dimension d=2 for certain classes of weighted Bergman spaces over the bidisk (with the diagonal z₁=z₂ as subvariety) and the ball (with z₂=0 as subvariety), as well as for a weighted Bargmann-Fock space over C² (with the diagonal z₁=z₂ as subvariety).     

On the homogeneous algebraic graphs of large girth and their applications

Families of finite graphs of large girth were introduced in classical extremal graph theory. One important theoretical result here is the upper bound on the maximal size of the graph with girth ?2d established in Even Circuit Theorem by P. Erdös. We consider some results on such algebraic graphs over any field. The upper bound on the dimension of variety of edges for algebraic graphs of girth ?2d is established. Getting the lower bound, we use the family of bipartite graphs D(n,K) with n?2 over a field K, whose partition sets are two copies of the vector space Kⁿ. We consider the problem of constructing homogeneous algebraic graphs with a prescribed girth and formulate some problems motivated by classical extremal graph theory. Finally, we present a very short survey on applications of finite homogeneous algebraic graphs to coding theory and cryptography.     

On the risk of estimates for block decreasing densities

A density f=f(x₁,…,x_d) on [0,∞)^d is block decreasing if for each j∈{1,…,d}, it is a decreasing function of x_j, when all other components are held fixed. Let us consider the class of all block decreasing densities on [0,1]^d bounded by B. We shall study the minimax risk over this class using n i.i.d. observations, the loss being measured by the L₁ distance between the estimate and the true density. We prove that if S=log(1+B), lower bounds for the risk are of the form C(S^d/n)^1/(d+2), where C is a function of d only. We also prove that a suitable histogram with unequal bin widths as well as a variable kernel estimate achieve the optimal multivariate rate. We present a procedure for choosing all parameters in the kernel estimate automatically without loosing the minimax optimality, even if B and the support of f are unknown.     

An approximation scheme for a problem of search for a vector subset

We consider the following clustering problem: Given a vector set, find a subset of cardinality k and minimum square deviation from its mean. The distance between the vectors is defined by the Euclideanmetric. We present an approximation scheme (PTAS) that allows us to solve this problem with an arbitrary relative error ? in time O(n ^2/?+1(9/?)^3/? d), where n is the number of vectors of the input set and d denotes the dimension of the space.     

Local well-posedness of lower regularity solutions for the incompressible viscoelastic fluid system

In the present paper,the local well-posedness of the incompressible viscoelastic fluid system in the whole space is proved under the following assumption on the initial data:the deformation tensor is Hlder continuous and the velocity is Lp integrable,pd,where d is the space dimension.     

A remark on full rank perfect codes

Any full rank perfect 1-error correcting binary code of length n=2^k-1 and with a kernel of dimension n-log(n+1)-m, where m is sufficiently large, may be used to construct a full rank perfect 1-error correcting binary code of length 2^m-1 and with a kernel of dimension n-log(n+1)-k. Especially we may construct full rank perfect 1-error correcting binary codes of length n=2^m-1 and with a kernel of dimension n-log(n+1)-4 for m=6,7,…,10.This result extends known results on the possibilities for the size of a kernel of a full rank perfect code.     

An exact algorithm for finding a vector subset with the longest sum

We consider the problem: Given a set of n vectors in the d-dimensional Euclidean space, find a subsetmaximizing the length of the sum vector.We propose an algorithm that finds an optimal solution to this problem in time O(n^d?1(d + logn)). In particular, if the input vectors lie in a plane then the problem is solvable in almost linear time.     

On the asymptotic optimality of a solution of the euclidean problem of covering a graph by <Emphasis Type="Italic">m</Emphasis> nonadjacent cycles of maximum total weight

In the problem of covering an n-vertex graph by m cycles of maximum total weight, it is required to find a family of m vertex-nonadjacent cycles such that it covers all vertices of the graph and the total weight of edges in the cover is maximum. The paper presents an algorithm for approximately solving the problem of covering a graph in Euclidean d-space R^d by m nonadjacent cycles of maximum total weight. The algorithm has time complexity O(n³). An estimate of the accuracy of the algorithm depending on the parameters d, m, and n is substantiated; it is shown that if the dimension d of the space is fixed and the number of covering cycles is m = o(n), then the algorithm is asymptotically exact.     

On the observation closest to the origin

Out of n i.i.d. random vectors in $\text{R}$^d let X¹_n be the one closest to the origin. We show that X¹_n has a nondegenerate limit distribution if and only if the common probability distribution satisfies a condition of multidimensional regular variation. The result is then applied to a problem of density estimation.     

Cutoff for the Ising model on the lattice

Introduced in 1963, Glauber dynamics is one of the most practiced and extensively studied methods for sampling the Ising model on lattices. It is well known that at high temperatures, the time it takes this chain to mix in L ¹ on a system of size n is O(logn). Whether in this regime there is cutoff, i.e. a sharp transition in the L ¹-convergence to equilibrium, is a fundamental open problem: If so, as conjectured by Peres, it would imply that mixing occurs abruptly at (c+o(1))logn for some fixed c>0, thus providing a rigorous stopping rule for this MCMC sampler. However, obtaining the precise asymptotics of the mixing and proving cutoff can be extremely challenging even for fairly simple Markov chains. Already for the one-dimensional Ising model, showing cutoff is a longstanding open problem. We settle the above by establishing cutoff and its location at the high temperature regime of the Ising model on the lattice with periodic boundary conditions. Our results hold for any dimension and at any temperature where there is strong spatial mixing: For ?² this carries all the way to the critical temperature. Specifically, for fixed d≥1, the continuous-time Glauber dynamics for the Ising model on (?/n?) ^d with periodic boundary conditions has cutoff at (d/2λ _∞)logn, where λ _∞ is the spectral gap of the dynamics on the infinite-volume lattice. To our knowledge, this is the first time where cutoff is shown for a Markov chain where even understanding its stationary distribution is limited. The proof hinges on a new technique for translating L ¹-mixing to L ²-mixing of projections of the chain, which enables the application of logarithmic-Sobolev inequalities. The technique is general and carries to other monotone and anti-monotone spin-systems, e.g. gas hard-core, Potts, anti-ferromagentic Ising, arbitrary boundary conditions, etc.