On the enumeration of chains in regular chain-groups

Let N be a regular chain-group on E (see W. T. Tutte, Canad. J. Math.8 (1956), 13–28); for instance, N may be the group of integer flows or tensions of a directed graph with edge-set E). It is known that the number of proper Z_λ-chains of N (λ ∈ Z, λ ≥ 2) is given by a polynomial in λ, P(N, λ) (when N is the chain-group of integer tensions of the connected graph G, λP(N, λ) is the usual chromatic polynomial of G). We prove the formula: P(N, λ) = Σ_{[E′]∈O(N)⁺/～}Q(R_[E′](N), λ), where O(N)⁺ is the set of orientations of N with a proper positive chain, ～ is a simple equivalence relation on O(N)⁺ (sequence of reversals of positive primitive chains), and Q(R_[E′](N), λ) is the number of chains with values in [1, λ ? 1] in any reorientation of N associated to an element of [E′]. Moreover, each term Q(R_[E′](N), λ) is a polynomial in λ. As applications we obtain: P(N, 0) = (?1)^r(N)∥O(N)⁺/～∥; P(N, ?1) = (?1)^r(N)∥O(N)⁺∥ (a result first proved by Brylawski and Lucas); P(N, λ + 1) ≥ P(N, λ) for λ ≥ 2, λ ∈ Z. Our result can also be considered as a refinement of the following known fact: A regular chain-group N has a proper Z_λ-chain iff it has a proper chain in [?λ + 1, λ ? 1].     

A uniformly convergent continuous-discontinuous Galerkin method for singularly perturbed problems of convection-diffusion type

In this paper, we introduce a coupled approach of local discontinuous Galerkin and standard finite element method for solving singularly perturbed convection-diffusion problems. On Shishkin mesh with linear elements, a rate O(N^-1lnN) in an associated norm is established, where N is the number of elements. Numerical experiments complement the theoretical results. Moreover, a rate O(N^-2ln²N) in a discrete L^∞ norm, and O(N^-2) in L² norm, are observed numerically on the Shishkin mesh.     

The kernel of the sum of two cooperative games

A sum of two gamesG ¹=(N ¹,v ¹) andG ²=(N ²,v ²) with disjoint sets of players is defined to be a gameG=(N, v), whereN=N ¹ ∪N ² andv (S)=max {v ¹ (S ∩N ¹),v ² (S ∩N ²)}. The kernel of the sum of two games is given in terms of the parts of kernels of the modified component games. The sum of games from certain classes is considered. When the components of the sum are simple games one of the corollaries of the main theorem coincides with known results.     

Solution of Band Matrix Equations by Projection-Recurrence

The solution space of the matrix equation Hx=u is decomposed by a projection which leads to a recurrence for H^-1. For tridiagonal H it is shown that the elements of H^-1 can always be completely factorized. An explicit expression is obtained for H^-1 when H is tridiagonal with constant interior elements and arbitrary boundary elements. This result reduces to a particularly simple form when H is Toeplitz. For general N×N tridiagonal H, the maximum number of arithmetic operations to obtain any element of H^-1 is asymptotic to 6N, and to obtain H^-1 it is N²+14N. To obtain the vector x the number of operations ranges from 8N to 11N.     

Symmetric Monge–Kantorovich problems and polar decompositions of vector fields

We address the problem of whether a bounded measurable vector field from a bounded domain Ω into \({\mathbb{R}^d}\) is N-cyclically monotone up to a measure preserving N-involution, where N is any integer larger than 2. Our approach involves the solution of a multidimensional symmetric Monge–Kantorovich problem, which we first study in the case of a general cost function on a product domain Ω ^N . The polar decomposition described above corresponds to a special cost function derived from the vector field in question (actually N ? 1 of them). The problem amounts to showing that the supremum in the corresponding Monge–Kantorovich problem when restricted to those probability measures on Ω ^N which are invariant under cyclic permutations and with a given first marginal μ, is attained on a probability measure that is supported on a graph of the form x → (x, Sx, S ² x,..., S ^N-1 x), where S is a μ-measure preserving transformation on Ω such that S ^N  = I a.e. The proof exploits a remarkable duality between such involutions and those Hamiltonians that are N-cyclically antisymmetric.     

Rectangular Matrix Multiplication Revisited

We give a constant α > 0.294 and, for any ε > 0, an algorithm for multiplying anN×Nmatrix by anN×N^αmatrix with complexityO(N^{2 + ε}).     

Type III1 equilibrium states of the Toeplitz algebra of the affine semigroup over the natural numbers

