Interval Linear Constraint Solving Using the Preconditioned Interval Gauss-Seidel Method
LEON S. STERLING · 1995
We propose the use of the preconditioned interval Gauss-Seidel method as the backbone of an efficient linear equality solver in a CLP(Interval) language. The method, as originally designed, works only on linear systems with square coefficient matrices. Even imposing such a restriction, a naive incorporation of the traditional preconditioning algorithm in a CLP language incurs a high worst-case time complexity of O(n4), where n is the number of variables in the linear system. In this paper, we generalize the algorithm for general linear systems with ro constraints and n variables, and give a novel incremental adaptation of preconditioning of O(n2(n + m)) complexity. The efficiency of the incremental preconditioned interval Gauss-Seidel method is demonstrated using large-scale linear systems.