A fast algorithm for scalar Nevanlinna-Pick interpolation

Summary In this paper, we derive a fast algorithm for the scalar Nevanlinna-Pick interpolation. Givenn distinct pointsz _i in the unit disk |z|<1 andn complex numbersw _i satisfying the Pick condition for 1in, the new Nevanlinna-Pick interpolation algorithm requires onlyO(n) arithmetic operations to evaluate the interpolatory rational function at a particular value ofz, in contrast to the classical algorithm which requiresO(n ²) arithmetic operations to compute the so-called Fenyves array (which is inherent in the classical algorithm). The new algorithm bypasses the generation of the Fenyves array to speed up the computation, and also yields a parallel scheme requiring onlyO(logn) arithmetic operations on a concurrent-read, exclusive-write parallel random access machine withn processors. We must remark that the rational functionf(z) computed by the new algorithm is one degree higher than the function computed by the classical algorithm.Supported in part by the US Army Research Office Grant No. DAAL03-91-G-0106     

Type II Hermite�CPad�� Approximations of Generalized Hypergeometric Series

We shall present short proofs for type II (simultaneous) Hermite–Padé approximations of the generalized hypergeometric and q-hypergeometric series

An extremal set theoretical characterization of some steiner systems

Letn, k, t be integers,n>k>t≧0, and letm(n, k, t) denote the maximum number of sets, in a family ofk-subsets of ann-set, no two of which intersect in exactlyt elements. The problem of determiningm(n, k, t) was raised by Erdős in 1975. In the present paper we prove that ifk≦2t+1 andk−t is a prime, thenm(n, k, t)≦( _t ⁿ )( _k ^2k-t-1 )/( _t ^2k-t-1 ). Moreover, equality holds if and only if an (n, 2k−t−1,t)-Steiner system exists. The proof uses a linear algebraic approach.     

On Hankel Nonnegative Definite Sequences, the Canonical Hankel Parametrization, and Orthogonal Matrix Polynomials

This paper continues recent investigations started in Dyukarev et al. (Complex anal oper theory 3(4):759–834, 2009) into the structure of the set H_q,2n ³ {\mathcal{H}_{q,2n}^{\ge}} of all Hankel nonnegative definite sequences, (s_j)_j=0²ⁿ{(s_{j})_{j=0}^{2n}}, of complex q × q matrices and its important subclasses H_q,2n ^{3 ,e}{\mathcal{H}_{q,2n}^{\ge,{\rm e}}} and ${\mathcal{H}_{q,2n}^>}${\mathcal{H}_{q,2n}^>} of all Hankel nonnegative definite extendable sequences and of all Hankel positive definite sequences, respectively. These classes of sequences arise quite naturally in the framework of matrix versions of the truncated Hamburger moment problem. In Dyukarev et al. (Complex anal oper theory 3(4):759–834, 2009) a canonical Hankel parametrization [(C_k)_k=1ⁿ, (D_k)_k=0ⁿ]{[(C_k)_{k=1}^n, (D_k)_{k=0}^n]} consisting of two sequences of complex q × q matrices was associated with an arbitrary sequence (s_j)_j=0²ⁿ{(s_{j})_{j=0}^{2n}} of complex q × q matrices. The sequences belonging to each of the classes H_q,2n ³ , H_q,2n ^{3 ,e}{\mathcal{H}_{q,2n}^{\ge}, \mathcal{H}_{q,2n}^{\ge,{\rm e}}}, and ${\mathcal{H}_{q,2n}^>}${\mathcal{H}_{q,2n}^>} were characterized in terms of their canonical Hankel parametrization (see, Dyukarev et al. in Complex anal oper theory 3(4):759–834, 2009; Proposition 2.30). In this paper, we will study further aspects of the canonical Hankel parametrization. Using the canonical Hankel parametrization [(C_k)_k=1ⁿ, (D_k)_k=0ⁿ]{[(C_k)_{k=1}^n, (D_k)_{k=0}^n]} of a sequence (s_j)_j=0²ⁿ ? H_q,2n ³ {(s_{j})_{j=0}^{2n} \in \mathcal{H}_{q,2n}^{\ge}}, we give a recursive construction of a monic right (resp. left) orthogonal system of matrix polynomials with respect to (s_j)_j=0²ⁿ{(s_{j})_{j=0}^{2n}} (see Theorem 5.5). The matrices [(C_k)_k=1ⁿ, (D_k)_k=0ⁿ]{[(C_k)_{k=1}^n, (D_k)_{k=0}^n]} will be expressed in terms of an arbitrary monic right (resp. left) orthogonal system with respect to (s_j)_j=0²ⁿ{(s_{j})_{j=0}^{2n}} (see Theorem 5.11). This result will be reformulated in terms of nonnegative Hermitian Borel measures on \mathbbR{\mathbb{R}}. In this way, integral representations for the matrices [(C_k)_k=1ⁿ, (D_k)_k=0ⁿ]{[(C_k)_{k=1}^n, (D_k)_{k=0}^n]} will be obtained (see Theorem 6.9). Starting from the monic orthogonal polynomials with respect to some classical probability distributions on \mathbbR{\mathbb{R}}, Theorem 6.9 is used to compute the canonical Hankel parametrization of their moment sequences. Moreover, we discuss important number sequences from enumerative combinatorics using the canonical Hankel parametrization.     

