Optimal quadratures for analytic functions

For integrals _–1 ¹ w(x)f(x)dx with and with analytic integrands, we consider the determination of optimal abscissasx _i ^o and weightsA _i ^o , for a fixedn, which minimize the errorE _n (f)= _–1 ¹ w(x)f(x)dx – _i ⁼¹ⁿ A _i f(x _i ) over an appropriate Hilbert spaceH ²(E ; w(z)) of analytic functions. Simultaneously, we consider the simpler problem of determining intermediate-optimal weightsA _i *, corresponding to (preassigned) Gaussian abscissasx _i ^G , which minimize the quadrature error. For eachw(x), the intermediate-optimal weightsA _i * are obtained explicitly, and these come out proportional to the corresponding Gaussian weightsA _i ^G . In each case,A _i ^G =A _i *+O( ^–4n ), . For , a complete explicit solution for optimal abscissas and weights is given; in fact, the set {x _i ^G ,A _i *;i=1,...,n} to provides the optimal abscissas and weights. For otherw(x), we study the closeness of the set {x _i ^G ,A _i *;i=1,...,n} to the optimal solution {x _i ^o ,A _i ^o ;i=1,...,n} in terms of _n (), the maximum absolute remainder in the second set ofn normal equations. In each case, _n () is, at least, of the order of ^–4n for large.     

Ergodic properties of Poisson processes with almost periodic intensity

Summary We discuss in this paper a non-homogeneous Poisson process A driven by an almost periodic intensity function. We give the stationary version A ^* and the Palm version A ⁰ corresponding to A ^*. Let (T _i ,i) be the inter-point distance sequence in A and (T _i ⁰ ,i) in A ⁰. We prove that forj, the sequence (T _i+j,i) converges in distribution to (T _i ⁰ ,i). If the intensity function is periodic then the convergence is in variation.     

Numerical stability of descent methods for solving linear equations

Summary In this paper we perform a round-off error analysis of descent methods for solving a liner systemAx=b, whereA is supposed to be symmetric and positive definite. This leads to a general result on the attainable accuracy of the computed sequence {x _i } when the method is performed in floating point arithmetic. The general theory is applied to the Gauss-Southwell method and the gradient method. Both methods appear to be well-behaved which means that these methods compute an approximationx _i to the exact solutionA ^–1 b which is the exact solution of a slightly perturbed linear system, i.e. (A+A)x _i =b, A of order A, where is the relative machine precision and · denotes the spectral norm.     

Numerical computation of polynomial zeros by means of Aberth's method

An algorithm for computing polynomial zeros, based on Aberth's method, is presented. The starting approximations are chosen by means of a suitable application of Rouché's theorem. More precisely, an integerq 1 and a set of annuliA _i,i=1,...,q, in the complex plane, are determined together with the numberk _i of zeros of the polynomial contained in each annulusA _i. As starting approximations we choosek _i complex numbers lying on a suitable circle contained in the annulusA _i, fori=1,...,q. The computation of Newton's correction is performed in such a way that overflow situations are removed. A suitable stop condition, based on a rigorous backward rounding error analysis, guarantees that the computed approximations are the exact zeros of a nearby polynomial. This implies the backward stability of our algorithm. We provide a Fortran 77 implementation of the algorithm which is robust against overflow and allows us to deal with polynomials of any degree, not necessarily monic, whose zeros and coefficients are representable as floating point numbers. In all the tests performed with more than 1000 polynomials having degrees from 10 up to 25,600 and randomly generated coefficients, the Fortran 77 implementation of our algorithm computed approximations to all the zeros within the relative precision allowed by the classical conditioning theorems with 11.1 average iterations. In the worst case the number of iterations needed has been at most 17. Comparisons with available public domain software and with the algorithm PA16AD of Harwell are performed and show the effectiveness of our approach. A multiprecision implementation in MATHEMATICA is presented together with the results of the numerical tests performed.Work performed under the support of the ESPRIT BRA project 6846 POSSO (POlynomial System SOlving).     

An Invariance Principle for Triangular Arrays

