Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems

A particular class of preconditioners for the conjugate gradient method and other iterative methods is proposed for the solution of linear systemsA _n,mx=b, whereA _n,m is ann×n positive definite block Toeplitz matrix withm×m Toeplitz blocks. In particular we propose a sparse preconditionerP _n,m such that the condition number of the preconditioned matrix turns out to be less than a suitable constant independent of bothn andm, even if the condition number ofA _n,m tends to . This leads to iterative methods which require a number of steps independent ofm andn in order to reduce the error by a given factor.     

Preconditioners for block Toeplitz systems based on circulant preconditioners

We study the numerical solution of a block system T _m,n x=b by preconditioned conjugate gradient methods where T _m,n is an m×m block Toeplitz matrix with n×n Toeplitz blocks. These systems occur in a variety of applications, such as two-dimensional image processing and the discretization of two-dimensional partial differential equations. In this paper, we propose new preconditioners for block systems based on circulant preconditioners. From level-1 circulant preconditioner we construct our first preconditioner q ₁(T _m,n ) which is the sum of a block Toeplitz matrix with Toeplitz blocks and a sparse matrix with Toeplitz blocks. By setting selected entries of the inverse of level-2 circulant preconditioner to zero, we get our preconditioner q ₂(T _m,n ) which is a (band) block Toeplitz matrix with (band) Toeplitz blocks. Numerical results show that our preconditioners are more efficient than circulant preconditioners.     

On the structure of linear graphs

Denote byG(n; m) a graph ofn vertices andm edges. We prove that everyG(n; [n ²/4]+1) contains a circuit ofl edges for every 3 ≦l<c ₂ n, also that everyG(n; [n ²/4]+1) contains ak _e(u _n, u_n) withu _n=[c ₁ logn] (for the definition ofk _e(u _n, u_n) see the introduction). Finally fort>t ₀ everyG(n; [tn ^3/2]) contains a circuit of 2l edges for 2≦l<c ₃ t ². This work was done while the author received support from the National Science Foundation, N.S.F. G.88.     

Asymptotic Formulas for the Zeros of the Meixner Polynomials

The zeros of the Meixner polynomialm_n(x; β, c) are real, distinct, and lie in (0, ∞). Letα_{n, s}denote thesth zero ofm_n(nα; β, c), counted from the right; and letα_{n, s}denote thesth zero ofm_n(nα; β, c), counted from the left. For each fixeds, asymptotic formulas are obtained for bothα_{n, s}andα_{n, s}, asn→∞.     

A direct method for the general solution of a system of linear equations

A computationally stable method for the general solution of a system of linear equations is given. The system isA ^Tx–B=0, where then-vectorx is unknown and then×q matrixA and theq-vectorB are known. It is assumed that the matrixA ^T and the augmented matrix [A ^T,B] are of the same rankm, wheremn, so that the system is consistent and solvable. Whenm<n, the method yields the minimum modulus solutionx _m and a symmetricn ×n matrixH _m of rankn–m, so thatx=x _m+H _my satisfies the system for ally, ann-vector. Whenm=n, the matrixH _m reduces to zero andx _m becomes the unique solution of the system.The method is also suitable for the solution of a determined system ofn linear equations. When then×n coefficient matrix is ill-conditioned, the method can produce a good solution, while the commonly used elimination method fails.This research was supported by the National Science Foundation, Grant No. GP-41158.     

Admissible wavelets on the Siegel domain of type one

LetSp(n, R) be the sympletic group, and letK _n * be its maximal compact subgroup. ThenG=Sp(n,R)/K _n * can be realized as the Siegel domain of type one. The square-integrable representation ofG gives the admissible wavelets AW and wavelet transform. The characterization of admissibility condition in terms of the Fourier transform is given. The Bergman kernel follows from the viewpoint of coherent state. With the Laguerre polynomials, Hermite polynomials and Jacobi polynomials, two kinds of orthogonal bases for AW are given, and they then give orthogonal decompositions ofL ²-space on the Siegel domain of type one ℒ(ℋ _n , |y| *dxdy). Project supported in part by the National Natural Science Foundation of China (Grant No. 19631080).     

Selection in Monotone Matrices and Computingkth Nearest Neighbors

Anm×nmatrix =(a_{i, j}), 1≤i≤mand 1≤j≤n, is called atotally monotonematrix if for alli₁, i₂, j₁, j₂, satisfying 1≤i₁<i₂≤m, 1≤j₁<j₂≤n.[formula]We present an[formula]time algorithm to select thekth smallest item from anm×ntotally monotone matrix for anyk≤mn. This is the first subquadratic algorithm for selecting an item from a totally monotone matrix. Our method also yields an algorithm of the same time complexity for ageneralized row-selection problemin monotone matrices. Given a setS={p₁,…, p_n} ofnpoints in convex position and a vectork={k₁,…, k_n}, we also present anO(n^4/3log^c n) algorithm to compute thek_ith nearest neighbor ofp_ifor everyi≤n; herecis an appropriate constant. This algorithm is considerably faster than the one based on a row-selection algorithm for monotone matrices. If the points ofSare arbitrary, then thek_ith nearest neighbor ofp_i, for alli≤n, can be computed in timeO(n^7/5 log^c n), which also improves upon the previously best-known result.     