A convexity-preservingC 2 parametric rational cubic interpolation

Summary AC ² parametric rational cubic interpolantr(t)=x(t) i+y(t) j,t[t ₁,t _n] to data S={(x_j, y_j)|j=1,...,n} is defined in terms of non-negative tension parameters _j ,j=1,...,n–1. LetP be the polygonal line defined by the directed line segments joining the points (x _j ,y _j ),t=1,...,n. Sufficient conditions are derived which ensure thatr(t) is a strictly convex function on strictly left/right winding polygonal line segmentsP. It is then proved that there always exist _j ,j=1,...,n–1 for whichr(t) preserves the local left/righ winding properties of any polygonal lineP. An example application is discussed.This research was supported in part by the natural Sciences and Engineering Research Council of Canada.     

Non-uniform Turán-type problems

Given positive integers n,k,t, with 2?k?n, and t<2^k, let m(n,k,t) be the minimum size of a family F of (nonempty distinct) subsets of [n] such that every k-subset of [n] contains at least t members of F, and every (k-1)-subset of [n] contains at most t-1 members of F. For fixed k and t, we determine the order of magnitude of m(n,k,t). We also consider related Turán numbers T_?r(n,k,t) and T_r(n,k,t), where T_?r(n,k,t) (T_r(n,k,t)) denotes the minimum size of a family such that every k-subset of [n] contains at least t members of F. We prove that T_?r(n,k,t)=(1+o(1))T_r(n,k,t) for fixed r,k,t with and n→∞.     

Asymptotic results on infinite tandem queueing networks

We consider an infinite tandem queueing network consisting of ·/GI/1/∞ stations with i.i.d. service times. We investigate the asymptotic behavior of t(n, k), the inter-arrival times between customers n and n + 1 at station k, and that of w(n, k), the waiting time of customer n at station k. We establish a duality property by which w(n, k) and the “idle times”y(n, k) play symmetrical roles. This duality structure, interesting by itself, is also instrumental in proving some of the ergodic results. We consider two versions of the model: the quadrant and the half-plane. In the quadrant version, the sequences of boundary conditions {w(0,k), k∈ℕ} and {t(n, 0), n∈ℕ}, are given. In the half-plane version, the sequence {t(n, 0), n∈ℕ} is given. Under appropriate assumptions on the boundary conditions and on the services, we obtain ergodic results for both versions of the model. For the quadrant version, we prove the existence of temporally ergodic evolutions and of spatially ergodic ones. Furthermore, the process {t(n, k), n∈ℕ} converges weakly with k to a limiting distribution, which is invariant for the queueing operator. In the more difficult half plane problem, the aim is to obtain evolutions which are both temporally and spatially ergodic. We prove that 1/n∑ _k=1 ⁿ w(0, k) converges almost surely and in L ₁ to a finite constant. This constitutes a first step in trying to prove that {t(n,k), n∈ℤ} converges weakly with k to an invariant limiting distribution. Received: 23 March 1999 / Revised version: 5 January 2000 / Published online: 12 October 2000     

Product integration of logarithmic singular integrands based on cubic splines

This paper is concerned with the practical evaluation of the product integral ∫¹_{? 1}f(x)k(x)dx for the case when k(x) = In|x - λ|, λ? (?1, +1) and f is bounded in [?1, +1]. The approximation is a quadrature rule

