Optimal successive overrelaxation iterative methods for P-cyclic matrices

Summary We consider linear systems whose associated block Jacobi matricesJ _p are weakly cyclic of indexp. In a recent paper, Pierce, Hadjidimos and Plemmons [13] proved that the block two-cyclic successive overrelaxation (SOR) iterative method is numerically more effective than the blockq-cyclic SOR-method, 2<qp, if the eigenvalues ofJ _p ^p are either all non-negative or all non-positive. Based on the theory of stationaryp-step methods, we give an alternative proof of their theorem. We further determine the optimal relaxation parameter of thep-cyclic SOR method under the assumption that the eigenvalues ofJ _p ^p are contained in a real interval, thereby extending results due to Young [19] (for the casep=2) and Varga [15] (forp>2). Finally, as a counterpart to the result of Pierce, Hadjidimos and Plemmons, we show that, under this more general assumption, the two-cyclic SOR method is not always superior to theq-cyclic SOR method, 2<qp.Dedicated to R. S. Varga on the occasion of his 60th birthdayResearch supported in part by the Deutsche Forschungsgemeinschaft     

Semiconvergence of block SOR method for singular linear systems with p-cyclic matrices

In this paper, we discuss semiconvergence of the block SOR method for solving singular linear systems with p-cyclic matrices. Some sufficient conditions for the semiconvergence of the block SOR method for solving a general p-cyclic singular system are proved.     

Precise domains of convergence for the block SSOR method associated withp-cyclic matrices

We apply Rouché's theorem to the functional equation relating the eigenvalues of theblock symmetric successive overrelaxation (SSOR) matrix with those of the block Jacobi iteration matrix found by Varga, Niethammer, and Cai, in order to obtain precise domains of convergence for the block SSOR iteration method associated withp-cyclic matricesA, p3. The intersection of these domains, taken over all suchp's, is shown to coincide with the exact domain of convergence of thepoint SSOR iteration method associated withH-matricesA. The latter domain was essentially discovered by Neumaier and Varga, but was recently sharpened by Hadjidimos and Neumann.Research supported in part by NSF Grant DMS 870064.     

Exact SOR convergence regions for a general class ofp-cyclic matrices

Linear systems whose associated block Jacobi iteration matrixB is weakly cyclic generated by the cyclic permutation = (₁,₂,..., _p ) in the spirit of Li and Varga are considered. Regions of convergence for the corresponding blockp-cyclic SOR method are derived and the exact convergence domains for real spectra, (B ^p ), of the same sign are obtained. Moreover, analytical expressions for two special cases forp = 5 are given and numerical results are presented confirming the theory developed. The tools used for this work are mainly from complex analysis and extensive use of (asteroidal) hypocycloids in the complex plane is made to produce our results.This work was supported in part by AFOSR grant F49620-92-J-0069 and NSF grant 9202536-CCR.     

Extrapolated Gauss-Seidel I and SOR methods for least-squares problems

Summary Recently, special attention has been given in the literature, to the problems of accurately computing the least-squares solution of very largescale over-determined systems of linear equations which occur in geodetic applications. In particular, it has been suggested that one can solve such problems iteratively by applying the block SOR (Successive Overrelaxation) and EGS1 (Extrapolated Gauss Seidel 1) plus semi-iterative methods to a linear system with coefficient matrix 2-cyclic or 3-cyclic. The comparison of 2-block SOR and 3-block SOR was made in [1] and showed that the 2-block SOR is better. In [6], the authors also proved that 3-block EGS1-SI is better than 3-block SOR. Here, we first show that the 2-block DJ (Double Jacobi)-SI, GS-SI and EGS1-SI methods are equivalent and all of them are equivalent to the 3-block EGS1-SI method; then, we prove that the composite methods and 2-block SOR have the same asymptotic rate of convergence, but the former has a better average rate of convergence; finally, numerical experiments are reported, and confirm that the 3-block EGS1-SI is better than the 2-block SOR.     

Matrix completion problems of block type

The solvability, either unconditional or under certain conditions, is proved for three matrix completion problems of block type. Being a problem of block type means that a matrixA must be constructed with a prescribed characteristic polynomial and one or several blocks in a 2 × 2 partition also prescribed. For the problems under analysis, one prescribes, respectively, (a) the blockA ₁₂; (b) the blockA ₁₁; (c) the blocksA ₁₁ andA ₁₂. We discuss our experience in implementing the algorithms that solve the problems above as procedures in the symbolic computation system MAPLE. Translated fromMatematicheskie Zametki, Vol. 67, No. 6, pp. 863–873, June, 2000. The first author was supported by the Russian Foundation for Basic Research under grant No. 97-01-00927.     

Improving two theorems of bose on difference families