Let A _{n, i} be a triangular array of sign-symmetric exchangeable random variables satisfying nE(A ² _{n, i} )1, nE(A ⁴ _{n, i} )0, n ² E(A ² _{n, 1} A ² _{n, 2})1. We show that ^[nt] _i=1 A _ni, 0t1, converges to Brownian motion. This is applied to show that if A is chosen from the uniform distribution on the orthogonal group O _n and X _n(t)=^[nt] _i=1 A _ii, then X _n converges to Brownian motion. Similar results hold for the unitary group.     

Some localized separation axioms and their implications

In a topological spaceX, a T₂-distinct pointx means that for anyyX xy, there exist disjoint open neighbourhoods ofx andy. Similarly, T₀-distinct points and T₁distinct points are defined. In a T_i-distinct point-setA, we assume that eachxA is a T _i -distinct point (i=0, 1, 2). In the present paper some implications of these notions which localize the T _i -separation axioms (i=0, 1, 2) requirement, are studied. Suitable variants of regularity and normality in terms of T₂-distinct points are shown hold in a paracompact space (without the assumption of any separation axioms). Later T₀-distinct points are used to give two characterizations of the R _D -axiom.¹ In the end, some simple results are presented including a condition under which an almost compact set is closed and a result regarding two continuous functions from a topological space into a Hausdorff space is sharpened. A result which relates a limit pointv to an -limit point is stated.     

Characterizations of Steiner points

To each convex compact A in Euclidian space Eⁿ there corresponds a point S (A) from Eⁿ such that 1) S(x) = x for x Eⁿ, 2) S(A + B) = S(A) + S(B), 3) S (A_i) , if A_i converges in the Hausdorff metric to the unit sphere in Eⁿ, then S(A) is the Steiner point of the set A. The theorem improves certain earlier results on characterizations of the Steiner point.Translated from Matematicheskie Zametki, Vol. 14, No. 2, pp. 243–247, August, 1973.In conclusion, I wish to express my appreciation to E. M. Semenov for his constant help with this work.     

The Smallest Parallelepiped of n Random Points and Peeling

Let n random points be given with uniform distribution in the d-dimensional unit cube [0,1]^d. The smallest parallelepiped A which includes all the n random points is dealt with. We investigate the asymptotic behavior of the volume of A as n tends to . Using a point process approach, we derive also the asymptotic behavior of the volumes of the k-th smallest parallelepipeds A _n ^(k) which are defined by iteration. Let A _n = A _n ⁽¹⁾ . Given A _n ^(k,-,1) delete the random points X _i which are on the boundary A _n ^(k,-,1) , and construct the smallest parallelepiped which includes the inner points of A _n ^(k,-,1) , this defines A _n ^(k) . This procedure is known as peeling of the parallelepiped A_n.     

Inequalities for two set systems with prescribed intersections

Inequalities are presented for systems {(A _i ,B _i ):1 i m} of pairs of finite sets satisfyingA _i B _i = andA _i B _j orA _j B _i fori j.     

A note on "More Operator Versions of the Schwarz Inequality"

It is shown that for any (n + 1)-positive (possibly non-linear) map and any bounded linear operators A _i ,i = 1,¨,n we have [(A _i ^* A _j )] _{i,j = 1} ^*[(A _i )^*(A _j )] _{i,j = 1} ^*, and that the statement is false if "(n + 1)-positive" is replaced by "n-positive". This resolves an issue raised by Bhatia and Davis in relation to a Schwartz inequality which can be regarded as a non-commutative variance-covariance inequality [2]     

Nonabelian K-theory: The nilpotent class of K1 and general stability