where the weights {w_n,n,i} are chosen to be exact when f is given by a linear combination of a chosen set of functions {φ_n,j}. In this paper the functions {φ_n,j} are chosen to be cubic B-splines. An error bound for product quadrature rules based on cubic splines is provided. Examples that test the performance of the product quadrature rules for different choices of the function are given. A comparison is made with product quadrature rules based on first kind Chebyshev polynomials.     

Some nodes matrices appearing in the numerical analysis for singular integral equations

Let {p _m (w)} be the sequence of Jacobi polynomials corresponding to the weightw(x)=(1–x)(1+x), 0, <1. denote=">x _k (w)=cos _m,k (w),k=1,...,m, the zeros ofp _m (w). If +=0, then the estimates

On a Turán type problem of Erdös

Let L ^k be the graph formed by the lowest three levels of the Boolean lattice B _k , i.e.,V(L ^k )={0, 1,...,k, 12, 13,..., (k–1)k} and 0is connected toi for all 1ik, andij is connected toi andj (1i<jk).It is proved that if a graph G overn vertices has at leastk ^3/2 n ^3/2 edges, then it contains a copy of L ^k .Research supported in part by the Hungarian National Science Foundation under Grant No. 1812     

Q-Splines

The classical weighted spline introduced by Ph. Cinquin (1981), (see also K. Salkauskas (1984) and T.A. Foley (1986)) consists in minimizing _a ^b w(t)(x(t))² dt under the conditionsx(t _i )=y _i ,i=1,...,n, where the functionw is piecewise constant on the subdivisiona<t ₁<t ₂<...<t _n <b. The solution is a cubic spline, but it is notC ². We consider here the minimization of

Remarks on Taylor Series Expansions and Conditional Expectations for Stratonovich SDEs with Complete V‐Commutativity

Abstract

It may happen that there is not a finite maximum order bound for numerical approximations of stochastic processes X = (X _t : 0 ≤ t ≤ T) satisfying Stratonovich stochastic differential equations (SDEs) with some commutative structure along an appropriate functional V(t, X _t ). This statement can be proven with respect to the concept of mean square convergence under the assumption of “infinite smoothness” of drift a(t, x) and diffusion coefficients b ^j (t, x) and with finite initial second moments. As a result, we obtain an infinite series expansion of the conditional expectation 𝔼[V(t, X _t )|? _t ^N ] on any fixed finite time interval [0, T], provided that the information is collected by discretized σ‐field ? _T ^N  = σ{W _{t 0} , W _{t 1} , …, W _{t N?1} , W _T } at N + 1 given time instants t _i  ∈ [0, T] with t ₀ ≤ t ₁ ≤ ··· ≤ t _N?1 ≤ t _N  = T.     

Some intriguing upper bounds for separating hash families

An N ×n matrix on q symbols is called {w_1,...,w_t}-separating if for arbitrary t pairwise disjoint column sets C_1,..., C_t with |C_i|=w_i for 1 ≤i≤t, there exists a row f such that f(C_1),...,f(C_t) are also pairwise disjoint, where f(C_i) denotes the collection of componentn of C_i restricted to row f. Given integers N, q and w_1,...,w_t, denote by C(N,q,{w_1,...,w_t}) the maximal a such that a corresponding matrix does exist.The determination of C(N,q,{w_1,...,w_t}) has received remarkable attention during the recent years. The main purpose of this paper is to introduce two novel methodologies to attack the upper bound of C(N, q, {w_1,...,w_t}).The first one is a combination of the famous graph removal lemma in extremal graph theory and a Johnson-type recursive inequality in coding theory, and the second onc is the probabilistic method. As a consequence, we obtain several intriguing upper bounds for some parameters of C(N,q,{w_1,...,w_t}), which significantly improve the previously known results.     

A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs

The scheduling problem 1|pmtn, r _j |w _j U _j calls forn jobs with arbitrary release dates and due dates to be preemptively scheduled for processing by a single machine, with the objective of minimizing the sum of the weights of the late jobs. A dynamic programming algorithm for this problem is described. Time and space bounds for the algorithm are, respectively,O(nk ² W ²) andO(k ² W), wherek is the number of distinct release dates andW is the sum of the integer job weights. Thus, for the problem 1|pmtn, r _j |U _j , in which the objective is simply to minimize the number of late jobs, the pseudopolynomial time bound becomes polynomial, i.e.O(n ³ k ²).     