In [2] R. C. Bose gives a sufficient condition for the existence of a (q, 5, 1) difference family in (GF(q), +)—where q ≡ 1 mod 20 is a prime power — with the property that every base block is a coset of the 5th roots of unity. Similarly he gives a sufficient condition for the existence of a (q, 4, 1) difference family in (GF(q, +)—where q ≡ 1 mod 12 is a prime power — with the property that every base block is the union of a coset of the 3rd roots of unity with zero. In this article we replace the mentioned sufficient conditions with necessary and sufficient ones. As a consequence, we obtain new infinite classes of simple difference families and hence new Steiner 2-designs with block sizes 4 and 5. In particular, we get a (p^4α, 5, 1)-DF for any odd prime p ≡ 2, 3 (mod 5), and a (p^2α, 4, 1)-DF for any odd prime p ≡ 2 (mod 3). © 1995 John Wiley & Sons, Inc.     

A note on preconditional diagonally dominant matrices

This note points out that the main results of [Appl. Math. Comput. 114 (2000) 255] is not true. We show that (1) Theorem 2.1 in [Appl. Math. Comput. 114 (2000) 255] is well known, (2) There are no nonsingular matrices satisfying the sufficient conditions for ensuring diagonally dominance given in Theorem 3.1, and (3) Theorem 4.1 for preconditioning p-cyclic matrices is not true. We also prove that p-cyclic matrices can be column diagonally preconditioned, with a special row permutation if required, to be row diagonally dominant under some assumptions.     

Relative Position,Sequences and Operators in Banach Spaces

A (p + q) × (p + q) matrix-valued inner function S in the unit disc ?? is called (p, q)-type Arov-inner if in the block partition . the p × p diagonal block S₁₁ and the q × q diagonal block S₂₂ are outer matrix-valued functions. A holomorphic p × q matrix-valued function f in ?? is called Arov-completable if there is a (p, q)-type Arov-inner function S such that S₁₂ = f Arov-completability of a given p × q Schur function f is characterized in terms of a (p + q)-variate stationary sequence (X_{n) ? Z}) in Hilbert space which is naturally associated with f. The necessary and sufficient condition for Arov-completability is an orthogonality condition for certain backward and forward innovation vectors generated by (X_{n) ? Z}.     

An application ofp-cyclic matrices,for solving periodic parabolic problems

Summary Finite-difference equations for the steady-state solution of a parabolic equation with periodic boundary conditions producep-cyclic matrices, wherep can be arbitrarily large. The periodic solution can be found by applying S.O.R. to the equations with thep-cyclic matrix, and this procedure is more economical than the standard step-by-step procedures for solving the parabolic equation. Bounds for the discretization error are found in terms of bounds for the known second derivatives of the boundary values.     

A condition for arcs and MDS codes

There is polynomial function X _q in the entries of an m × m(q − 1) matrix over a field of prime characteristic p, where q = p ^h is a power of p, that has very similar properties to the determinant of a square matrix. It is invariant under multiplication on the left by a non-singular matrix, and under permutations of the columns. This gives a way to extend the invariant theory of sets of points in projective spaces of prime characteristic, to make visible hidden structure. There are connections with coding theory, permanents, and additive bases of vector spaces.     

Compositions of isometric immersions¶in higher codimension

Given a submanifold M ⁿ of Euclidean space ℝ ^{n + p} with codimension p≤6, under generic conditions on its second fundamental form, we show that any other isometric immersion of M ⁿ into ℝ ^{n + p + q} , 0≤q≤n− 2p−1 and 2q≤n+ 1 if q≥ 5, must be locally a composition of isometric immersions. This generalizes several previous results on rigidity and compositions of submanifolds. We also provide conditions under which our result is global. 14 March 2001     

On Distinguished Solutions of Truncated Matricial Hamburger Moment Problems

We study two slightly different versions of the truncated matricial Hamburger moment problem. A central topic is the construction and investigation of distinguished solutions of both moment problems under consideration. These solutions turn out to be nonnegative Hermitian q × q Borel measures on the real axis which are concentrated on a finite number of points. These points and the corresponding masses will be explicitly described in terms of the given data. Furthermore, we investigate a particular class of sequences (s_j)^∞_{j = 0} of complex q × q matrices for which the corresponding infinite matricial Hamburger moment problem has a unique solution. Our approach is mainly algebraic. It is based on the use of particular matrix polynomials constructed from a nonnegative Hermitian block Hankel matrix. These matrix polynomials are immediate generalizations of the monic orthogonal matrix polynomials associated with a positive Hermitian block Hankel matrix. We generalize a classical theorem due to Kronecker on infinite Hankel matrices of finite rank to block Hankel matrices and discuss its consequences for the nonnegative Hermitian case.     

Construction of Z-cyclic triple whist tournaments

Let p = 2^kt + 1 be a prime where t>1 is an odd integer, k ≥ 2. Methods of constructing a Z-cyclic triple whist tournament TWh(p) are given. By such methods we construct a Z-cyclic TWh(p) for all primes p,p≡1(mod 4), 29 ≤ p ≤ 16097, except p = 257. Let p_i = 2t_i + 1,q = 2t₀ + 3 be primes where t_i;i = 0,1,…, n are odd > 1 and k_i are integers ≥2. We prove that if Z-cyclic TWh(p_i) and TWh(q + 1) exist then Z-cyclic TWh(∏ⁿ_{i = 1} p_i) and TWh(q∏ⁿ_{i = 1} p_i + 1) exist. © 1996 John Wiley & Sons, Inc.     

