Band Toeplitz preconditioners for block Toeplitz systems

We consider the solutions of block Toeplitz systems with Toeplitz blocks by the preconditioned conjugate gradient (PCG) method. Here the block Toeplitz matrices are generated by nonnegative functions f(x,y). We use band Toeplitz matrices as preconditioners. The generating functions g(x,y) of the preconditioners are trigonometric polynomials of fixed degree and are determined by minimizing (f − g)/f∞. We prove that the condition number of the preconditioned system is O(1). An a priori bound on the number of iterations for convergence is obtained.     

A survey of some estimates of eigenvalues and condition numbers for certain preconditioned matrices

Eigenvalue and condition number estimates for preconditioned iteration matrices provide the information required to estimate the rate of convergence of iterative methods, such as preconditioned conjugate gradient methods. In recent years various estimates have been derived for (perturbed) modified (block) incomplete factorizations. We survey and extend some of these and derive new estimates. In particular we derive upper and lower estimates of individual eigenvalues and of condition number. This includes a discussion that the condition number of preconditioned second order elliptic difference matrices is O(h⁻¹). Some of the methods are applied to compute certain parameters involved in the computation of the preconditioner.     

A note on minimum degree conditions for supereulerian graphs

A graph is called supereulerian if it has a spanning closed trail. Let G be a 2-edge-connected graph of order n such that each minimal edge cut SE(G) with |S|3 satisfies the property that each component of G−S has order at least (n−2)/5. We prove that either G is supereulerian or G belongs to one of two classes of exceptional graphs. Our results slightly improve earlier results of Catlin and Li. Furthermore, our main result implies the following strengthening of a theorem of Lai within the class of graphs with minimum degree δ4: If G is a 2-edge-connected graph of order n with δ(G)4 such that for every edge xyE(G) , we have max{d(x),d(y)}(n−2)/5−1, then either G is supereulerian or G belongs to one of two classes of exceptional graphs. We show that the condition δ(G)4 cannot be relaxed.     

On the planarity of jump graphs

For a graph G of size m1 and edge-induced subgraphs F and H of size k (1km), the subgraph H is said to be obtained from F by an edge jump if there exist four distinct vertices u,v,w, and x in G such that uvE(F), wxE(G)−E(F), and H=F−uv+wx. The minimum number of edge jumps required to transform F into H is the k-jump distance from F to H. For a graph G of size m1 and an integer k with 1km, the k-jump graph J_k(G) is that graph whose vertices correspond to the edge-induced subgraphs of size k of G and where two vertices of J_k(G) are adjacent if and only if the k-jump distance between the corresponding subgraphs is 1. All connected graphs G for which J₂(G) is planar are determined.     

A new t-norm

We define a new t-norm, and t-conorm, whose domain is usually a restricted subset of [0, 1] x [0, 1], with one parameter, the correlation coefficient between the membership values, which ranges from −1 to 1. We then investigate their properties showing at one extreme they equal the Zadeh operators (max, min), and at the other extreme they produce the Lukasiewicz operators (max(a + b - l, 0), min(a + b,1)).     

Designs with no three mutually disjoint blocks

Let D(v,b,r,k,λ) be any quasi-symmetric block design with block intersection numbers 0 and y. Suppose D has no three mutually disjoint blocks. We show that for a given value of y, there are only finitely many parameter sets of such designs. Moreover, the ‘extremal’ designs D have one of the following parameter sets: (1) v = 4y, k = 2y, λ = 2y − 1 (y 2) (2) v = y(y²+3y+1), k = y(y+1), λ =y²+y−1(y2) (3) v = (y+1)(y²+2y−1), k = y(y+1), λ =y² (y2) A computer search revealed only three parameter sets in the range 1y199, which are not of the above types.     

Convergence estimates for an optimized Schwarz method for PDEs with discontinuous coefficients