The Cardinality of Sets of <Emphasis Type="Italic">k</Emphasis>-Independent Vectors over Finite Fields

A set of vectors is k-independent if all its subsets with no more than k elements are linearly independent. We obtain a result concerning the maximal possible cardinality Ind _q (n, k) of a k-independent set of vectors in the n-dimensional vector space F _q ⁿ over the finite field F _q of order q. Namely, we give a necessary and sufficient condition for Ind _q (n, k) = n + 1. We conclude with some pertinent remarks re applications of our results to codes, graphs and hypercubes. Supported, in part by grants EP/C000285, NSF-DMS-0439734 and NSF-DMS-0555839. S. B. Damelin thanks the Institute for Mathematics and Applications for their hospitality.     

Essential self-adjointness of Schrödinger-type operators

The essential self-adjointness of the strongly elliptic operator L = ∑_j,k=1ⁿ (?_j ? ib_j(x)) a_jk(x)(?_k ? ib_k(x)) + q(x) acting on C₀^∞(Rⁿ) is considered, where the matrix (a_jk) is real and symmetric, b_j and q are real, a_jk and b_j are sufficiently smooth, and q?L_loc². It has been shown by Ural'ceva and also Laptev that if q is bounded below and n ? 3 the minimal operator may not be self-adjoint if the principal coefficients rise too rapidly. Thus a theorem of Weyl for ordinary differential operators does not extend to partial differential operators. In this paper it is shown that if q is bounded below and if the principal coefficients are “well behaved” within a sequence of closed shells which go to infinity, then the minimal operator is self-adjoint. It is also shown that a number of results which were known to be true when q is sufficiently smooth may be extended to include the case where q?L_loc². The principal tools used are a distribution inequality due to Tosio Kato and a general maximum principle due to Walter Littman.     

Fluctuations of the empirical quantiles of independent Brownian motions

We consider iid Brownian motions, B_j(t), where B_j(0) has a rapidly decreasing, smooth density function f. The empirical quantiles, or pointwise order statistics, are denoted by B_j:n(t), and we consider a sequence Q_n(t)=B_j(n):n(t), where j(n)/n→α∈(0,1). This sequence converges in probability to q(t), the α-quantile of the law of B_j(t). We first show convergence in law in C[0,∞) of F_n=n^1/2(Q_n−q). We then investigate properties of the limit process F, including its local covariance structure, and Hölder-continuity and variations of its sample paths. In particular, we find that F has the same local properties as fBm with Hurst parameter H=1/4.     

A generalized numerical range: the range of a constrained sesquilinear form

Let M_n denote the algebra of all nxn complex matrices. For a given q?C with ∣Q∣≤1, we define and denote the q-numerical range of A?M_n by

W_q (A)={x ^? Ay:x,y?C ⁿ , _{x ^? x?y ^? y=1,x ^? y=q} }

The q-numerical radius is then given by r_q (A)=sup{∣z∣:z?W _q (A)}. When q=1,W _q (A) and r _q (A) reduce to the classical numerical range of A and the classical numerical radius of A, respectively. when q≠0, another interesting quantity associated with W _q (A) is the inner q-numerical radius defined by [rtilde] _q (A)=inf{∣z∣:z?W _q (A)}

In this paper, we describe some basic properties of W _q (A), extending known results on the classical numerical range. We also study the properties of r_q considered as a norm (seminorm if q=0) on M_n .Finally, we characterize those linear operators L on M_n that leave W_q ,r_q of [rtilde]_q invariant. Extension of some of our results to the infinite dimensional case is discussed, and open problems are mentioned.     

Van der waerden and ramsey type games

Let us consider the following 2-player game, calledvan der Waerden game. The players alternately pick previously unpicked integers of the interval {1, 2, ...,N}. The first player wins if he has selected all members of ann-term arithmetic progression. LetW*(n) be the least integerN so that the first player has a winning strategy. By theRamsey game on k-tuples we shall mean a 2-player game where the players alternately pick previously unpicked elements of the completek-uniform hypergraph ofN verticesK _N ^k , and the first player wins if he has selected allk-tuples of ann-set. LetR _k*(n) be the least integerN so that the first player has a winning strategy. We prove (W* (n))¹/n → 2,R ₂*(n)<(2+ε) ⁿ andR _k ^* n<2 ^nk / ^k! fork ≧3.