A functorial filtration GL _n =S^–1L _n S⁰L _n S ⁱ L _n E _n of the general linear group GL _{n, n} 3, is defined and it is shown for any algebra A, which is a direct limit of module finite algebras, that S^–1 L _n (A)/S⁰L _n (A) is abelian, that S⁰L _n (A) S¹L _n (A) is a descending central series, and that S ⁱ L _n (A) = E _n(A) whenever i the Bass-Serre dimension of A. In particular, the K-functors k ₁ S ⁱ L _n =S ⁱ L _n /E _n are nilpotent for all i 0 over algebras of finite Bass-Serre dimension. Furthermore, without dimension assumptions, the canonical homomorphism S ⁱ L _n (A)/S ⁱ⁺¹ L _n (A)S ⁱ L _{n+ 1}(A)/S ⁱ⁺¹ L _{n + 1} (A) is injective whenever n i + 3, so that one has stability results without stability conditions, and if A is commutative then S⁰L _n (A) agrees with the special linear group SL _n (A), so that the functor S⁰L _n generalizes the functor SL _n to noncommutative rings. Applying the above to subgroups H of GL _n (A), which are normalized by E _n(A), one obtains that each is contained in a sandwich GL _n (A, ) H E _n(A, ) for a unique two-sided ideal of A and there is a descending S⁰L _n (A)-central series GL _n (A, ) S⁰L _n (A, ) S¹L _n (A, ) S ⁱ L _n (A, ) E _n(A, ) such that S ⁱ L _n (A, )=E _n(A, ) whenever i Bass-Serre dimension of A.Dedicated to Alexander Grothendieck on his sixtieth birthday     

Regular solutions of transmission and interaction problems for wave equations

Consider n bounded domains Ω ? ? and elliptic formally symmetric differential operators A₁ of second order on Ω_i Choose any closed subspace V in $ \prod\limits_{i = 1}^n {L^2 \left({\Omega _i } \right)} $, and extend (A_i)_i=1,…,n by Friedrich's theorem to a self-adjoint operator A with D(A^1/2) = V (interaction operator). We give asymptotic estimates for the eigenvalues of A and consider wave equations with interaction. With this concept, we solve a large class of problems including interface problems and transmission problems on ramified spaces.^25,32 We also treat non-linear interaction, using a theorem of Minty²⁹.     

Extremal problems for linear orders on [n] p

Let be a product order on [n] ^p i.e. for A, B [n] ^p , 1a ₁<a ₂<...<a _p º-n and 1<-b ₁<b ₂<...<b _p <-n we have AB iff a _i<-b _i for all i=1, 2,..., p. For a linear extension < of (ordering [n] ^p as ) let F _< ^[n],p (m) count the number of A _i 's, i<-m such that 1A _i. Clearly, for every m and <, where <l denotes the lexicographic order on [n] ^p . In this note we prove that the colexicographical order, <c, provides a corresponding lower bound i.e. that holds for any linear extension < of .This project together with [2] was initiated by the first author and continued in colaboration with the second author. After the death of the first author the work was continued and finalized by the second and the third author.Research supported by NSF grant DMS 9011850.     

Facets of the clique partitioning polytope

A subsetA of the edge set of a graphG = (V, E) is called a clique partitioning ofG is there is a partition of the node setV into disjoint setsW ¹,,W ^k such that eachW _i induces a clique, i.e., a complete (but not necessarily maximal) subgraph ofG, and such thatA = _i=1 ^k 1{uv|u, v W _i ,u v}. Given weightsw ^e for alle E, the clique partitioning problem is to find a clique partitioningA ofG such that _eA w _e is as small as possible. This problem—known to be-hard, see Wakabayashi (1986)—comes up, for instance, in data analysis, and here, the underlying graphG is typically a complete graph. In this paper we study the clique partitioning polytope of the complete graphK _n , i.e., is the convex hull of the incidence vectors of the clique partitionings ofK _n . We show that triangles, 2-chorded odd cycles, 2-chorded even wheels and other subgraphs ofK _n induce facets of. The theoretical results described here have been used to design an (empirically) efficient cutting plane algorithm with which large (real-world) instances of the clique partitioning problem could be solved. These computational results can be found in Grötschel and Wakabayashi (1989).     

Stability of the C *-Algebra Associated with Twisted CCR