Optimized Schwarz methods form a class of domain decomposition methods for the solution of elliptic partial differential equations. When the subdomains are overlapping or nonoverlapping, these methods employ the optimal value of parameter(s) in the boundary condition along the artificial interface to accelerate its convergence. In the literature, the analysis of optimized Schwarz methods rely mostly on Fourier analysis and so the domains are restricted to be regular (rectangular). As in earlier papers, the interface operator can be expressed in terms of Poincaré–Steklov operators. This enables the derivation of an upper bound for the spectral radius of the interface operator on essentially arbitrary geometry. The problem of interest here is a PDE with a discontinuous coefficient across the artificial interface. We derive convergence estimates when the mesh size h along the interface is small and the jump in the coefficient may be large. We consider two different types of Robin transmission conditions in the Schwarz iteration: the first one leads to the best estimate when h is small, whereas for the second type, we derive a convergence estimate inversely proportional to the jump in the coefficient. This latter result improves upon the rate of popular domain decomposition methods such as the Neumann–Neumann method or FETI-DP methods, which was shown to be independent of the jump. In memory of Gene Golub.     

Rate of Convergence for some constraint decomposition methods for nonlinear variational inequalities

Summary. Some general subspace correction algorithms are proposed for a convex optimization problem over a convex constraint subset. One of the nontrivial applications of the algorithms is the solving of some obstacle problems by multilevel domain decomposition and multigrid methods. For domain decomposition and multigrid methods, the rate of convergence for the algorithms for obstacle problems is of the same order as the rate of convergence for jump coefficient linear elliptic problems. In order to analyse the convergence rate, we need to decompose a finite element function into a sum of functions from the subspaces and also satisfying some constraints. A special nonlinear interpolation operator is introduced for decomposing the functions. Received December 13, 2001 / Revised version received February 19, 2002 / Published online June 17, 2002 This work was partially supported by the Norwegian Research Council under projects 128224/431 and SEP-115837/431.     

A faster 2-approximation algorithm for the minmax p-traveling salesmen problem on a tree

Given an edge-weighted tree T and an integer p1, the minmax p-traveling salesmen problem on a tree T asks to find p tours such that the union of the p tours covers all the vertices. The objective is to minimize the maximum of length of the p tours. It is known that the problem is NP-hard and has a (2−2/(p+1))-approximation algorithm which runs in O(p^p−1n^p−1) time for a tree with n vertices. In this paper, we consider an extension of the problem in which the set of vertices to be covered now can be chosen as a subset S of vertices and weights to process vertices in S are also introduced in the tour length. For the problem, we give an approximation algorithm that has the same performance guarantee, but runs in O((p−1)!·n) time.     

A doubly cyclic channel assignment problem

A standard model for radio channel assignment involves a set V of sites, the set {0,1,2,…} of channels, and a constraint matrix (w(u, v)) specifying minimum channel separations. An assignment f:V→{0,1,2,…} is feasible if the distance f(u) − f(v)w(u, v) for each pair of sites u and v. The aim is to find the least k such that there is a feasible assignment using only the k channels 0, 1, …, k − 1, and to find a corresponding optimal assignment.

We consider here a related problem involving also two cycles. There is a given cyclic order τ on the sites, and feasible assignments f must also satisfy f(τv) f(v) for all except one site v. Further, the channels are taken to be evenly spaced around a circle, so that if the k channels 0, 1, …, k − 1 are available then the distance between channels i and j is the minimum of ¦i − j¦ and k − ¦i − j¦. We show how to find a corresponding optimal channel assignment in O(¦V¦³) steps.     

A TAGE iterative method for the solution of non-linear singular two point boundary value problems using a sixth order discretization

