A comparison of some methods for bounding connected and disconnected solution sets of interval linear systems (Q956687)

The paper focuses on the preconditioned interval Gauss-Seidel method for enclosing the set of all solutions of linear systems \(Y\,Ax=Yb\), where \(A,b\) are allowed to vary in a given interval matrix \({\mathbf A}= [\underline A,\overline A]\) and a corresponding interval vector \({\mathbf b}\), respectively; \(Y\) is a preconditioning point matrix used to reduce the width of overestimation of the unpreconditioned method. The preconditioner can even be chosen such that zero is contained in some of the diagonal entries of \(Y{\mathbf A}\) leading to disconnected semi-infinite components of the Gauss-Seidel iterate. Such preconditioners are called splitting- or \(S\)-preconditioners. Optimization problems are formulated for special representatives of them and for various other preconditioners which are optimal in a specific sense. Based on detailed studies of numerous examples two composite polynomial time algorithms are proposed which incorporate all of these preconditioners. The algorithms were tested with randomly generated matrices, as well as with selected matrices from the Matrix Market collection. It turns out that in many cases the traditional inverse midpoint preconditioner \(Y=((\underline A+ \overline A)/2)^{-1}\) is inferior to the new choices of \(Y\).