A new algorithm for meromorphic Nevanlinna-Pick interpolation

Summary. Let D be be the open unit disc, H₀ the space of all bounded analytic functions in D and H_k the set of all functions of the form f(z)/(z–z₁)...(z–z_k) where z₁,...,z_k D and f H₀. Given {z₁,...,z_n},{w₁,...,w_n}, where z_i D,w_i and z_iz_j if ij, we show for 0kn–1, under certain assumptions, how to construct the unique interpolating function B_kH_k, B_k(z_j)=w_j, of minimal essential supremum norm on D by solving an eigenvalue problem defined by the interpolation data. The function B_k is a scaled quotient of two finite Blaschke products.Mathematics Subject Classification (2000): 65E05, 30D50, 30E05Acknowledgement We are very indebted to Professor Martin Gutknecht for pointing out the necessity of Assumption A and for providing us with a translation of [A]. Also valuable discussions with Professors Olof Staffans and Göran Högnäs are acknowledged. The research of the second named author was supported by the Academy of Finland Project 51906.     

拟圆周的两个几何性质

§1　IntroductionLetΓbe a Jordan curve of R2 and f∶R2→R2 be a k-quasiconformal mapping,where1≤k<+∞.Γis called a quasicirlce ifΓis the image of the unit circle B2 under f.It is well-known that quasicircles play a very important role in quasiconformalmapping theory,complex dynamics,Fuchsian groups,Teichmuller space theory and lowdimensional topology,( see[1—5] etc.)In1 963 ,Ahlfors obtained the three-point property of quasidisks[6] .Later,Gehring[7] ,Osgood[8] ,Krzyz[9] ,Ch…     

First boundary value problem in elasticity: Bounds for the displacements and Saint-Venant's principle

Summary We consider here the Dirichlet's problem for the Lamé's equations without body force in a semi-infinite cylinder (0z<) with cross-sectionS _z , the displacementsu _i vanishing on the cylindrical surface. We give in this paper an explicit decay estimate for aL ₂-norm ofu _i . The evaluation is of the type wherek ₁ andk ₂ are determined constants andI(f _i ) an integral depending only on the displacementsf _i prescribed onS ₀. Our results consequently reinforce the Saint-Venant's principle.

---

Résumé On considère ici le problème de Dirichlet pour les équations de Lamé sans force volumique dans un cylindre semi-infini (0z<) de section droiteS _z , les déplacementsu _i étant nuls sur la surface cylindrique. On donne dans ce travail une estimation explicite de la décroissance pour une norme (dansL ₂) desu _i . L'évaluation est du type oùk ₁ etk ₂ sont des constantes déterminées etI(f _i ) une intégrale ne dépendant que des déplacementsf _i imposés surS ₀. Notre résultat, par conséquent, renforce le principe de Saint-Venant.

     

Preemptive multiprocessor order scheduling to minimize total weighted flowtime

Consider m identical machines in parallel, each of which can produce k different product types. There is no setup cost when the machines switch from producing one product type to another. There are n orders each of which requests various quantities of the different product types. All orders are available for processing at time t = 0, and preemption is allowed. Order i has a weight w_i and its completion time is the time when its last requested product type finishes. Our goal is to find a preemptive schedule such that the total weighted completion time ∑_wiCi$\sum w_i{C}_i$ is minimized. We show that this problem is NP-hard even when all jobs have identical weights and there are only two machines. Motivated by the computational complexity of the problem, we propose a simple heuristic and show that it obeys a worst-case bound of 2 − 1/m. Finally, empirical studies show that our heuristic performs very well when compared with a lower bound of the optimal cost.     

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 ²).     

Optimal pairs of score vectors for positional scoring rules

Letw=(w ₁,,w _m ) andv=(v ₁,,v _m-1 ) be nonincreasing real vectors withw ₁>w _m andv ₁>v _m-1 . With respect to a lista ₁,,a _n of linear orders on a setA ofm3 elements, thew-score ofaA is the sum overi from 1 tom ofw _i times the number of orders in the list that ranka inith place; thev-score ofaA{b} is defined in a similar manner after a designated elementb is removed from everya _j .We are concerned with pairs (w, v) which maximize the probability that anaA with the greatestw-score also has the greatestv-score inA{b} whenb is randomly selected fromA{a}. Our model assumes that linear ordersa _j onA are independently selected according to the uniform distribution over them linear orders onA. It considers the limit probabilityP _m (w, v) forn that the element inA with the greatestw-score also has the greatestv-score inA{b}.It is shown thatP _m (m,v) takes on its maximum value if and only if bothw andv are linear, so thatw _i –w _i+1=w _i+1–w _i+2 forim–2, andv _i –v _i+1 =v _i+1 –v _i+2 forim–3. This general result for allm3 supplements related results for linear score vectors obtained previously form{3,4}.     

Robustness of positional scoring over subsets of alternatives