We report two parameter alternating group explicit (TAGE) iteration method to solve the tri-diagonal linear system derived from a new finite difference discretization of sixth order accuracy of the two point singular boundary value problem , 0 < r < 1,  = 1 and 2 subject to boundary conditions u(0) = A, u(1) = B, where A and B are finite constants. We also discuss Newton-TAGE iteration method for the sixth order numerical solution of two point non-linear boundary value problem. The proof for the convergence of the TAGE iteration method when the coefficient matrix is real and unsymmetric is discussed. Numerical results are presented to illustrate the proposed iterative methods.     

On-line algorithms for ordered sets and comparability graphs

We discuss several results concerning on-line algorithms for ordered sets and comparability graphs. The main new result is on the problem of on-line transitive orientation. We view on-line transitive orientation of a comparability graph G as a two-person game. In the ith round of play, 1 i | V(G)|, player A names a graph G_i such that G_i is isomorphic to a subgraph of G, |V(G_i)| = i, and G_i−1 is an induced subgraph of G_i if i> 1. Player B must respond with a transitive orientation of G_i which extends the transitive orientation given to G_i−1 in the previous round of play. Player A wins if and only if player B fails to give a transitive orientation to G_i for some i, 1 i |V(G)|. Our main result shows that player A has at most three winning moves. We also discuss applications to on-line clique covering of comparability graphs, and we mention some open problems.     

A Helly-type theorem for higher-dimensional transversals

We prove that a collection of compact convex sets of bounded diameters in that is unbounded in k independent directions has a k-flat transversal for k<d if and only if every d+1 of the sets have a k-transversal. This result generalizes a theorem of Hadwiger(–Danzer–Grünbaum–Klee) on line transversals for an unbounded family of compact convex sets. It is the first Helly-type theorem known for transversals of dimension between 1 and d−1.     

An $L^{\infty}$ Second Order Cartesian Method for 3D Anisotropic Interface Problems

A second order accurate method in the infinity norm is proposed for general three dimensional anisotropic elliptic interface problems in which the solution and its derivatives, the coefficients, and source terms all can have finite jumps across one or several arbitrary smooth interfaces. The method is based on the 2D finite element-finite difference (FE-FD) method but with substantial differences in method derivation, implementation, and convergence analysis. One of challenges is to derive 3D interface relations since there is no invariance anymore under coordinate system transforms for the partial differential equations and the jump conditions. A finite element discretization whose coefficient matrix is a symmetric semi-positive definite is used away from the interface; and the maximum preserving finite difference discretization whose coefficient matrix part is an M-matrix is constructed at irregular elements where the interface cuts through. We aim to get a sharp interface method that can have second order accuracy in the point-wise norm. We show the convergence analysis by splitting errors into several parts. Nontrivial numerical examples are presented to confirm the convergence analysis.     

ContributionsSign-balanced covering matrices

