Semiconvergence of extrapolated iterative methods for singular linear systems

In this paper, we discuss convergence of the extrapolated iterative methods for solving singular linear systems. A general principle of extrapolation is presented. The semiconvergence of an extrapolated method induced by a regular splitting and a nonnegative splitting is proved whenever the coefficient matrix A is a singular M-matrix with ‘property c’ and an irreducible singular M-matrix, respectively. Since the (generalized, block) JOR and AOR methods are respectively the extrapolated methods of the (generalized, block) Jacobi and SOR methods, so the semiconvergence of the (generalized, block) JOR and AOR methods for solving general singular systems are proved. Furthermore, the semiconvergence of the extrapolated power method, the (block) JOR, AOR and SOR methods for solving Markov chains are discussed.     

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     

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     

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.     

Semiconvergence of nonnegative splittings for singular matrices

Summary. In this paper, we discuss semiconvergence of the matrix splitting methods for solving singular linear systems. The concepts that a splitting of a matrix is regular or nonnegative are generalized and we introduce the terminologies that a splitting is quasi-regular or quasi-nonnegative. The equivalent conditions for the semiconvergence are proved. Comparison theorem on convergence factors for two different quasi-nonnegative splittings is presented. As an application, the semiconvergence of the power method for solving the Markov chain is derived. The monotone convergence of the quasi-nonnegative splittings is proved. That is, for some initial guess, the iterative sequence generated by the iterative method introduced by a quasi-nonnegative splitting converges towards a solution of the system from below or from above. Received August 19, 1997 / Revised version received August 20, 1998 / Published online January 27, 2000     

Block SOR methods for rank-deficient least-squares problems

Many papers have discussed preconditioned block iterative methods for solving full rank least-squares problems. However very few papers studied iterative methods for solving rank-deficient least-squares problems. Miller and Neumann (1987) proposed the 4-block SOR method for solving the rank-deficient problem. Here a 2-block SOR method and a 3-block SOR method are proposed to solve such problem. The convergence of the block SOR methods is studied. The optimal parameters are determined. Comparison between the 2-block SOR method and the 3-block SOR method is given also.     

Existence of Z-cyclic 3PTWh (p) for any Prime p≡ 1 (mod 4)

We show that a Z-cyclic triplewhist tournament on p players with three-person property, briefly 3PTWh(p), exists for any prime p≡ 1 (mod 4) with the only exceptions of p=5,13,17.     

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.     

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.     

Optimum first and second order extrapolations of Successive Overrelaxation type methods for certain classes of matrices

This paper deals with the iterative solution of the linear systemx=Bx+c when its Jacobi matrixB is weakly 2-cyclic consistently ordered and has a complex eigenvalue spectrum which lies on a straight-line segment. The optimization problem of the following three methods is considered and solved: i) The extrapolation of the optimum Successive Overrelaxation (SOR) ii) The second order extrapolation of a good SOR and iii) The second order extrapolation of the Gauss-Seidel method. In addition a variant of the second order methods considered, suitable for the solution of the system even ifB isnot necessarily weakly 2-cyclic consistently ordered, is proposed. Finally a reference to a theoretical comparison of the various optimum methods in the paper is made and their asymptotic convergence factors for selected eigenvalue spectra are illustrated in a Table in support of the theory developed.     

On parallel multisplitting methods for symmetric positive semidefinite linear systems

In this paper we propose some parallel multisplitting methods for solving consistent symmetric positive semidefinite linear systems, based on modified diagonally compensated reduction. The semiconvergence of the parallel multisplitting method is discussed. The results here generalize some known results for the nonsingular linear systems to the singular systems. Copyright © 2008 John Wiley & Sons, Ltd.     

Semiconvergence of parallel multisplitting methods for symmetric positive semidefinite linear systems

In this paper we construct some parallel relaxed multisplitting methods for solving consistent symmetric positive semidefinite linear systems, based on modified diagonally compensated reduction and incomplete factorizations. The semiconvergence of the parallel multisplitting method, relaxed multisplitting method and relaxed two‐stage multisplitting method are discussed. The results generalize some well‐known results for the nonsingular linear systems to the singular systems. Copyright © 2010 John Wiley & Sons, Ltd.     

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.     

New numerical methods and some applied aspects of the p-regularity theory

The theory of p-regularity is applied to optimization problems and to singular ordinary differential equations (ODE). The special variant of the method of the modified Lagrangian function proposed by Yu.G. Evtushenko for constrained optimization problems with inequality constraints is justified on the basis of the 2-factor transformation. An implicit function theorem is given for the singular case. This theorem is used to show the existence of solutions to a boundary value problem for a nonlinear differential equation in the resonance case. New numerical methods are proposed including the p-factor method for solving ODEs with a small parameter.     

Cyclic Functions in <Emphasis Type="Italic">L</Emphasis><Superscript><Emphasis Type="Italic">p</Emphasis></Superscript>(<Emphasis Type="Bold">R</Emphasis>), 1 \le <Emphasis Type="Italic">p</Emphasis> < \infty

Functions whose translates span L ^p (R) are called L ^p-cyclic functions. For a fixed p \memb [1, \infty], we construct Schwartz-class functions which are L ^r -cyclic for r > p and not L ^r - cyclic for r \le p. We then construct Schwartz-class functions which are L ^r -cyclic for r \ge p and not L ^r -cyclic for r < p. The constructions differ for p \memb (1, 2) and p > 2.     

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.     

Positive solutions for higher order singular p-Laplacian boundary value problems

This paper investigates 2m-th (m ≥ 2) order singular p-Laplacian boundary value problems, and obtains the necessary and sufficient conditions for existence of positive solutions for sublinear 2m-th order singular p-Laplacian BVPs on closed interval.     

Equivalent iterative methods for p-cyclic matrices

An overview is given of the simplifications which arise when p-cyclic systems are solved by iterative methods. Besides the classic iterative methods, we treat the Chebyshev semi-iterative method and the OR and MR variants of the class of Krylov subspace methods. Particular emphasis is given to equivalent iterations applied to the cyclically reduced system.     

A note on the spectral distribution of toeplitz matrices

An elementary and direct proof of the Szegö formula is given, for both eigen and singular values. This proof, which is based on tools from linear algebra and does not rely on the theory of Fourier series, simultaneously embraces multilevel Toeplitz matrices, block Toeplitz matrices and combinations of them. The assumptions on the generating

function f are as weak as possible; indeedf is a matrix-valued function of p variables, and it is only supposed to be integrable. In the case of singular values f(x), and hence the block p-level Toeplitz matrices it generates, are not even supposed to be square matrices. Moreover, in the asymptotic formulas for eigen and singular values the test functions involved are not required to have compact support.     

Optimal Parameters for 2-cyclic AOR

Assume A∈C^n×n is a 2-cyclic consistently ordered matrix and J is denoted as its associated block Jacobi iteration matrix. We consider the 2-cyclic AOR method for solving the consistent linear systems Ax=b. In the case that σ(J²) is either nonnegative or nonpositive, we give detailed discussion and derive definite expressions on optimal parameters and spectral radius by efficient method. Moreover, we give some numerical examples.