Positional score vectorsw=(w ₁,,w _m ) for anm-element setA, andv=(v ₁,,v _k ) for ak-element proper subsetB ofA, agree at a profiles of linear orders onA when the restriction toB of the ranking overA produced byw operating ons equals the ranking overB produced byv operating on the restriction ofs toB. Givenw ₁>w _mandv ₁>v _k , this paper examines the extent to which pairs of nonincreasing score vectors agree over sets of profiles. It focuses on agreement ratios as the number of terms in the profiles becomes infinite. The limiting agreement ratios that are considered for (m, k) in {(3,2),(4,2),(4,3)} are uniquely maximized by pairs of Borda (linear, equally-spaced) score vectors and are minimized when (w,v) is either ((1,0,,0),(1,,1,0)) or ((1,,,1,0),(1,0,,0)).This research was supported by the National Science Foundation, Grants SOC 75-00941 and SOC 77-22941.     

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     

Polynomials orthogonal on the semicircle,II

Generalizing previous work [2], we study complex polynomials {π _k },π _k (z)=z ^k +?, orthogonal with respect to a complex-valued inner product (f,g)=∫ ₀ ^π f(e ^iθ)g(e ^iθ)w(e ^iθ)dθ. Under suitable assumptions on the “weight function”w, we show that these polynomials exist whenever Re ∫ ₀ ^π w(e ^iθ)dθ≠0, and we express them in terms of the real polynomials orthogonal with respect to the weight functionw(x). We also obtain the basic three-term recurrence relation. A detailed study is made of the polynomials {π _k } in the case of the Jacobi weight functionw(z)=(1?z)^α(1+z)^β, α>?1, and its special case \(\alpha = \beta = \lambda - \tfrac{1}{2}\) (Gegenbauer weight). We show, in particular, that for Gegenbauer weights the zeros ofπ _n are all simple and, ifn≥2, contained in the interior of the upper unit half disc. We strongly suspect that the same holds true for arbitrary Jacobi weights. Finally, for the Gegenbauer weight, we obtain a linear second-order differential equation forπ _n (z). It has regular singular points atz=1, ?1, ∞ (like Gegenbauer's equation) and an additional regular singular point on the negative imaginary axis, which depends onn.     

Stepwise test procedures and approximate chi-square analysis

Let an overall null hypothesisH be factored in a certain stepwise manner intok subhypotheses as . Suppose the test statisticw forH be correspondingly expressed asw=w ₁ w₂…w_k wherew _i is the test statistic forH _i. We consider the case where the Box method [2] is applicable for the distributions ofw andw _i's. Ifw _i's are independent underH, we obtain a stepwise test procedure forH on the basis of an approximate chi-square analysis. To demonstrate the procedure of this sort, the testing hypotheses of equality of several convariance matrices and of the multiple independence are discussed. Finally the related asymptotic distributions are shortly noted.     

Identification of Refined ARMA Echelon Form Models for Multivariate Time Series

In the present article, we are interested in the identification of canonical ARMA echelon form models represented in a “refined” form. An identification procedure for such models is given by Tsay (J. Time Ser. Anal.10(1989), 357-372). This procedure is based on the theory of canonical analysis. We propose an alternative procedure which does not rely on this theory. We show initially that an examination of the linear dependency structure of the rows of the Hankel matrix of correlations, with originkin (i.e., with correlation at lagkin position (1, 1)), allows us not only to identify the Kronecker indicesn₁, …, n_d, whenk=1, but also to determine the autoregressive ordersp₁, …, p_d, as well as the moving average ordersq₁, …, q_dof the ARMA echelon form model by settingk>1 andk<1, respectively. Successive test procedures for the identification of the structural parametersn_i,p_i, andq_iare then presented. We show, under the corresponding null hypotheses, that the test statistics employed asymptotically follow chi-square distributions. Furthermore, under the alternative hypothesis, these statistics are unbounded in probability and are of the formNδ{1+o_p(1)}, whereδis a positive constant andNdenotes the number of observations. Finally, the behaviour of the proposed identification procedure is illustrated with a simulated series from a given ARMA model.     

Online weighted flow time and deadline scheduling

In this paper we study some aspects of weighted flow time. We first show that the online algorithm Highest Density First is an O(1)-speed O(1)-approximation algorithm for P|r_i,pmtn|∑w_iF_i. We then consider a related Deadline Scheduling Problem that involves minimizing the weight of the jobs unfinished by some unknown deadline D on a uniprocessor. We show that any c-competitive online algorithm for weighted flow time must also be c-competitive for deadline scheduling. We then give an O(1)-competitive algorithm for deadline scheduling.     

Padé approximations to certain power series

Summary An explicit identity involvingQ _n (q ⁱ z) (i = 0, 1,, 4) is shown, whereQ _n (z) is the denominator of thenth Padé approximant to the functionf(z) = _k=0 q ^1/2k(k–1 Z ^k . By using the Padé approximations, irrationality measures for certain values off(z) are also given.

     

Inverse Matroid Intersection Problem

LetM ₁ andM ₂ be matroids onS,B be theirk-element common independent set, andw a weight function onS. Given two functionsb 0 andc 0 onS, the Inverse Matroid Intersection Problem (IMIP) is to determine a modified weight functionw such that (a)B becomes a maximum weight common independent set of cardinalityk underw, (b)c¦w — w¦ is minimum, and (c)¦w — w b. Many Inverse Combinatorial Optimization Problems can be considered as the special cases of the IMIP.In this paper we show that the IMIP can be solved in strongly polynomial time, and give a necessary and sufficient condition for the feasibility of the IMIP. Finally we extend the discussion to the version of the IMIP with Multiple Common Independent Sets.Research partially supported by the National Natural Science Foundation of China     

Manifolds with involution

In this paper, we determine the groups (k _i are odd), (k _i are odd and (k _i are even andn>k _l ), (k _i are even andn>k _l ), (k _i are even andn>k _l ,k _l 12),J _n ^1,2,J _n ^2,3,J _n ^1,4. And we obtain the relation Im _n ^k =J _n ^l,k .     

Integral approximation sequences

Letn linear formsL _i onm variables be given, normalized so that all coefficients have absolute value at most unity. Letw ₁, ...,w _m be real numbers andx ₁, ...,x _m be integers. We sayE _i =L _i (w ₁, ...,w _m )-L _i (x ₁, ...,x _m ) is the error in approximating thew's by thex's with respect to formL _i It is shown that given anyw's there is an integral approximation ofx's so that the errorsE _i are small-roughly that simultaneously for alli.     

An estimate for the region of regularity of solutions of certain nonlinear differential inequalities

In the diskx ²+y ²R ² of thex, y-plane we consider the differential inequalityz _xxz_yy–z _xy ² –(1+z _x ^/2 +z _y ^/2 )^k, where the constants >0 andk>1. In the case =1 andk=2 this inequality means that the surfacez(x, y) has Gaussian curvatureK1. Efimov has shown that in this case the radius of the disk has an upper bound. In the present article we establish an analogous upper bound for the radiusR of the disk in which the functionz(x, y) satisfies the differential inequality above.Translated from Ukrainskií Geometricheskií Sbornik, Issue 28, 1985, pp. 19–21.     

The transcendental meromorphic solutions of a certain type of nonlinear differential equations

In this paper, we study the differential equations of the following form w²+R(z)²(w(k))=Q(z), where R(z), Q(z) are nonzero rational functions. We proved the following three conclusions: (1) If either P(z) or Q(z) is a nonconstant polynomial or k is an even integer, then the differential equation w²+P²(z)²(w(k))=Q(z) has no transcendental meromorphic solution; if P(z), Q(z) are constants and k is an odd integer, then the differential equation has only transcendental meromorphic solutions of the form f(z)=acos(bz+c). (2) If either P(z) or Q(z) is a nonconstant polynomial or k>1, then the differential equation w²+(z−z₀)P²(z)²(w(k))=Q(z) has no transcendental meromorphic solution, furthermore the differential equation w²+A(z−z₀)²(w^′)=B, where A, B are nonzero constants, has only transcendental meromorphic solutions of the form , where a, b are constants such that Ab²=1, a²=B. (3) If the differential equation , where P is a nonconstant polynomial and Q is a nonzero rational function, has a transcendental meromorphic solution, then k is an odd integer and Q is a polynomial. Furthermore, if k=1, then Q(z)≡C (constant) and the solution is of the form f(z)=Bcosq(z), where B is a constant such that B²=C and q^′(z)=±P(z).     

Buffons Nadelproblem und verwandte probleme behandelt mit der Theorie der Gleichverteilung: Teil II

We denote with PC ^m the m-dimensional complex projective space, with U the unitary group acting on it with z _i(j=0, 1,..., m) the homogenous coordinates of a point [z] of PC ^m and assume that the z _i are normalized such that z ₀z₀ +...+z _mz_m=1. Furthermore we denote the U-invariant metric on PC ^m with d. We consider now a uniformly distributed sequence ([z] _k ; k=1,2,...) of points on PC ^m and study the sequence (d ^l([z] _k , [z]₀)), l0, [z]₀ a fixed point. We prove with the help of the theory of uniform distribution properties of this sequence. We consider furthermore a dual sequence suggested by the theory of H. Weyl and L. V. Ahlfors on meromorphic curves.     

Krasnosel'skii numbers for bounded finitely starlike sets inR d

For eachk andd, 1kd, definef(d, d)=d+1 andf(d, k)=2d if 1kd–1. The following results are established:Let be a uniformly bounded collection of compact, convex sets inR ^d . For a fixedk, 1kd, dim {MM in }k if and only if for some > 0, everyf(d, k) members of contain a commonk-dimensional set of measure (volume) at least.LetS be a bounded subset ofR ^d . Assume that for some fixedk, 1kd, there exists a countable family of (k–l)-flats {H _i :i1} inR ^d such that clS S {H_i i 1 } and for eachi1, (clS S) H _i has (k–1) dimensional measure zero. Every finite subset ofS sees viaS a set of positivek-dimensional measure if and only if for some>0, everyf(d,k) points ofS see viaS a set ofk-dimensional measure at least .The numbers off(d,d) andf(d, 1) above are best possible.Supported in part by NSF grant DMS-8705336.