We complete the analysis of KMS-states of the Toeplitz algebra T(N?N^×) of the affine semigroup over the natural numbers, recently studied by Raeburn and the first author, by showing that for every inverse temperature β in the critical interval 1?β?2, the unique KMSβ-state is of type III₁. We prove this by reducing the type classification from T(N?N^×) to that of the symmetric part of the Bost-Connes system, with a shift in inverse temperature. To carry out this reduction we first obtain a parametrization of the Nica spectrum of N?N^× in terms of an adelic space. Combining a characterization of traces on crossed products due to the second author with an analysis of the action of N?N^× on the Nica spectrum, we can also recover all the KMS-states of T(N?N^×) originally computed by Raeburn and the first author. Our computation sheds light on why there is a free transitive circle action on the extremal KMSβ-states for β>2 that does not ostensibly come from an action of T on the C^?-algebra.     

Necessary conditions for ɛ-uniform convergence of finite difference schemes for parabolic equations with moving boundary layers

A grid approximation of the boundary value problem for a singularly perturbed parabolic reaction-diffusion equation is considered in a domain with the boundaries moving along the axis x in the positive direction. For small values of the parameter ? (this is the coefficient of the higher order derivatives of the equation, ? ∈ (0, 1]), a moving boundary layer appears in a neighborhood of the left lateral boundary S ₁ ^L . In the case of stationary boundary layers, the classical finite difference schemes on piece-wise uniform grids condensing in the layers converge ?-uniformly at a rate of O(N ^?1lnN + N ₀), where N and N ₀ define the number of mesh points in x and t. For the problem examined in this paper, the classical finite difference schemes based on uniform grids converge only under the condition N ^?1 + N ₀ ^?1 ? ?. It turns out that, in the class of difference schemes on rectangular grids that are condensed in a neighborhood of S ₁ ^L with respect to x and t, the convergence under the condition N ^?1 + N ₀ ^?1 ≤ ?^1/2 cannot be achieved. Examination of widths that are similar to Kolmogorov’s widths makes it possible to establish necessary and sufficient conditions for the ?-uniform convergence of approximations of the solution to the boundary value problem. These conditions are used to design a scheme that converges ?-uniformly at a rate of O(N ^?1lnN + N ₀).     

A fourth order finite difference method for the Dirichlet biharmonic problem

Using the coupled approach, we formulate a fourth order finite difference scheme for the solution of the Dirichlet biharmonic problem on the unit square. On an N × N uniform partition of the square the scheme is solved at a cost O(N ² log₂ N)+m8N ² using fast Fourier transforms and m iterations of the preconditioned conjugate gradient method. Numerical tests confirm the fourth order accuracy of the scheme at the partition nodes with m proportional to log₂ N.     

Multivariate Jackson Inequality

By known multivariate versions of the classical Jackson theorem, every compact cube P in R^N admits Jackson’s inequality. The purpose of this note is to deliver other examples of Jackson sets in R^N. We shall show that a finite union of disjoint Jackson compact sets in R^N is also a Jackson set and that this in general fails to hold for an infinite union of Jackson sets. We also give a characterization of Jackson sets in the family of Markov compact sets in R^N which together with a Bierstone result permits one to show that Whitney regular compact subsets of R^N are Jackson.     

On the fast solution of a linear system arising in numerical conformal mapping

One step of the Newton method for the discretized Theodorsen equation in conformal mapping requires the solution of a certain 2N×2N system. Application of the Gaussian algorithm costs O(N³) arithmetic operations (a.o.). We present an algorithm which reduces the problem to the solution of three N×N linear Toeplitz systems. These systems can be solved in O(N log²N) a.o. This is also the amount of work required by the whole algorithm.     

The use of solutions on embedded grids for the approximation of singularly perturbed parabolic convection-diffusion equations on adapted grids

The Dirichlet problem on a closed interval for a parabolic convection-diffusion equation is considered. The higher order derivative is multiplied by a parameter ? taking arbitrary values in the semi-open interval (0, 1]. For the boundary value problem, a finite difference scheme on a posteriori adapted grids is constructed. The classical approximations of the equation on uniform grids in the main domain are used; in some subdomains, these grids are subjected to refinement to improve the grid solution. The subdomains in which the grid should be refined are determined using the difference of the grid solutions of intermediate problems solved on embedded grids. Special schemes on a posteriori piecewise uniform grids are constructed that make it possible to obtain approximate solutions that converge almost ?-uniformly, i.e., with an error that weakly depends on the parameter ?: |u(x, t) ? z(x, t)| ≤ M[N ₁ ^?1 ln² N ₁ + N ₀ ^?1 lnN ₀ + ?^?1 N ₁ ^?K ln ^K?1 N ₁], (x, t) ε ? _h , where N ₁ + 1 and N ₀ + 1 are the numbers of grid points in x and t, respectively; K is the number of refinement iterations (with respect to x) in the adapted grid; and M = M(K). Outside the σ-neighborhood of the outflow part of the boundary (in a neighborhood of the boundary layer), the scheme converges ?-uniformly at a rate O(N ₁ ^?1 ln² N ₁ + N ₀ ^?1 lnN ₀), where σ ≤ MN ₁ ^{?K + 1} ln ^K?1 N ₁ for K ≥ 2.     

