Generalizations of Property A and Consistent Orderings
David M. Young · SIAM Journal on Numerical Analysis · 1972
If the matrix A is consistently ordered, it is often possible to choose the relaxation factor so that the successive overrelaxation method for solving the linear system $Au = b$ converges rapidly. It is known that a consistently ordered matrix can be obtained by permuting the rows and corresponding columns of a given matrix A if and only if A has Property A. In this paper the concept of Property A is generalized to correspond to known generalizations of the concept of consistently ordered matrices. It is also shown how one can in some cases permute the rows and columns of a matrix with generalized Property A so that rapid convergence is obtained using the successive overrelaxation method. An alternative proof, based on the use of graph theory, is given for a characterization, due to Broyden, of a still more general class of consistently ordered matrices. The possibility of reducing a given matrix to a block tri-diagonal matrix or to some other canonical form by various permutations of the rows and columns is also considered.