Interval Linear Constraint Solving Using the Preconditioned Interval Gauss-Seidel Method

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(n 4 ), where n is the number of variables in the linear system. In this paper, we generalize the algorithm for general linear systems with m constraints and n variables, and give a novel incremental adaptation of preconditioning of O(n 2 (n + m)) complexity. The efficiency of the incremental preconditioned interval Gauss-Seidel method is demonstrated using large-scale linear systems. 1 Introduction and Related Work Interval narrowing [7] is deficient in handling general systems of constraints over real numbers [5, 2]. Chiu and Lee [6] suggest to separate linear equali..