On real moduli spaces of holomorphic bundles over M-curves

Let F be a genus g curve and σ:F→F a real structure with the maximal possible number of fixed circles. We study the real moduli space N^′=Fix(σ#) where σ#:N→N is the induced real structure on the moduli space N of stable holomorphic bundles of rank 2 over F with fixed non-trivial determinant. In particular, we calculate H^?(N^′,Z) in the case of g=2, generalizing Thaddeus' approach to computing H^?(N,Z).     

On sets of integers whose shifted products are powers

Let N be a positive integer and let A be a subset of {1,…,N} with the property that aa^′+1 is a pure power whenever a and a^′ are distinct elements of A. We prove that |A|, the cardinality of A, is not large. In particular, we show that |A|?(logN)^2/3(loglogN)^1/3.     

Minimal polynomials for compact sets of the complex plane

LetW _N(z)=a_Nz^N+... be a complex polynomial and letT _n be the classical Chebyshev polynomial. In this article it is shown that the polynomials (2a_N)^?n+1T_n(W_N), n ∈N, are minimal polynomials on all equipotential lines for {z∈C:|W _N(z)|≤1 Λ ImW _N(z)=0}     

Равносходимость разложений в кратный ряд и интеграл фурье, «прямоугольные частичные суммы» которых рассматриваются по некоторой подпоследовательности

In this paper we investigate the problem of the equiconvergence on T ^N = [-π, π) ^N of the expansions in multiple trigonometric series and Fourier integral of functions f ∈ L _p (T ^N ) and g ∈ L _p (? ^N ), where p > 1, N ≥ 3, g(x) = f(x) on T ^N , in the case when the “rectangular partial sums” of the indicated expansions, i.e.,– _n (x; f) and J _α(x; g), respectively, have indices n ∈ ? ^N and α ∈ ? ^N (n _j = [α _j ], j = 1,...,N, [t] is the integer part of t ∈ ?¹), in those certain components are the elements of “lacunary sequences”.     

Strong stability of a scheme on locally uniform meshes for a singularly perturbed ordinary differential convection-diffusion equation

The Dirichlet problem for a singularly perturbed ordinary differential convection-diffusion equation with a small parameter ? (? ?? (0, 1]) multiplying the higher order derivative is considered. For the problem, a difference scheme on locally uniform meshes is constructed that converges in the maximum norm conditionally, i.e., depending on the relation between the parameter ? and the value N defining the number of nodes in the mesh used; in particular, the scheme converges almost ?-uniformly (i.e., its accuracy depends weakly on ?). The stability of the scheme with respect to perturbations in the data and its conditioning are analyzed. The scheme is constructed using classical monotone approximations of the boundary value problem on a priori adapted grids, which are uniform on subdomains where the solution is improved. The boundaries of these subdomains are determined by a majorant of the singular component of the discrete solution. On locally uniform meshes, the difference scheme converges at a rate of O(min[?^?1 N ^?K lnN, 1] + N ^?1lnN), where K is a prescribed number of iterations for refining the discrete solution. The scheme converges almost ?-uniformly at a rate of O(N ^?1lnN) if N ^?1 ?? ?^??, where ?? (the defect of ?-uniform convergence) determines the required number K of iterations (K = K(??) ?? ??^?1) and can be chosen arbitrarily small from the half-open interval (0, 1]. The condition number of the difference scheme satisfies the bound ?? _P = O(?^?1/K ln^1/K ?^?1??^{?(K + 1)/K} ), where ?? is the accuracy of the solution of the scheme in the maximum norm in the absence of perturbations. For sufficiently large K, the scheme is almost ?-uniformly strongly stable.     

Remarks on a displacement-rank inversion method for Toeplitz systems

Comments are made regarding the implementation of a Toeplitz-matrix inversion algorithm described by Bitmead and Anderson in [1]. We show that although the algorithm is asymptotically efficient with O(N(logN)²) operations, it requires a 10⁶×10⁶ matrix to break even with the class of algorithms whose operation count is of the order of O(N²) (as found in [4]).     

Dynamic programming algorithms for picture comparison

Two-dimensional arrays can be compared by a generalization of dynamic programming algorithms for string comparison. Earlier algorithms have computational complexity O(N⁶) for comparison of two N × N arrays. The computational complexity is reduced to O(N⁴) in general and O(N²) algorithms are pointed out for the range limited case. An example is given to illustrate the lack of knowledge of mathematical properties of these algorithms. The problem of finding an algorithm to compute the minimum number of insertions, deletions, and substitutions to transform one array into another remains open.     

The Estermann cubic problem with almost equal summands

We prove an asymptotic formula for the number of representations of a sufficiently large natural number N as the sum of two primes p ₁ and p ₂ and the cube of a natural numbermsatisfying the conditions |p _i ? N/3| ≤ H, |m ³ ? N/3| ≤ H, H ≥ N ^5/6 ? ¹⁰.