A note on the convergence of the MAOR method

The MAOR method as a generalization of the well-known MSOR method was introduced by Hadjidimos et al. (Appl. Numer. Math. 10 (1992) 115–127) and investigated in Y. Song (J. Comput. Appl. Math. 79 (1997) 299–317) where some convergence results for the case when matrix of the system is strictly diagonally dominant are obtained. In this paper we shall improve these results.     

On the convergence of the modified overrelaxation method

The modified overrelaxation (MSOR) method is applied to a linear system Ax=b, where A has property A. We get bounds for the spectral radius of the iteration matrix of this method, and we achieve convergence conditions for the MSOR method when A is strictly diagonally dominant. We extend our conclusions to another kind of matrices—H,L,M or Stieltjes. In the last section we use the vectorial norms, getting convergence conditions for the MSOR method, when A is a block-H matrix. We also generalize a theorem of Robert's for this kind of matrices.     

On the choice of parameters in MAOR type splitting methods for the linear complementarity problem

In the present work we consider the iterative solution of the Linear Complementarity Problem (LCP), with a nonsingular H ₊ coefficient matrix A, by using all modulus-based matrix splitting iterative methods that have been around for the last couple of years. A deeper analysis shows that the iterative solution of the LCP by the modified Accelerated Overrelaxation (MAOR) iterative method is the “best”, in a sense made precise in the text, among all those that have been proposed so far regarding the following three issues: i) The positive diagonal matrix-parameter Ω ≥ diag(A) involved in the method is Ω = diag(A), ii) The known convergence intervals for the two AOR parameters, α and β, are the widest possible, and iii) The “best” possible MAOR iterative method is the modified Gauss-Seidel one.     

Optimum Modified SOR (MSOR) Method in a Special Case

In this paper we study the MSOR method with fixed parameters, when applied to a linear system of equations $Ax=b(1)$, where $A$ is consistently ordered and all the eigenvalues of the iteration matrix of the Jacobi method for (1) are purely imaginary. The optimum parameters and the optimum virtual spectral radius of the MSOR method are also obtained by an analysis similar to that of [5, pp. 277-281] for the real case. Finally, a comparison of the optimum MSOR method with the optimum SOR and AOR methods is presented, showing the superiority of the MSOR one.     

Extended convergence regions for the AOR method

In this paper, we give sufficient conditions for the convergence of the (AOR) method, when the matrix A for Ax = b is a strictly diagonally dominant matrix. These results improve the conclusions obtained in the Theorem 4 [10].With the notion of generalized diagonal dominant matrix, we enlarge the convergence regions given in Theorem 9 [10], when A is a nonsingular H-matrix.In the last section we generalize theorem 6 of Robert [11] and we present some results which extend the convergence regions for the (AOR) method.     

On the convergence of splittings for semidefinite linear systems

Recently, Lee et al. [Young-ju Lee, Jinbiao Wu, Jinchao Xu, Ludmil Zikatanov, On the convergence of iterative methods for semidefinite linear systems, SIAM J. Matrix Anal. Appl. 28 (2006) 634-641] introduce new criteria for the semi-convergence of general iterative methods for semidefinite linear systems based on matrix splitting. The new conditions generalize the classical notion of P-regularity introduced by Keller [H.B. Keller, On the solution of singular and semidefinite linear systems by iterations, SIAM J. Numer. Anal. 2 (1965) 281-290]. In view of their results, we consider here stipulations on a splitting A=M-N, which lead to fixed point systems such that, the iterative scheme converges to a weighted Moore-Penrose solution to the system Ax=b. Our results extend the result of Lee et al. to a more general case and we also show that it requires less restrictions on the splittings than Keller’s P-regularity condition to ensure the convergence of iterative scheme.     

Is modified PSD equivalent to modified SOR for two-cyclic matrices?

In this paper we study the convergence analysis of the Modified Preconditioned Simultaneous Displacement (MPSD) method when A is a two-cyclic matrix. Convergence conditions and optimum values of the parameters are determined in case the eigenvalues of the associated Jacobi iteration matrix are either all real or all imaginary.     

Global relaxed modulus-based synchronous block multisplitting multi-parameters methods for linear complementarity problems

