PARALLEL ALL-ROW PRECONDITIONED INTERVAL LINEAR SOLVER FOR NONLINEAR EQUATIONS ON MULTIPROCESSORS

Interval Newton methods in conjunction with generalized bisection form the basis of algorithms that find all real roots within a specified X subset of R(n) of a system of nonlinear equations F(X) = 0 with mathe matical certainty, even in finite-precision arithmetic. One of the maj or computational cost in such methods is solving a correspondent linea r interval system. This paper proposes parallel implementations of the all-row preconditioned interval linear solver on two multiprocessor a rchitectures: shared bus multiprocessor and hypercube connected multip rocessor. Efficient parallel algorithms that are specifically tailored for these architectures are presented. The algorithms effectively use the hardware features to minimize communication overheads. Performanc e evaluation is carried out by means of actual measurements of the alg orithms running on real parallel computers. Our numerical results show that data partitioning, data allocation and processor scheduling play important roles in the performance of the parallel computation. In bo th systems, significant speedup can be obtained by properly overlappin g computation and communication.