Optimality relationships forp-cyclic SOR

Summary The optimality question for blockp-cyclic SOR iterations discussed in Young and Varga is answered under natural conditions on the spectrum of the block Jacobi matrix. In particular, it is shown that repartitioning a blockp-cyclic matrix into a blockq-cyclic form,q, results in asymptotically faster SOR convergence for the same amount of work per iteration. As a consequence block 2-cyclic SOR is optimal under these conditions.Research supported in part by the US Air Force under Grant no. AFOSR-88-0285 and the National Science Foundation under grant no. DMS-85-21154 Present address: Boeing Computer Services, P.O. Box 24346, MS 7L-21, Seattle, WA 98124-0346, USA     

Generalization of Strang's Preconditioner with Applications to Toeplitz Least Squares Problems

In this paper, we propose a method to generalize Strang's circulant preconditioner for arbitrary n-by-n matrices A_n. The th column of our circulant preconditioner Sn is equal to the th column of the given matrix A_n. Thus if A_n is a square Toeplitz matrix, then Sn is just the Strang circulant preconditioner. When Sn is not Hermitian, our circulant preconditioner can be defined as . This construction is similar to the forward-backward projection method used in constructing preconditioners for tomographic inversion problems in medical imaging. We show that if the matrix A_n has decaying coefficients away from the main diagonal, then is a good preconditioner for An. Comparisons of our preconditioner with other circulant-based preconditioners are carried out for some 1-D Toeplitz least squares problems: min ∥ b - Ax∥₂. Preliminary numerical results show that our preconditioner performs quite well, in comparison to other circulant preconditioners. Promising test results are also reported for a 2-D deconvolution problem arising in ground-based atmospheric imaging.     

LU decomposition of M-matrices by elimination without pivoting

It is shown that if A or ?A is a singular M-matrix satisfying the generalized diagonal dominance condition y^TA?0 for some vector y? 0, then A can be factored into A = LU by a certain elimination algorithm, where L is a lower triangular M-matrix with unit diagonal and U is an upper triangular M-matrix. The existence of LU decomposition of symmetric permutations of A and for irreducible M-matrices and symmetric M-matrices follow as colollaries. This work is motivated by applications to the solution of homogeneous systems of linear equations Ax = 0, where A or ?A is an M-matrix. These applications arise, e.g., in the analysis of Markov chains, input-output economic models, and compartmental systems. A converse of the theorem metioned above can be established by considering the reduced normal form of A.     

M-matrices leading to semiconvergent splittings

An M-matrix as defined by Ostrowski is a matrix that can be split into A = sI ? B, s > 0, B ? 0 with s ? ρ(B), the spectral radius of B. M-matrices with the property that the powers of T = (1/s)B converge for some s are studied and are characterized here in terms of the nonnegativity of the group generalized inverse of A on the range space of A, extending the well-known property that A^{? 1} ? 0 whenever A is nonsingular.     

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     

Direct iterative methods for least-squares solutions to singular operator equations

Least-squares consistency and convergence of iterative schemes are investigated for singular operator equations (1) Tx = f, where T is a bounded linear operator from a Banach space to a Hilbert space. A direct splitting of T into T = M ? N is then used to obtain the iterative formula (2) x^(k+1) = M^?Nx^(k) + M^?f, where M^? is a least-squares generalized inverse of M. Cone monotonicity is used to investigate convergence of (2) to a least-squares solutions to (1), extending results given for the matrix case given by Berman and Plemmons.     

M-matrix characterizations.I—nonsingular M-matrices

The purpose of this survey is to classify systematically a widely ranging list of characterizations of nonsingular M-matrices from the economics and mathematics literatures. These characterizations are grouped together in terms of their relations to the properties of (1) positivity of principal minors, (2) inverse-positivity and splittings, (3) stability and (4) semipositivity and diagonal dominance. A list of forty equivalent conditions is given for a square matrix A with nonpositive off-diagonal entries to be a nonsingular M-matrix. These conditions are grouped into classes in order to identify those that are equivalent for arbitrary real matrices A. In addition, other remarks relating nonsingular M-matrices to certain complex matrices are made, and the recent literature on these general topics is surveyed.     

Groups of binary relations

It was shown in [3] that every finite group is the maximal subgroup of a semigroupB _x of all binary relations on some finite set X. This result is extended here to arbitrary groups.     

Backward error analysis for linear systems associated with inverses ofH-matrices

In this paper, bounds on the growth factors resulting from Gaussian elimination applied to inverses ofH-matrices are developed and investigated. These bounds are then used in the error analysis for solving linear systemsAx =b whose coefficient matricesA are of this type. For each such system our results show that the Gaussian elimination without pivoting can proceed safely provided that the elements of the inverse of a certainM-matrix (associated with the coefficient matrixA) are not excessively large. We exhibit a particularly satisfactory situation for the special case whenA itself is an inverse of anM-matrix. Part of the first section of this paper is devoted to a discussion on some results of de Boor and Pinkus for the stability of triangular factorizations of systemsAx =b, whereA is a nonsingular totally nonnegative matrix, and to the explanation of why the analysis of de Boor and Pinkus is not applicable to the case when the coefficient matrixA is an inverse of anM-matrix.Research supported in part by NSF Grant MCS-8102114.Research supported in part by the U.S. Army Research Office under contract No. DAAG-29-81-K-0132 and in part by NSF Grant MCS-8219500.