Optimal Semi-Iterative Methods for Complex SOR with Results from Potential Theory

We consider the application of semi-iterative methods (SIM) to the standard (SOR) method with complex relaxation parameter ω, under the following two assumptions: (1) the associated Jacobi matrix J is consistently ordered and weakly cyclic of index 2, and (2) the spectrum σ(J) of J belongs to a compact subset Σ of the complex plane , which is symmetric with respect to the origin. By using results from potential theory, we determine the region of optimal choice of for the combination SIM–SOR and settle, for a large class of compact sets Σ, the classical problem of characterising completely all the cases for which the use of the SIM-SOR is advantageous over the sole use of SOR, under the hypothesis that . In particular, our results show that, unless the outer boundary of Σ is an ellipse, SIM–SOR is always better and, furthermore, one of the best possible choices is an asymptotically optimal SIM applied to the Gauss–Seidel method. In addition, we derive the optimal complex SOR parameters for all ellipses which are symmetric with respect to the origin. Our work was motivated by recent results of M.Eiermann and R.S. Varga.Dedicated to Professor Richard S. Varga in recognition of his substantial contributions to the subject of the paper.     

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.     

Old and new from SOR

From the long history of Successive Over Relaxation (SOR) between the end of second world war and today three points are considered: (1) Classical results of Young and Varga are described. (2) It is shown how results on semiiterative methods can be used to derive these classical results in a unifying way and to compare SOR with other iterative methods. (3) In the last 15 years the application of SOR to compute the stationary distribution of a homogeneous Markov chain has been discussed. These results are reported, considering especially the term extended convergence introduced by Kontovasilis, Plemmons and Stewart.     

The Successive Over Relaxation Method (SOR) and Markov Chains

In the sixties SOR has been the working horse for the numerical solution of elliptic boundary problems; classical results for chosing the relaxation parameter have been derived by D. Young and R.S. Varga. In the last fifteen years SOR has been examined for the computation of the stationary distribution of Markov chains. In the paper there are pointed out similarities and differences compared with the application of SOR for elliptic boundary problems.     

RADICAL THEORY FOR SEMIRINGS

Abstract

In this article we continue investigations on a Kurosh-Amitsur radical theory for a universal class U of hemirings as introduced by O.M. Olson et al. We give some necessary and sufficient conditions that such a universal class U consists of all hemirings. Further we consider special and weakly special subclasses M of U which yield hereditary radical classes P = um of U. In this context we correct some statements in the papers of Olson et al. Moreover, a problem posed there concerning the equality of two radicals ?_∞(S) and ?^ε(S) and two similar ideals β_∞ (S) and β^ε(S) is widely solved. We prove ?_∞(S) ? ?^ε(S) = β^∞(S) = β^ε(S) and give necessary and sufficient conditions for equality in the first inclusion. This yields in particular that the weakly special class M_ε(U) is always semisimple, a result which is not true for the special class M_∞(U).     

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     

一类矩阵的AOR迭代收敛性分析及其与SOR迭代的比较

1 引言 许多实际问题最后常归结为解一个或一些矩阵的线性代数方程组Ax=b （1.1）这里讨论A为（1,1）相容次序矩阵的情形。     

DIRECT ITERATIVE METHODS FOR RANK DEFICIENT GENERALIZED LEAST SQUARES PROBLEMS

