Parallel all-row preconditioned interval linear solver for nonlinear equations on multiprocessors (Q1339233)

Enclosure methods for solving systems of nonlinear equations are usually based on interval versions of Newton's method. In each iteration one has to deal with a `linear' system of equations, where the coefficient matrix has interval entries. One is interested in calculating a tight interval enclosure \(E\) of the corresponding solution set, the set of all solutions of all real linear systems with their coefficient matrices being contained in the interval matrix. The all row preconditioner considered in this paper calculates each component of \(E\) (an interval vector of dimension \(n\)) as the intersection of \(n\) 1-dimensional intervals. For component \(j\), these \(n\) intervals are obtained by `solving' each equation of the interval system with respect to component \(j\) in a total step manner. Solving these \(n^ 2\) systems bears a big amount of parallelism. The authors consider parallel implementations on a shared memory and a local memory hypercube architecture. On a shared memory system, processors should work on blocks of rows of the interval system in order to minimize bus services. The authors also show how to schedule bus requests evenly in time by overlapping computation and bus communication through an appropriate allocation of shared variables among processors. On the hypercube, processors are basically seen as being arranged in a \(2d\)-torus, on which the interval system matrix is mapped by \(2d\)-blocks. The additional hypercube structure is used when global operations (summation, intersection) have to be performed. Since several such global operations arise at a time, there is a potential for additional parallelism which can be exploited by embedding several binary trees or a ring into the hypercube. Numerical results on the Encore Multimax and the Connection Machine CM2 are included.