Convergence of a direct-iterative method for large-scale least-squares problems

In 1975 Chen and Gentleman suggested a 3-block SOR method for solving least-squares problems, based on a partitioning scheme for the observation matrix A into

$\text{A=}\text{A}{}_1\text{A}{}_2$

where A₁ is square and nonsingular. In many cases A₁ is obvious from the nature of the problem. This combined direct-iterative method was discussed further and applied to angle adjustment problems in geodesy, where A₁ is easily formed and is large and sparse, by Plemmons in 1979. Recently, Niethammer, de Pillis, and Varga have rekindled interest in this method by correcting and extending the SOR convergence interval. The purpose of our paper is to discuss an alternative formulation of the problem leading to a 2-block SOR method. For this formulation it is shown that the resulting direct-iterative method always converges for sufficiently small SOR parameter, in contrast to the 3-block formulation. Formulas for the optimum SOR parameter and the resulting asymptotic convergence factor, based upon 6A₂A^-1₁6₂, are given. Furthermore, it is shown that this 2-cyclic block SOR method always gives better convergence results than the 3-cyclic one for the same amount of work per iteration. The direct part of the algorithm requires only a sparse-matrix factorization of A₁. Our purpose here is to establish theoretical convergence results, in line with the purpose of the recent paper by Niethammer, de Pillis, and Varga. Practical considerations of choosing A₁ in certain applications and of estimating the resulting 6A₂A^-1₁6₂ will be addressed elsewhere.     

An iterative substructuring algorithm for equilibrium equations

Summary The topic of iterative substructuring methods, and more generally domain decomposition methods, has been extensively studied over the past few years, and the topic is well advanced with respect to first and second order elliptic problems. However, relatively little work has been done on more general constrained least squares problems (or equivalent formulations) involving equilibrium equations such as those arising, for example, in realistic structural analysis applications. The potential is good for effective use of iterative algorithms on these problems, but such methods are still far from being competitive with direct methods in industrial codes. The purpose of this paper is to investigate an order reducing, preconditioned conjugate gradient method proposed by Barlow, Nichols and Plemmons for solving problems of this type. The relationships between this method and nullspace methods, such as the force method for structures and the dual variable method for fluids, are examined. Convergence properties are discussed in relation to recent optimality results for Varga's theory ofp-cyclic SOR. We suggest a mixed approach for solving equilibrium equations, consisting of both direct reduction in the substructures and the conjugate gradient iterative algorithm to complete the computations.Dedicated to R. S. Varga on the occasion of his 60th birthdayResearch completed while pursuing graduate studies sponsored by the Department of Mathematical Sciences, US Air Force Academy, CO, and funded by the Air Force Institute of Technology, WPAFB, OHResearch supported by the Air Force under grant no. AFOSR-88-0285 and by the National Science Foundation under grant no. DMS-89-02121     

A representation theorem and Z-cyclic whist tournaments

Let E denote the group of units (i.e., the reduce set of residues) in the ring Z. Here we consider q,p to be primes, q ≡ 3 (mod 4), q ? 7, p ≡ 1 (mod 4). Let W denote a common primitive root of 3, q, and p². If H denotes the (normal) subgroup of E that is generated by {?1, W}, we show that the factor group E/H is cyclic by demonstrating the existence of an element x in E such that the coset xH has order equal to |E/H|. This order is given by gcd(p^n?1(p ? 1),q ? 1). This representation of E/H is exploited via an appropriate construction to produce Z-cyclic whist tournaments for 3qpⁿ players. Consequently these results extend those of an early study of Wh(3qpⁿ) that was restricted to gcd(p^n?1(p ? 1),q ? 1) = 2. © 1995 John Wiley & Sons, Inc.     

Domains of divergence of the USSOR method applied onp-cyclic matrices

Summary Using a recently derived classical type general functional equation, relating the eigenvalues of a weakly cyclic Jacobi iteration matrix to the eigenvalues of its associated Unsymmetric Successive Overrelaxation (USSOR) iteration matrix, we obtain bounds for the convergence of the USSOR method, when applied to systems with ap-cyclic coefficient matrix.     

On the asymptotic existence of complex Hadamard matrices

Let N = N(q) be the number of nonzero digits in the binary expansion of the odd integer q. A construction method is presented which produces, among other results, a block circulant complex Hadamard matrix of order 2^αq, where α ≥ 2N - 1. This improves a recent result of Craigen regarding the asymptotic existence of Hadamard matrices. We also present a method that gives complex orthogonal designs of order 2^α+1q from complex orthogonal designs of order 2^α. We also demonstrate the existence of a block circulant complex Hadamard matrix of order 2^βq, where © 1997 John Wiley & Sons, Inc. J Combin Designs 5:319–327, 1997     

Essential Norms of Composition Operators

We obtain simple estimates for the essential norm of a composition operator acting from the Hardy space H ^p to H ^q , p > q, in one or several variables. When p = and q = 2 our results give an exact formula for the essential norm.