Straffe Untermannigfaltigkeiten in konvexen Hyperflächen

It will be proved that a tight substantial embedding ofS ^m×Sⁿ intoE ^m+n+2 whose image lies in a strictly convex hypersurface is projectively equivalent to the productC ₁×C ₂E ^m+1×E ^m+1=E ^m+n+2 of two convex hypersurfacesC ₁ undC ₂.     

Correlated equilibria of games with many players

Let G _m,n be the class of strategic games with n players, where each player has m≥2 pure strategies. We are interested in the structure of the set of correlated equilibria of games in G _m,n when n→∞. As the number of equilibrium constraints grows slower than the number of pure strategy profiles, it might be conjectured that the set of correlated equilibria becomes large. In this paper, we show that (1) the average relative measure of the set of correlated equilibria is smaller than 2⁻ⁿ; and (2) for each 1<c<m, the solution set contains c ⁿ correlated equilibria having disjoint supports with a probability going to 1 as n grows large. The proof of the second result hinges on the following inequality: Let c ₁, …, c _l be independent and symmetric random vectors in R ^k, l≥k. Then the probability that the convex hull of c ₁, …, c _l intersects R ^k ₊ is greater than or equal to . Received: December 1998/Final version: March 2000     

A generalization of the Busemann-Petty problem on sections of convex bodies

It is proved that for arbitrarymεℕ and for a sufficiently nontrivial compact groupG of operators acting on a “typical”n-dimensional quotientX _n ofl ₁ ^m withm=(1+δ)n, there is a constantc=c(δ) such that Supported in part by KBN grant no. 2 P03A 034 10.     

Cycle systems without 2-colorings

In an m-cycle system C of order n the blocks are the vertex sets of n(n−1)/(2m) cycles C_i such that each edge of the complete graph K_n belongs to precisely one cycle C_i E C. We prove the existence of m-cycle systems that admit no vertex partition into two classes in such a way that each class meets every cycle of C. The proofs apply both constructive and probabilistic methods, and also some old and new facts about Steiner Triple Systems without large independent sets. © 1996 John Wiley & Sons, Inc.     

Some Best Constants in the Landau Inequality on a Finite Interval

An additive form of the Landau inequality forf∈Wⁿ_∞[−1, 1],is proved for 0<c?(cos(π/2n))⁻², 1?m?n−1, with equality forf(x)=T_n(1+(x−1)/c), 1?c?(cos(π/2n))⁻², whereT_nis the Chebyshev polynomial. From this follows a sharp multiplicative inequality,for ‖f⁽ⁿ⁾‖?σ ‖f‖, 2ⁿ⁻¹n! cos²ⁿ(π/2n)?σ?2ⁿ⁻¹n!, 1?m?n−1. For these values ofσ, the result confirms Karlin's conjecture on the Landau inequality for intermediate derivatives on a finite interval. For the proof of the additive inequality a Duffin and Schaeffer-type inequality for polynomials is shown.     

The exact density function of the ratio of two dependent linear combinations of chi-square variables

A computable expression is derived for the raw moments of the random variableZ=N/D whereN= ₁ ⁿ m _iX_i+ _n ^+1s m _iX_i,D= _n ^+1s l _iX_i+ _s ^+1r n _iX_i, and theX _i's are independently distributed central chi-square variables. The first four moments are required for approximating the distribution ofZ by means of Pearson curves. The exact density function ofZ is obtained in terms of sums of generalized hypergeometric functions by taking the inverse Mellin transform of theh-th moment of the ratioN/D whereh is a complex number. The casen=1,s=2 andr=3 is discussed in detail and a general technique which applies to any ratio having the structure ofZ is also described. A theoretical example shows that the inverse Mellin transform technique yields the exact density function of a ratio whose density can be obtained by means of the transformation of variables technique. In the second example, the exact density function of a ratio of dependent quardratic forms is evaluated at various points and then compared with simulated values.     

Sine transform based preconditioners for elliptic problems

We consider applying the preconditioned conjugate gradient (PCG) method to solving linear systems Ax = b where the matrix A comes from the discretization of second-order elliptic operators with Dirichlet boundary conditions. Let (L + Σ)Σ⁻¹(L^t + Σ) denote the block Cholesky factorization of A with lower block triangular matrix L and diagonal block matrix Σ. We propose a preconditioner M = (Lˆ + Σˆ)Σˆ⁻¹(Lˆ^t + Σˆ) with block diagonal matrix Σˆ and lower block triangular matrix Lˆ. The diagonal blocks of Σˆ and the subdiagonal blocks of Lˆ are respectively the optimal sine transform approximations to the diagonal blocks of Σ and the subdiagonal blocks of L. We show that for two-dimensional domains, the construction cost of M and the cost for each iteration of the PCG algorithm are of order O(n² log n). Furthermore, for rectangular regions, we show that the condition number of the preconditioned system M⁻¹A is of order O(1). In contrast, the system preconditioned by the MILU and MINV methods are of order O(n). We will also show that M can be obtained from A by taking the optimal sine transform approximations of each sub-block of A. Thus, the construction of M is similar to that of Level-1 circulant preconditioners. Our numerical results on two-dimensional square and L-shaped domains show that our method converges faster than the MILU and MINV methods. Extension to higher-dimensional domains will also be discussed. © 1997 John Wiley & Sons, Ltd.     