A q × n array with entries from 0, 1,…,q − 1 is said to form a difference matrix if the vector difference (modulo q) of each pair of columns consists of a permutation of [0, 1,… q − 1]; this definition is inverted from the more standard one to be found, e.g., in Colbourn and de Launey (1996). The following idea generalizes this notion: Given an appropriate δ (-[−1, 1]^t, a λq × n array will be said to form a (t, q, λ, Δ) sign-balanced matrix if for each choice C₁, C₂,…, C_t of t columns and for each choice = (₁,…,_t) Δ of signs, the linear combination ∑_j=1^t _jC_j contains (mod q) each entry of [0, 1,…, q − 1] exactly λ times. We consider the following extremal problem in this paper: How large does the number k = k(n, t, q, λ, δ) of rows have to be so that for each choice of t columns and for each choice (₁, …, _t) of signs in δ, the linear combination ∑_j=1^t _jC_j contains each entry of [0, 1,…, q t- 1] at least λ times? We use probabilistic methods, in particular the Lovász local lemma and the Stein-Chen method of Poisson approximation to obtain general (logarithmic) upper bounds on the numbers k(n, t, q, λ, δ), and to provide Poisson approximations for the probability distribution of the number W of deficient sets of t columns, given a random array. It is proved, in addition, that arithmetic modulo q yields the smallest array - in a sense to be described.     

Complementarity forms of theorems of Lyapunov and Stein, and related results

The well-known Lyapunov's theorem in matrix theory / continuous dynamical systems asserts that a (complex) square matrix A is positive stable (i.e., all eigenvalues lie in the open right-half plane) if and only if there exists a positive definite matrix X such that AX+XA^* is positive definite. In this paper, we prove a complementarity form of this theorem: A is positive stable if and only if for any Hermitian matrix Q, there exists a positive semidefinite matrix X such that AX+XA^*+Q is positive semidefinite and X[AX+XA^*+Q]=0. By considering cone complementarity problems corresponding to linear transformations of the form I−S, we show that a (complex) matrix A has all eigenvalues in the open unit disk of the complex plane if and only if for every Hermitian matrix Q, there exists a positive semidefinite matrix X such that X−AXA^*+Q is positive semidefinite and X[X−AXA^*+Q]=0. By specializing Q (to −I), we deduce the well known Stein's theorem in discrete linear dynamical systems: A has all eigenvalues in the open unit disk if and only if there exists a positive definite matrix X such that X−AXA^* is positive definite.     

The streamline-diffusion method for nonconforming Qrot1 elements on rectangular tensor-product meshes

When the streamline–diffusion finite element method isapplied to convection–diffusion problems using nonconformingtrial spaces, it has previously been observed that stabilityand convergence problems may occur. It has consequently beenproposed that certain jump terms should be added to the bilinearform to obtain the same stability and convergence behaviouras in the conforming case. The analysis in this paper showsthat for the Q^rot₁ 1 element on rectangular shape-regular tensor-productmeshes, no jump terms are needed to stabilize the method. Inthis case moreover, for smooth solutions we derive in the streamline–diffusionnorm convergence of order h^3/2 (uniformly in the diffusion coefficientof the problem), where h is the mesh diameter. (This estimateis already known for the conforming case.) Our analysis alsoshows that similar stability and convergence results fail tohold true for analogous piecewise linear nonconforming elements.     

H least-squares method for the velocity–pressure–stress formulation of Stokes equations

This paper studies the discrete H⁻¹-norm least-squares method for the incompressible Stokes equations based on the velocity–pressure–stress formulation by the least-squares functional defined as the sum of L²-norms and H⁻¹-norm of the residual equations. Some computational experiments by multigrid method and preconditioning conjugate gradient method (PCGM) on this method are shown by taking efficient and β in the discrete solution operator T_h=h²I+βB_h corresponding to the minus one norm. We also propose a new method and compare it with PCGM and multigrid method through the analysis of numerical experiments depending on the choice of β.     

Graphs having distance-n domination number half their order

For any positive integer n and any graph G a set D of vertices of G is a distance-n dominating set, if every vertex vV(G)−D has exactly distance n to at least one vertex in D. The distance-n domination number γ_=n(G) is the smallest number of vertices in any distance-n dominating set. If G is a graph of order p and each vertex in G has distance n to at least one vertex in G, then the distance-n domination number has the upper bound p/2 as Ore's upper bound on the classical domination number. In this paper, a characterization is given for graphs having distance-n domination number equal to half their order, when the diameter is greater or equal 2n−1. With this result we confirm a conjecture of Boland, Haynes, and Lawson.     

The modified quadrature method for classical pseudodifferential equations of negative order on smooth closed curves

In this article we present and analyze the modified quadrature method for strongly elliptic boundary integral equations of negative order on smooth closed curves. The method employs a modification that extracts the singularity appearing in the kernel or in some of its derivatives. Moreover, the composite trapezoidal rule is used for approximation of the integral. The modified quadrature method is proved to have the maximal rate O(h^−β+1) of convergence for operators of order β < 0 in general, and O(h^−β+2) for a large class of operators appearing in applications. Some numerical experiments confirming our theoretical results are also presented.