Recently, Bai and Zhang [Numerical Linear Algebra with Applications, 20(2013):425439] constructed modulus-based synchronous multisplitting methods by an equivalent reformulation of the linear complementarity problem into a system of ?xed-point equations and studied the convergence of them; Li et al. [Journal of Nanchang University (Natural Science), 37(2013):307-312] studied synchronous block multisplitting iteration methods; Zhang and Li [Computers and Mathematics with Application, 67(2014):1954-1959] analyzed and obtained the weaker convergence results for linear complementarity problems. In this paper, we generalize their algorithms and further study global relaxed modulus-based synchronous block multisplitting multi-parameters methods for linear complementarity problems. Furthermore, we give the weaker convergence results of our new method in this paper when the system matrix is a block H+?matrix. Therefore, new results provide a guarantee for the optimal relaxation parameters, please refer to [A. Hadjidimos, M. Lapidakis and M. Tzoumas, SIAM Journal on Matrix Analysis and Applications, 33(2012):97-110, (dx.doi.org/10.1137/100811222)], where optimal parameters are determined.     

Convergence of a preconditioned iterative method for H-matrices

In this paper, we consider a preconditioned iterative method for solving the linear system Ax = b, which is a generalization of a method proposed in Kotakemori et al. [3] and prove its convergence for the case when A is an H-matrix.     

New error bounds for the linear complementarity problem of <Emphasis Type="Italic">QN</Emphasis>-matrices

An error bound for the linear complementarity problem (LCP) when the involved matrices are QN-matrices with positive diagonal entries is presented by Dai et al. (Error bounds for the linear complementarity problem of QN-matrices. Calcolo, 53:647-657, 2016), and there are some limitations to this bound because it involves a parameter. In this paper, for LCP with the involved matrix A being a QN-matrix with positive diagonal entries an alternative bound which depends only on the entries of A is given. Numerical examples are given to show that the new bound is better than that provided by Dai et al. in some cases.     

A new inversion-free method for a rational matrix equation

Motivated by the classical Newton-Schulz method for finding the inverse of a nonsingular matrix, we develop a new inversion-free method for obtaining the minimal Hermitian positive definite solution of the matrix rational equation X+A^∗X^-1A=I, where I is the identity matrix and A is a given nonsingular matrix. We present convergence results and discuss stability properties when the method starts from the available matrix AA^∗. We also present numerical results to compare our proposal with some previously developed inversion-free techniques for solving the same rational matrix equation.     

The relaxed inexact projection methods for the split feasibility problem

In this paper we present several relaxed inexact projection methods for the split feasibility problem (SFP). Each iteration of the first proposed algorithm consists of a projection onto a halfspace containing the given closed convex set. The algorithm can be implemented easily and its global convergence to the solution can be established under suitable conditions. Moreover,we present some modifications of the relaxed inexact projection method with constant stepsize by adopting Armijo-like search. We furthermore present a variable-step relaxed inexact projection method which does not require the computation of the matrix inverses and the largest eigenvalue of the matrix A^TA, and the objective function can decrease sufficiently at each iteration. We show convergence of these modified algorithms under mild conditions. Finally, we perform some numerical experiments, which show the behavior of the algorithms proposed.     

A note on universally optimal matrices and field independence of the minimum rank of a graph

For a simple graph G on n vertices, the minimum rank of G over a field F, written as mr^F(G), is defined to be the smallest possible rank among all n×n symmetric matrices over F whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. A symmetric integer matrix A such that every off-diagonal entry is 0, 1, or -1 is called a universally optimal matrix if, for all fields F, the rank of A over F is the minimum rank of the graph of A over F. Recently, Dealba et al. [L.M. Dealba, J. Grout, L. Hogben, R. Mikkelson, K. Rasmussen, Universally optimal matrices and field independence of the minimum rank of a graph, Electron. J. Linear Algebra 18 (2009) 403-419] initiated the study of universally optimal matrices and established field independence or dependence of minimum rank for some families of graphs. In the present paper, more results on universally optimal matrices and field independence or dependence of the minimum rank of a graph are presented, and some results of Dealba et al. [5] are improved.     

On the convergence of the symmetric successive overrelaxation method

The symmetric successive overrelaxation (SSOR) iterative method is applied to the solution of the system of linear equations $\text{A}\text{x}\text{=}\text{b}$, where A is an n×n nonsingular matrix. We give bounds for the spectral radius of the SSOR iterative matrix when A is an Hermitian positive definite matrix, and when A is a nonsingular M-matrix. Then, we discuss the convergence of the SSOR iterative method associated with a new splitting of the matrix A which extends the results of Varga and Buoni [1].     