Simplicial algorithm to solve the nonlinear complementarity problem onS n×R + m

In this paper, a simplicial algorithm is developed to solve the nonlinear complementarity problem onS ⁿ×R ₊ ^m . Furthermore, a condition for convergence is formulated. The triangulation which underlies the algorithm is a combination of the V-triangulation ofS ⁿ and the K-triangulation ofR ₊ ^m . Therefore, we will call it the VK-triangulation.The author wishes to thank Professor G. van der Laan for his valuable comments.     

The sequence of codimensions of PI-algebras

Bounds and asymptotic formulas are given for the size of the irreducible representations of the symmetric groups. These are applied to obtain information on the identities and codimension sequencec _n(R) of a PI-algebraR, of a PI-algebraR of characteristic zero, e.g., the “ultimate” width of the hook in which the diagrams of the cocharacters ofR lies is <=(lim c _n (R)^1/n ) ² , and lim c_n(R)^1/n≦ 2(lim c_n(R)^1/n)² for rings with no right (or left) total annihilators.     

Laurent-Padé approximants to four kinds of Chebyshev polynomial expansions. Part II: Clenshaw-Lord type approximants

Laurent-Padé (Chebyshev) rational approximantsP _m (w, w ⁻¹)/Q _n (w, w ⁻¹) of Clenshaw-Lord type [2,1] are defined, such that the Laurent series ofP _m /Q _n matches that of a given functionf(w, w ⁻¹) up to terms of orderw ^±(m+n) , based only on knowledge of the Laurent series coefficients off up to terms inw ^±(m+n) . This contrasts with the Maehly-type approximants [4,5] defined and computed in part I of this paper [6], where the Laurent series ofP _m matches that ofQ _n f up to terms of orderw ^±(m+n ), but based on knowledge of the series coefficients off up to terms inw ^±(m+2n). The Clenshaw-Lord method is here extended to be applicable to Chebyshev polynomials of the 1st, 2nd, 3rd and 4th kinds and corresponding rational approximants and Laurent series, and efficient systems of linear equations for the determination of the Padé-Chebyshev coefficients are obtained in each case. Using the Laurent approach of Gragg and Johnson [4], approximations are obtainable for allm≥0,n≥0. Numerical results are obtained for all four kinds of Chebyshev polynomials and Padé-Chebyshev approximants. Remarkably similar results of formidable accuracy are obtained by both Maehly-type and Clenshaw-Lord type methods, thus validating the use of either.     

Minkowski spaces with extremal distance from the Euclidean space

It is proved that if the Banach-Mazur distance between ann-dimensional Minkowski spaceB andl ₂ ⁿ satisfiesd (B ₁ l ₂ ⁿ ) ≧c √n (for some constantc>0 and for bign) thenB contains anA(c)-isomorphic copy ofl ₁ ^k (fork ∼ log log logn). In the special cased (B ₁ l ₂ ⁿ ) = √n,B contains an isometric copy ofl ₁ ^k fork ∼ logn.     

Normal sequences for markov shifts and intrinsically ergodic subshifts

A construction of normal sequences, similar to Champernowne’s one, is obtained for Markov shifts and intrinsically ergodic subshifts. For eachn a set Ω _n ofn-blocks is selected. A normal sequence is constructed by first concatenating the blocks of Ω _n (in any order) and then concatenating the resultant finite sequences successively.     

Separating convex sets in the plane

Given a setA inR ² and a collectionS of plane sets, we say that a lineL separatesA fromS ifA is contained in one of the closed half-planes defined byL, while every set inS is contained in the complementary closed half-plane.We prove that, for any collectionF ofn disjoint disks inR ², there is a lineL that separates a disk inF from a subcollection ofF with at least (n–7)/4 disks. We produce configurationsH _n andG _n , withn and 2n disks, respectively, such that no pair of disks inH _n can be simultaneously separated from any set with more than one disk ofH _n , and no disk inG _n can be separated from any subset ofG _n with more thann disks.We also present a setJ _m with 3m line segments inR ², such that no segment inJ _m can be separated from a subset ofJ _m with more thanm+1 elements. This disproves a conjecture by N. Alonet al. Finally we show that ifF is a set ofn disjoint line segments in the plane such that they can be extended to be disjoint semilines, then there is a lineL that separates one of the segments from at least n/3+1 elements ofF.