Some cyclic codes of length 2<Emphasis Type="Italic">p</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

Explicit expressions for 4n + 2 primitive idempotents in the semi-simple group ring $R_{2p^{n}}\equiv \frac{GF(q)[x]}{p and q are distinct odd primes; n ≥ 1 is an integer and q has order \fracf(2pⁿ)2{\frac{\phi(2p^{n})}{2}} modulo 2p ⁿ . The generator polynomials, the dimension, the minimum distance of the minimal cyclic codes of length 2p ⁿ generated by these 4n + 2 primitive idempotents are discussed. For n = 1, the properties of some (2p, p) cyclic codes, containing the above minimal cyclic codes are analyzed in particular. The minimum weight of some subset of each of these (2p, p) codes are observed to satisfy a square root bound.     

On the completeness of regular {q(n−1)+m;n}-arcs in a finite projective plane

Summary The notion of regularity for {q(n–1)+1;n}-acrs of a finite projective plane, discussed previously ([3]), is extended to the {q(n–1)+m;n}-acrs of the plane. Following this, conditions for the completeness of regular {q(n–1)+m;n}-arcs are determined.Lavoro eseguito nell' ambito dei contratti di ricerca matematici del C.N.R.     

Computing homotopic shortest paths in the plane

We address the problem of computing homotopic shortest paths in the presence of obstacles in the plane. Problems on homotopy of paths received attention very recently [Cabello et al., in: Proc. 18th Annu. ACM Sympos. Comput. Geom., 2002, pp. 160–169; Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. We present two output-sensitive algorithms, for simple paths and non-simple paths. The algorithm for simple paths improves the previous algorithm [Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. The algorithm for non-simple paths achieves O(log²n) time per output vertex which is an improvement by a factor of O(n/log²n) of the previous algorithm [Hershberger, Snoeyink, Comput. Geom. Theory Appl. 4 (1994) 63–98], where n is the number of obstacles. The running time has an overhead O(n²⁺) for any positive constant . In the case k<n²⁺, where k is the total size of the input and output, we improve the running to O((n+k+(nk)^2/3)log^O(1)n).     

On the Average Running Time of Odd–Even Merge Sort

This paper gives an upper bound for the average running time of Batcher's odd–even merge sort when implemented on a collection of processors. We consider the case wheren, the size of the input, is an arbitrary multiple of the numberpof processors used. We show that Batcher's odd–even merge (for two sorted lists of lengthneach) can be implemented to run in timeO((n/p)(log(2 + p²/n))) on the average,¹and that odd–even merge sort can be implemented to run in timeO((n/p)(log n + log p log(2 + p²/n))) on the average. In the case of merging (sorting), the average is taken over all possible outcomes of the merge (all possible permutations ofnelements). That means that odd–even merge and odd–even merge sort have an optimal average running time ifn ≥ p². The constants involved are also quite small.     

On an Approximate Solution of the Dirichlet Problem for the Generalized Laplacian

For an arbitrary differential operator P of order p on an open set X ? R ⁿ, the Laplacian is defined by Δ = P*P. It is an elliptic differential operator of order 2p provided the symbol mapping of P is injective. Let O be a relatively compact domain in X with smooth boundary, and B_j(j = 0…,p — 1) be a Dirichlet system of order p ? 1 on ?O. By {C_j} we denote the Dirichlet system on ?O adjoint for {B_j} with respect to the Green formula for P. The Hardy space H²(O) is defined to consist of all the solutions f of Δf = 0 in O of finite order of growth near the boundary such that the weak boundary values of the expression {B_jf} and {C_j(Pf)} belong to the Lebesgue space L²(?O). Then the Dirichlet problem consists of finding a solution f ? H²(O) with prescribed data {B_jf} on ?O. We develop the classical Fischer-Riesz equations method to derive a solvability condition of the Dirichlet problem as well as an approximate formula for solutions.     

Asymptotic behavior of positive solutions of fourth-order nonlinear difference equations

We consider a class of fourth-order nonlinear difference equations of the form {fx006-01} where α, β are ratios of odd positive integers and {p _n}, {q _n} are positive real sequences defined for all n ∈ ℕ(n ₀). We establish necessary and sufficient conditions for the existence of nonoscillatory solutions with specific asymptotic behavior under suitable combinations of convergence or divergence conditions for the sums {fx006-02}. Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 60, No. 1, pp. 8–27, January, 2008.     

Mean-Field Conditions for Percolation on Finite Graphs

Let {G _n } be a sequence of finite transitive graphs with vertex degree d = d(n) and |G _n | = n. Denote by p ^t (v, v) the return probability after t steps of the non-backtracking random walk on G _n . We show that if p ^t (v, v) has quasi-random properties, then critical bond-percolation on G _n behaves as it would on a random graph. More precisely, if $\mathop {\rm {lim\, sup\,}} \limits_{n} n^{1/3} \sum\limits_{t = 1}^{n^{1/3}} {t{\bf p}^t(v,v) < \infty ,}$ then the size of the largest component in p-bond-percolation with ${p =\frac{1+O(n^{-1/3})}{d-1}}Let {G _n } be a sequence of finite transitive graphs with vertex degree d = d(n) and |G _n | = n. Denote by p ^t (v, v) the return probability after t steps of the non-backtracking random walk on G _n . We show that if p ^t (v, v) has quasi-random properties, then critical bond-percolation on G _n behaves as it would on a random graph. More precisely, if

lim sup  n n1/3 ?t = 1n1/3 tpt(v,v) < ￥,\mathop {\rm {lim\, sup\,}} \limits_{n} n^{1/3} \sum\limits_{t = 1}^{n^{1/3}} {t{\bf p}^t(v,v) < \infty ,}      8. S<Superscript>1</Superscript>-Valued Sobolev maps      P. Mironescu 《Journal of Mathematical Sciences》2010,170(3):340-355 We describe the structure of the space Ws,p( \mathbbSn;\mathbbS1 ) {W^{s,p}}\left( {{\mathbb{S}^n};{\mathbb{S}^1}} \right) , where 0 < s < ∞ and 1 ≤ p < ∞. According to the values of s, p, and n, maps in Ws,p( \mathbbSn;\mathbbS1 ) {W^{s,p}}\left( {{\mathbb{S}^n};{\mathbb{S}^1}} \right) can either be characterised by their phases or by a couple (singular set, phase).      9. On the maximal ergodic theorem for certain subsets of the integers   总被引：6，自引：0，他引：6   J. Bourgain 《Israel Journal of Mathematics》1988,61(1):39-72 It is shown that the set of squares {n 2|n=1, 2,…} or, more generally, sets {n t|n=1, 2,…},t a positive integer, satisfies the pointwise ergodic theorem forL 2-functions. This gives an affirmative answer to a problem considered by A. Bellow [Be] and H. Furstenberg [Fu]. The previous result extends to polynomial sets {p(n)|n=1, 2,…} and systems of commuting transformations. We also state density conditions for random sets of integers in order to be “good sequences” forL p-functions,p>1.      10. The complexity and depth of Boolean circuits for multiplication and inversion in some fields <Emphasis Type="Italic">GF</Emphasis>(2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>)      S. B. Gashkov  I. S. Sergeev 《Moscow University Mathematics Bulletin》2009,64(4):139-143 Let n = (p − 1) · p k , where p is a prime number such that 2 is a primitive root modulo p, and 2 p−1 − 1 is not a multiple of p 2. For a standard basis of the field GF(2 n ), a multiplier of complexity O(log log p)n log n log log p n and an inverter of complexity O(log p log log p)n log n log log p n are constructed. In particular, in the case p = 3 the upper bound $ 5\frac{5} {8}n\log _3 n\log _2 \log _3 n + O(n\log n) $ 5\frac{5} {8}n\log _3 n\log _2 \log _3 n + O(n\log n)       11. Para-orthogonal Laurent polynomials and associated sequences of rational functions      Catherine M. Bonan-Hamada  William B. Jones  W. J. Thron  Arne Magnus 《Numerical Algorithms》1992,3(1):67-74 On the space, , of Laurent polynomials (L-polynomials) we consider a linear functional which is positive definite on (0, ) and is defined in terms of a given bisequence, { k } – . Two sequences of orthogonal L-polynomials, {Q n (z) 0 and , are constructed which span in the order {1,z –1,z,z –2,z 2,...} and {1,z,z –1,z 2,z –2,...} respectively. Associated sequences of L-polynomials {P n (z) 0 , and are introduced and we define rational functions , wherew is a fixed positive number. The partial fraction decomposition and integral representation of,M n (z, w) are given and correspondence of {M n (z, w)} is discussed. We get additional solutions to the strong Stieltjes moment problem from subsequences of {M n (z, w)}. In particular when { k } – is a log-normal bisequence, {M 2n (z, w)} and {M 2n+1 (z, w)} yield such solutions.Research supported in part by the National Science Foundation under Grant DMS-9103141.      12. On the parity of the class number of an imaginary abelian field of conductor 2<Superscript><Emphasis Type="Italic">a</Emphasis></Superscript><Emphasis Type="Italic">p</Emphasis><Superscript><Emphasis Type="Italic">b</Emphasis></Superscript>      Humio Ichimura 《Archiv der Mathematik》2011,96(6):555-563 Let p be an odd prime number, and pn0{p^{n_0}} the highest power of p dividing 2 p−1 − 1. Let Kn=Q(zpn+1){K_n={\bf Q}(\zeta_{p^{n+1}})} and Ln,j=Kn+(z2j+2){L_{n,j}=K_n^+(\zeta_{2^{j+2}})} for j ≥ 0. Let hn*{h_n^*} be the relative class number of K n , and h n,j the class number of L n,j , respectively. Let n be an integer with n ≥ n 0. We prove that if the ratio hn*/hn-1*{h_n^*/h_{n-1}^*} is odd, then h n,j /h n−1,j is odd for any j ≥ 0.      13. Infinite series of combinatorially regular polyhedra in three-space      P. McMullen  E. Schulte  J. M. Wills 《Geometriae Dedicata》1988,26(3):299-307 The paper discusses polyhedral realizations in ordinary Euclidean 3-space of Coxeter's regular skew polyhedra {4, p|4 p/2]–1} and their duals on an orientable surface of genus 2 p–3(p–4)+1. Our considerations are based on work of Coxeter, Ringel and McMullen et al., revealing that certain polyhedral manifolds discovered by the last three authors are in fact the polyhedra in question. We also describe Kepler-Poinsot-type polyhedra in 3-space obtained by projections from Coxeter's regular skew star-polyhedra in 4 dimensions.      14. Higher order representations of the Robbins–Monro process      Jürgen Dippon   《Journal of multivariate analysis》2004,90(2):301-326 For quasi-linear regression functions, the Robbins–Monro process Xn is decomposed in a sum of a linear form and a quadratic form both defined in the observation errors. Under regularity conditions, the remainder term is of order O(n−3/2) with respect to the Lp-norm. If a cubic form is added, the remainder term can be improved up to an order of O(n−2). As a corollary the expectation of Xn is expanded up to an error of order O(n−2). This is used to correct the bias of Xn up to an error of order O(n−3/2 log n).      15. One-dimensional Tilings Using Tiles with Two Gap Lengths      Tomoki Nakamigawa 《Graphs and Combinatorics》2005,21(1):97-105 Let n,p,k,q,l be positive integers with n=k+l+1. Let x1,x2, . . . ,xn be a sequence of positive integers with x1<x2<···<xn. A set {x1,x2, . . . ,xn} is called a set of type (p,k;q,l) if the set of differences {x2–x1,x3–x2, . . . ,xn–xn–1} equals {p, . . . ,p,q, . . . ,q} as a multiset, where p and q appear k and l times, respectively. Among other results, it is shown that for any p,k,q, there exists a finite interval I in the set of integers such that I is partitioned into sets of type (p,k;q,1).      16. On improved estimators of the generalized variance      Bimal Kumar Sinha 《Journal of multivariate analysis》1976,6(4):617-625 Treated in this paper is the problem of estimating with squared error loss the generalized variance | Σ | from a Wishart random matrix S: p × p Wp(n, Σ) and an independent normal random matrix X: p × k N(ξ, Σ Ik) with ξ(p × k) unknown. Denote the columns of X by X(1) ,…, X(k) and set ψ(0)(S, X) = {(n − p + 2)!/(n + 2)!} | S |, ψ(i)(X, X) = min[ψ(i−1)(S, X), {(n − p + i + 2)!/(n + i + 2)!} | S + X(1) X′(1) + + X(i) X′(i) |] and Ψ(i)(S, X) = min[ψ(0)(S, X), {(n − p + i + 2)!/(n + i + 2)!}| S + X(1) X′(1) + + X(i) X′(i) |], i = 1,…,k. Our result is that the minimax, best affine equivariant estimator ψ(0)(S, X) is dominated by each of Ψ(i)(S, X), i = 1,…,k and for every i, ψ(i)(S, X) is better than ψ(i−1)(S, X). In particular, ψ(k)(S, X) = min[{(n − p + 2)!/(n + 2)!} | S |, {(n − p + 2)!/(n + 2)!} | S + X(1)X′(1)|,…,| {(n − p + k + 2)!/(n + k + 2)!} | S + X(1)X′(1) + + X(k)X′(k)|] dominates all other ψ's. It is obtained by considering a multivariate extension of Stein's result (Ann. Inst. Statist. Math. 16, 155–160 (1964)) on the estimation of the normal variance.      17. Fast inversion of vandermonde-like matrices involving orthogonal polynomials      D. Calvetti  L. Reichel 《BIT Numerical Mathematics》1993,33(3):473-484 Let {q} j =0n–1 be a family of polynomials that satisfy a three-term recurrence relation and let {t k } k =1n be a set of distinct nodes. Define the Vandermonde-like matrixW n =[w jk ] k,j =1n ,w jk =q j–1(t k ). We describe a fast algorithm for computing the elements of the inverse ofW n inO(n 2) arithmetic operations. Our algorithm generalizes a scheme presented by Traub [22] for fast inversion of Vandermonde matrices. Numerical examples show that our scheme often yields higher accuracy than the LINPACK subroutine SGEDI for inverting a general matrix. SGEDI uses Gaussian elimination with partial pivoting and requiresO(n 3) arithmetic operations.Dedicated to Gene H. Golub on his 60th birthdayResearch supported by NSF grant DMS-9002884.      18. A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions      Kazuhisa Makino  Toshihide Ibaraki 《Journal of Algorithms in Cognition, Informatics and Logic》1998,26(2):291-305 Consider the problem of identifying min T(f) and max F(f) of a positive (i.e., monotone) Boolean functionf, by using membership queries only, where min T(f) (max F(f)) denotes the set of minimal true vectors (maximum false vectors) off. Moreover, as the existence of a polynomial total time algorithm (i.e., polynomial time in the length of input and output) for this problem is still open, we consider here a restricted problem: given an unknown positive functionfofnvariables, decide whetherfis 2-monotonic or not, and iffis 2-monotonic, output both min T(f) and max F(f). For this problem, we propose a simple algorithm, which is based on the concept of maximum latency, and we show that it usesO(n2m) time andO(n2m) queries, wherem = |min T(f)| + |max F(f)|. This answers affirmatively the conjecture raised in Boroset al.[Lecture Notes in Comput. Sci.557(1991), 104–115], Boroset al.[SIAM J. Comput.26(1997), 93–109], and is an improvement over the two algorithms discussed therein: one usesO(n3m) time andO(n3m) queries, and the other usesO(nm2 + n2m) time andO(nm) queries.      19. Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches      Jyh-Jye Lin  Biing-Feng Wang 《Discrete Applied Mathematics》2010,158(8):932-942 Let p≥2 be an integer and T be an edge-weighted tree. A cut on an edge of T is a splitting of the edge at some point on it. A p-edge-partition of T is a set of p subtrees induced by p−1 cuts. Given p and T, the max-min continuous tree edge-partition problem is to find a p-edge-partition that maximizes the length of the smallest subtree; and the min-max continuous tree edge-partition problem is to find a p-edge-partition that minimizes the length of the largest subtree. In this paper, O(n2)-time algorithms are proposed for these two problems, improving the previous upper bounds by a factor of log (min{p,n}). Along the way, we solve a problem, named the ratio search problem. Given a positive integer m, a (non-ordered) set B of n non-negative real numbers, a real valued non-increasing function F, and a real number t, the problem is to find the largest number z in {b/a|a∈[1,m],b∈B} such that F(z)≥t. We give an O(n+tF×(logn+logm))-time algorithm for this problem, where tF is the time required to evaluate the function value F(z) for any real number z.      20. Generating Uniform Random Vectors in Z p k : The General Case      Claudio Asci 《Journal of Theoretical Probability》2009,22(3):791-809 We consider the rate of convergence of the Markov chain X n+1=A X n +B n (mod p), where A is an integer matrix with nonzero eigenvalues, and {B n } n is a sequence of independent and identically distributed integer vectors, with support not parallel to a proper subspace of Q k invariant under A. If for all eigenvalues λ i of A, then n=O((ln p)2) steps are sufficient and n=O(ln p) steps are necessary to have X n sampling from a nearly uniform distribution. Conversely, if A has the eigenvalues λ i that are roots of positive integer numbers, |λ 1|=1 and |λ i |>1 for all , then O(p 2) steps are necessary and sufficient.

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号

S<Superscript>1</Superscript>-Valued Sobolev maps

We describe the structure of the space W^s,p( \mathbbSⁿ;\mathbbS¹ ) {W^{s,p}}\left( {{\mathbb{S}^n};{\mathbb{S}^1}} \right) , where 0 < s < ∞ and 1 ≤ p < ∞. According to the values of s, p, and n, maps in W^s,p( \mathbbSⁿ;\mathbbS¹ ) {W^{s,p}}\left( {{\mathbb{S}^n};{\mathbb{S}^1}} \right) can either be characterised by their phases or by a couple (singular set, phase).     

On the maximal ergodic theorem for certain subsets of the integers

It is shown that the set of squares {n ²|n=1, 2,…} or, more generally, sets {n ^t|n=1, 2,…},t a positive integer, satisfies the pointwise ergodic theorem forL ²-functions. This gives an affirmative answer to a problem considered by A. Bellow [Be] and H. Furstenberg [Fu]. The previous result extends to polynomial sets {p(n)|n=1, 2,…} and systems of commuting transformations. We also state density conditions for random sets of integers in order to be “good sequences” forL ^p-functions,p>1.     

The complexity and depth of Boolean circuits for multiplication and inversion in some fields <Emphasis Type="Italic">GF</Emphasis>(2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>)

Let n = (p − 1) · p ^k , where p is a prime number such that 2 is a primitive root modulo p, and 2 ^p−1 − 1 is not a multiple of p ². For a standard basis of the field GF(2 ⁿ ), a multiplier of complexity O(log log p)n log n log log _p n and an inverter of complexity O(log p log log p)n log n log log _p n are constructed. In particular, in the case p = 3 the upper bound

Para-orthogonal Laurent polynomials and associated sequences of rational functions

On the space, , of Laurent polynomials (L-polynomials) we consider a linear functional which is positive definite on (0, ) and is defined in terms of a given bisequence, { _k } _– . Two sequences of orthogonal L-polynomials, {Q _n (z) ₀ and , are constructed which span in the order {1,z ^–1,z,z ^–2,z ²,...} and {1,z,z ^–1,z ²,z ^–2,...} respectively. Associated sequences of L-polynomials {P _n (z) ₀ , and are introduced and we define rational functions , wherew is a fixed positive number. The partial fraction decomposition and integral representation of,M _n (z, w) are given and correspondence of {M _n (z, w)} is discussed. We get additional solutions to the strong Stieltjes moment problem from subsequences of {M _n (z, w)}. In particular when { _k } _– is a log-normal bisequence, {M _2n (z, w)} and {M _2n+1 (z, w)} yield such solutions.Research supported in part by the National Science Foundation under Grant DMS-9103141.     

On the parity of the class number of an imaginary abelian field of conductor 2<Superscript><Emphasis Type="Italic">a</Emphasis></Superscript><Emphasis Type="Italic">p</Emphasis><Superscript><Emphasis Type="Italic">b</Emphasis></Superscript>

Let p be an odd prime number, and p^n₀{p^{n_0}} the highest power of p dividing 2 ^p−1 − 1. Let K_n=Q(z_pⁿ⁺¹){K_n={\bf Q}(\zeta_{p^{n+1}})} and L_n,j=K_n⁺(z_2^j+2){L_{n,j}=K_n^+(\zeta_{2^{j+2}})} for j ≥ 0. Let h_n^*{h_n^*} be the relative class number of K _n , and h _n,j the class number of L _n,j , respectively. Let n be an integer with n ≥ n ₀. We prove that if the ratio h_n^*/h_n-1^*{h_n^*/h_{n-1}^*} is odd, then h _n,j /h _n−1,j is odd for any j ≥ 0.     

Infinite series of combinatorially regular polyhedra in three-space

The paper discusses polyhedral realizations in ordinary Euclidean 3-space of Coxeter's regular skew polyhedra {4, p|4 ^p/2]–1} and their duals on an orientable surface of genus 2 ^p–3(p–4)+1. Our considerations are based on work of Coxeter, Ringel and McMullen et al., revealing that certain polyhedral manifolds discovered by the last three authors are in fact the polyhedra in question. We also describe Kepler-Poinsot-type polyhedra in 3-space obtained by projections from Coxeter's regular skew star-polyhedra in 4 dimensions.     

Higher order representations of the Robbins–Monro process

For quasi-linear regression functions, the Robbins–Monro process X_n is decomposed in a sum of a linear form and a quadratic form both defined in the observation errors. Under regularity conditions, the remainder term is of order O(n^−3/2) with respect to the L_p-norm. If a cubic form is added, the remainder term can be improved up to an order of O(n⁻²). As a corollary the expectation of X_n is expanded up to an error of order O(n⁻²). This is used to correct the bias of X_n up to an error of order O(n^−3/2 log n).     

One-dimensional Tilings Using Tiles with Two Gap Lengths

Let n,p,k,q,l be positive integers with n=k+l+1. Let x₁,x₂, . . . ,x_n be a sequence of positive integers with x₁<x₂<···<x_n. A set {x₁,x₂, . . . ,x_n} is called a set of type (p,k;q,l) if the set of differences {x₂–x₁,x₃–x₂, . . . ,x_n–x_n–1} equals {p, . . . ,p,q, . . . ,q} as a multiset, where p and q appear k and l times, respectively. Among other results, it is shown that for any p,k,q, there exists a finite interval I in the set of integers such that I is partitioned into sets of type (p,k;q,1).     

On improved estimators of the generalized variance

Treated in this paper is the problem of estimating with squared error loss the generalized variance | Σ | from a Wishart random matrix S: p × p W_p(n, Σ) and an independent normal random matrix X: p × k N(ξ, Σ I_k) with ξ(p × k) unknown. Denote the columns of X by X₍₁₎ ,…, X_(k) and set ψ⁽⁰⁾(S, X) = {(n − p + 2)!/(n + 2)!} | S |, ψ⁽ⁱ⁾(X, X) = min[ψ⁽ⁱ⁻¹⁾(S, X), {(n − p + i + 2)!/(n + i + 2)!} | S + X₍₁₎ X′₍₁₎ + + X_(i) X′_(i) |] and Ψ⁽ⁱ⁾(S, X) = min[ψ⁽⁰⁾(S, X), {(n − p + i + 2)!/(n + i + 2)!}| S + X₍₁₎ X′₍₁₎ + + X_(i) X′_(i) |], i = 1,…,k. Our result is that the minimax, best affine equivariant estimator ψ⁽⁰⁾(S, X) is dominated by each of Ψ⁽ⁱ⁾(S, X), i = 1,…,k and for every i, ψ⁽ⁱ⁾(S, X) is better than ψ⁽ⁱ⁻¹⁾(S, X). In particular, ψ^(k)(S, X) = min[{(n − p + 2)!/(n + 2)!} | S |, {(n − p + 2)!/(n + 2)!} | S + X₍₁₎X′₍₁₎|,…,| {(n − p + k + 2)!/(n + k + 2)!} | S + X₍₁₎X′₍₁₎ + + X_(k)X′_(k)|] dominates all other ψ's. It is obtained by considering a multivariate extension of Stein's result (Ann. Inst. Statist. Math. 16, 155–160 (1964)) on the estimation of the normal variance.     

Fast inversion of vandermonde-like matrices involving orthogonal polynomials

Let {q} _j ^=0n–1 be a family of polynomials that satisfy a three-term recurrence relation and let {t _k } _k ⁼¹ⁿ be a set of distinct nodes. Define the Vandermonde-like matrixW _n =[w _jk ] _k,j ⁼¹ⁿ ,w _jk =q _j–1(t _k ). We describe a fast algorithm for computing the elements of the inverse ofW _n inO(n ²) arithmetic operations. Our algorithm generalizes a scheme presented by Traub [22] for fast inversion of Vandermonde matrices. Numerical examples show that our scheme often yields higher accuracy than the LINPACK subroutine SGEDI for inverting a general matrix. SGEDI uses Gaussian elimination with partial pivoting and requiresO(n ³) arithmetic operations.Dedicated to Gene H. Golub on his 60th birthdayResearch supported by NSF grant DMS-9002884.     

A Fast and Simple Algorithm for Identifying 2-Monotonic Positive Boolean Functions

Consider the problem of identifying min T(f) and max F(f) of a positive (i.e., monotone) Boolean functionf, by using membership queries only, where min T(f) (max F(f)) denotes the set of minimal true vectors (maximum false vectors) off. Moreover, as the existence of a polynomial total time algorithm (i.e., polynomial time in the length of input and output) for this problem is still open, we consider here a restricted problem: given an unknown positive functionfofnvariables, decide whetherfis 2-monotonic or not, and iffis 2-monotonic, output both min T(f) and max F(f). For this problem, we propose a simple algorithm, which is based on the concept of maximum latency, and we show that it usesO(n²m) time andO(n²m) queries, wherem = |min T(f)| + |max F(f)|. This answers affirmatively the conjecture raised in Boroset al.[Lecture Notes in Comput. Sci.557(1991), 104–115], Boroset al.[SIAM J. Comput.26(1997), 93–109], and is an improvement over the two algorithms discussed therein: one usesO(n³m) time andO(n³m) queries, and the other usesO(nm² + n²m) time andO(nm) queries.     

Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches

Let p≥2 be an integer and T be an edge-weighted tree. A cut on an edge of T is a splitting of the edge at some point on it. A p-edge-partition of T is a set of p subtrees induced by p−1 cuts. Given p and T, the max-min continuous tree edge-partition problem is to find a p-edge-partition that maximizes the length of the smallest subtree; and the min-max continuous tree edge-partition problem is to find a p-edge-partition that minimizes the length of the largest subtree. In this paper, O(n²)-time algorithms are proposed for these two problems, improving the previous upper bounds by a factor of log (min{p,n}). Along the way, we solve a problem, named the ratio search problem. Given a positive integer m, a (non-ordered) set B of n non-negative real numbers, a real valued non-increasing function F, and a real number t, the problem is to find the largest number z in {b/a|a∈[1,m],b∈B} such that F(z)≥t. We give an O(n+t_F×(logn+logm))-time algorithm for this problem, where t_F is the time required to evaluate the function value F(z) for any real number z.     

Generating Uniform Random Vectors in Z p k : The General Case

We consider the rate of convergence of the Markov chain X _n+1=A X _n +B _n (mod p), where A is an integer matrix with nonzero eigenvalues, and {B _n } _n is a sequence of independent and identically distributed integer vectors, with support not parallel to a proper subspace of Q ^k invariant under A. If for all eigenvalues λ _i of A, then n=O((ln p)²) steps are sufficient and n=O(ln p) steps are necessary to have X _n sampling from a nearly uniform distribution. Conversely, if A has the eigenvalues λ _i that are roots of positive integer numbers, |λ ₁|=1 and |λ _i |>1 for all , then O(p ²) steps are necessary and sufficient.