The universal enveloping C ^*-algebra A of twisted canonical commutation relations is considered. It is shown that, for any (–1,1), the C ^*-algebra A is isomorphic to the C ^*-algebra A ₀ generated by partial isometries t _i ,t _i ^*,i=1,¨,d satisfying the relations t _i ^* t _j = _ij (1– _k<i t _k t _k ^*), t _j t _i =0, ij and it is proved that the Fock representation of A is faithful.     

Counting Sets With Small Sumset, And The Clique Number Of Random Cayley Graphs

Given a set A /N we may form a Cayley sum graph G _A on vertex set /N by joining i to j if and only if i+j A. We investigate the extent to which performing this construction with a random set A simulates the generation of a random graph, proving that the clique number of G _A is almost surely O(logN). This shows that Cayley sum graphs can furnish good examples of Ramsey graphs. To prove this result we must study the specific structure of set addition on /N. Indeed, we also show that the clique number of a random Cayley sum graph on =(/2) ⁿ is almost surely not O(log ||).* Supported by a grant from the Engineering and Physical Sciences Research Council of the UK and a Fellowship of Trinity College Cambridge.     

Semi-groupes sous-Markoviens engendrés par des opérateurs matriciels

We characterize generators of sub-Markovian semigroups onL ^p () by a version of Kato's inequality. This will be used to show (under precise assumptions) that the semigroup generated by a matrix operatorA=(A _ij )_1i,jn on (L ^p ()) ⁿ is sub-Markovian if and only if the semigroup generated by the sum of each rowA _i 1+...+A _in (1in), is sub-Markovian. The corresponding result on (C ₀(X)) ⁿ characterizes dissipative operator matrices.

     

Edge-isoperimetric inequalities in the grid

The grid graph is the graph on [k] ⁿ ={0,...,k–1} ⁿ in whichx=(x _i ) ₁ ⁿ is joined toy=(y _i ) ₁ ⁿ if for somei we have |x _i –y _i |=1 andx _j =y _j for allji. In this paper we give a lower bound for the number of edges between a subset of [k] ⁿ of given cardinality and its complement. The bound we obtain is essentially best possible. In particular, we show that ifA[k] ⁿ satisfiesk ⁿ /4|A|3k ⁿ /4 then there are at leastk ^n–1 edges betweenA and its complement.Our result is apparently the first example of an isoperimetric inequality for which the extremal sets do not form a nested family.We also give a best possible upper bound for the number of edges spanned by a subset of [k] ⁿ of given cardinality. In particular, forr=1,...,k we show that ifA[k] ⁿ satisfies |A|r ⁿ then the subgraph of [k] ⁿ induced byA has average degree at most 2n(1–1/r).Research partially supported by NSF Grant DMS-8806097     

Generalized Eulerian numbers and the topology of the Hessenberg variety of a matrix

Let Agl(n, C) and let p be a positive integer. The Hessenberg variety of degree p for A is the subvariety Hess(p, A) of the complete flag manifold consisting of those flags S ₁ S _n–1 in ⁿ which satisfy the condition AS _i S _i+p ,for all i. We show that if A has distinct eigenvalues, then Hess(p, A) is smooth and connected. The odd Betti numbers of Hess(p, A) vanish, while the even Betti numbers are given by a natural generalization of the Eulerian numbers. In the case where the eigenvalues of A have distinct moduli, |₁|<<|₁|, these results are applied to determine the dimension and topology of the submanifold of U(n) consisting of those unitary matrices P for which A ₀=P ^-1 AP is in Hessenberg form and for which the diagonal entries of the QR-iteration initialized at A ₀ converge to a given permutation of ₁,_n.Research partially supported by the National Science Foundation under Grant ECS-8696108.     

Solution of an extremal problem for sets using resultants of polynomials

A new, short proof is given of the following theorem of Bollobás: LetA ₁,..., A_h andB ₁,..., B_h be collections of sets with _i ¦A _i¦=r,¦B_i¦=s and ¦A _iB_j¦=Ø if and only ifi=j, thenh( _s ^r+s ). The proof immediately extends to the generalizations of this theorem obtained by Frankl, Alon and others.