1. IntroductionThe generalized LS problemis frequently found in solving problems from statistics, engineering, economics, imageand signal processing. Here A e Rmxn with m 2 n, b E Re and W E Rmxm issymmetric positive definite. The large sparse rank deficient generalized LS problemsappeal in computational genetics when we consider mited linear model for tree oranimal genetics [2], [31, [5].Recentlyg Yuan [9] and [10], Yuan and lusem [11] considered direct iterative methodsfor the problem …     

On Hermitian nonnegative-definite solutions to matrix equations

In this note, for a system of q matrix equations of the form $$ A_i XA_i^* = B_i B_i^* ,i = 1,2,...,q, $$ we consider the problem of the existence of Hermitian nonnegative-definite solutions. We offer an alternative with simplification and regularity to the result on necessary and sufficient conditions for the above matrix equations with q = 2 to have a Hermitian nonnegative-definite solution obtained by Zhang [1], who proposed a revised version of Young et al. [2]. Moreover, we give a necessary condition for the general case and then put forward a conjecture, with which at least some special situations are in agreement.     

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     

On the convergence of inexact Newton methods for discrete-time algebraic Riccati equations

In this paper, we present a convergence analysis of the inexact Newton method for solving Discrete-time algebraic Riccati equations (DAREs) for large and sparse systems. The inexact Newton method requires, at each iteration, the solution of a symmetric Stein matrix equation. These linear matrix equations are solved approximatively by the alternating directions implicit (ADI) or Smith?s methods. We give some new matrix identities that will allow us to derive new theoretical convergence results for the obtained inexact Newton sequences. We show that under some necessary conditions the approximate solutions satisfy some desired properties such as the d-stability. The theoretical results developed in this paper are an extension to the discrete case of the analysis performed by Feitzinger et al. (2009) [8] for the continuous-time algebraic Riccati equations. In the last section, we give some numerical experiments.     

On the convergence of the MAOR method

In order to solve a linear system Ax = b, Hadjidimos et al. (1992) defined a class of modified AOR (MAOR) method, whose special case implies the MSOR method. In this paper, some sufficient and/or necessary conditions for convergence of the MAOR and MSOR methods will be achieved, when A is a two-cyclic matrix and when A is a Hermitian positive-definite matrix, an H-, L- or M-matrix, and a strictly or irreducibly diagonally dominant matrix. The convergence results on the MSOR method are better than some known theorems. The optimum parameters and the optimum spectral radii of the MAOR and MSOR methods are obtained, which also answers the open problem given by Hadjidimos et al.     

A new class of variational problems arising in the modeling of elastic multi-structures

Summary It is shown howelastic multi-structures that comprise substructures of possibly different dimensions (three-dimensional structures, plates, rods) are modeled bycoupled, pluri-dimensional, variational problems of a new type. Following recent work by the author, H. LeDret, and R. Nzengwa, we describe here in detail one such problem, which is simultaneously posed over a threedimensional open set with a slit and a two-dimensional open set. The numerical analysis of such problems is also discussed and finally, some numerical results are presented.Dedicated to R. S. Varga on the occasion of his sixtieth birthdayInvited lecture,Conference on Approximation Theory and Numerical Linear Algebra, in honor of Richard S. Varga on the occasion of his 60th birthday, March 30–April 1, 1989, Kent State University, Kent, USALaboratoire du Centre National de la Recherche Scientifique associé à l'Université Pierre et Marie Curie     

k-循环矩阵的最佳SOR方法

本文研究 K-循环矩阵的SOR迭代,提出一种确定最佳松弛因子的方法，应用和改进了Young和Eidson等人的结果，同时给出了计算实例．     

Intermediate rings between D+I And K [y1,…,yt]

Let R = k [y₁,…,y_t] be an affine domain (where k is a field) having krull dimension =n>0. Let I be a nonzero proper ideal of R and D be a subring of K. In section 1 we determine necessary and sufficient conditions in order that (S,R) is a 'lying over pair' where S = D+I. In section 2 we chaaracterize when S is a Maximal non-Noetherian subring of R. Further we determine when S is a maximal subring of R.     

More About Geršgorin‐type theorems

In the recent book of R.S. Varga, [3], one of two main recurring themes is that a nonsingular theorem for matrices gives rise to an equivalent eigenvalue inclusion set in the complex plane, and conversely. If such nonsingularity result can be extended via irreducibility, usually this can be used for obtaining more information about the boundary of the corresponding eigenvalue inclusion set. Here we will start with one of Geršgorin‐type theorem for eigenvalue inclusion, given in [1], (for which exists corresponding equivalent statement about nonsingularity of a particular class of matrices) and use it for proving necessary conditions for an eigenvalue to lie on the boundary of localization area. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Local convergence of alternating low-rank optimization methods with overrelaxation

The local convergence of alternating optimization methods with overrelaxation for low-rank matrix and tensor problems is established. The analysis is based on the linearization of the method which takes the form of an SOR iteration for a positive semidefinite Hessian and can be studied in the corresponding quotient geometry of equivalent low-rank representations. In the matrix case, the optimal relaxation parameter for accelerating the local convergence can be determined from the convergence rate of the standard method. This result relies on a version of Young's SOR theorem for positive semidefinite $2\times 2$ block systems.     

Regular splittings and monotone iteration functions

Summary In this paper we introduce the set of so-called monotone iteration functions (MI-functions) belonging to a given function. We prove necessary and sufficient conditions in order that a given MI-function is (in a precisely defined sense) at least as fast as a second one.Regular splittings of a function which were initially introduced for linear functions by R.S. Varga in 1960 are generating MI-functions in a natural manner.For linear functions every MI-function is generated by a regular splitting. For nonlinear functions, however, this is generally not the case.     

On the supports of functions

In this paper, finite difference and finite element methods are used with nonlinear SOR to solve the problems of minimizing strict convex functionals. The functionals are discretized by both methods and some numerical quadrature formula. The convergence of such discretization is guaranteed and will be discussed. As for the convergence of the iterative process, it is necessary to vary the relaxation parameter in each iterations. In addition, for the model catenoid problem, boundary grid refinements play an essential role in the proposed nonlinear SOR algorithm. Numerical results which illustrate the importance of the grid refinements will be presented.

     

A Stein-Rosenberg theorem for rectangular matrices

In the theory of iterative methods, the classical Stein-Rosenberg theorem can be viewed as giving the simultaneous convergence (or divergence) of the extrapolated Jacobi (JOR) matrix $\text{J}$_ω and the successive overrelaxation (SOR) matrix $\text{L}$_ω, in the case when the Jacobi matrix $\text{J}$₁ is nonegative. As has been established by Buoni and Varga, necessary and sufficient conditions for the simultaneous convergence (or divergence) of $\text{J}$_ω and $\text{L}$_ω have been established which do not depend on the assumption that $\text{J}$₁ is nonnegative. More recently, Buoni, Neumann, and Varga extended these results to the singular case, using the notion of semiconvergence. The aim here is to extend these results to consistent rectangular systems.