An error bound for the modified successive overrelaxation method

In this paper we consider the modified successive overrelaxation(MSOR)methodto appropriate the solution of the linear system D^-1/2 Ax =D^-1/2b, where A is a symmetric, positive definite and consistentlyordered matrix and D is a diagonal matrix with the diagonalidentical to that of A. The main purpose of this paper is to obtain some theoreticalresults, namely a bound for the norm of _n = v –v_n in termsof the norms _n –v_n-1, _n+1 –v_n and their inner product,where v =D^-1/2 x and v_n is the nth iteration vector, obtainedusing the (MSOR)method.     

Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices

We show that the Hamiltonicity of a regular graph G can be fully characterized by the numbers of blocks of consecutive ones in the binary matrix A+I, where A is the adjacency matrix of G, I is the unit matrix, and the blocks can be either linear or circular. Concretely, a k-regular graph G with girth g(G)?5 has a Hamiltonian circuit if and only if the matrix A+I can be permuted on rows such that each column has at most (or exactly) k-1 circular blocks of consecutive ones; and if the graph G is k-regular except for two (k-1)-degree vertices a and b, then there is a Hamiltonian path from a to b if and only if the matrix A+I can be permuted on rows to have at most (or exactly) k-1 linear blocks per column.Then we turn to the problem of determining whether a given matrix can have at most k blocks of consecutive ones per column by some row permutation. For this problem, Booth and Lueker gave a linear algorithm for k=1 [Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, 1975, pp. 255-265]; Flammini et al. showed its NP-completeness for general k [Algorithmica 16 (1996) 549-568]; and Goldberg et al. proved the same for every fixed k?2 [J. Comput. Biol. 2 (1) (1995) 139-152]. In this paper, we strengthen their result by proving that the problem remains NP-complete for every constant k?2 even if the matrix is restricted to (1) symmetric, or (2) having at most three blocks per row.     

Fast algorithms for placing large entries along the diagonal of a sparse matrix

Solving a sparse system of linear equations Ax=b is one of the most fundamental operations inside any circuit simulator. The equations/rows in the matrix A are often rearranged/permuted before factorization and applying direct or iterative methods to obtain the solution. Permuting the rows of the matrix A so that the entries with large absolute values lie on the diagonal has several advantages like better numerical stability for direct methods (e.g., Gaussian elimination) and faster convergence for indirect methods (such as the Jacobi method). Duff (2009) [3] has formulated this as a weighted bipartite matching problem (the MC64 algorithm). In this paper we improve the performance of the MC64 algorithm with a new labeling technique which improves the asymptotic complexity of updating dual variables from O(|V|+|E|) to O(|V|), where |V| is the order of the matrix A and |E| is the number of non-zeros. Experimental results from using the new algorithm, when benchmarked with both industry benchmarks and UFL sparse matrix collection, are very promising. Our algorithm is more than 60 times faster (than Duff’s algorithm) for sparse matrices with at least a million non-zeros.     

On a shifted LR transformation derived from the discrete hungry Toda equation

The discrete hungry Toda (dhToda) equation is known as an integrable system which is derived from the study of the numbered box and ball system. In the authors’ paper (Fukuda et al., in Phys Lett A 375, 303–308, 2010), we associate the dhToda equation with a sequence of LR transformations for a totally nonnegative (TN) matrix, and then, in another paper (Fukuda et al. in Annal Math Pura Appl, 2011), based on the dhToda equation, we design an algorithm for computing the eigenvalues of the TN matrix. In this paper, in order to accelerate the convergence speed, we first introduce the shift of origin into the LR transformations associated with the dhToda equation, then derive a recursion formula for generating the shifted LR transformations.We next present a shift strategy for avoiding the breakdown of the shifted LR transformations. We finally clarify the asymptotic convergence and show that the sequence of TN matrices generated by the shifted LR transformations converges to a lower triangular matrix, exposing the eigenvalues of the original TN matrix. The asymptotic convergence is also verified through some numerical examples.     

Convergence of the parallel chaotic waveform relaxation method for stiff systems

In this paper, we establish several algorithms for parallel chaotic waveform relaxation methods for solving linear ordinary differential systems based on some given models. Under some different assumptions on the coefficient matrix A and its multisplittings we obtain corresponding sufficient conditions of convergence of the algorithms. Also a discussion on convergence speed comparison of synchronous and asynchronous algorithms is given.