RUI: Finding All Numerical Solutions for Large-Scale Nonlinear Systems of Equations Parallelly and Reliably in a Given Domain

9503757胡本项目将研究有效的并行算法，以找到所有的数值解的大规模非线性方程组在一个给定的域与数学的确定性，即使在存在不确定性的数据，舍入误差和非线性有限位计算。 使用的基本算法是基于区间牛顿/广义二分法。 并行算法将在向量处理器、共享内存多处理器和分布式内存多计算机上实现。 在向量处理器上，将设计新的数据结构以充分利用向量处理器的完全流水线功能单元。 为了加速存储器访问，将开发技术来增加具有高速缓存的机器（如IBM 3090）上的高速缓存命中率，并减少交叉存储器系统（如CRAY C90）上的存储体冲突。 在一个共享内存的多处理机上，将研究基于两种协议的给定非线性系统的最优划分方案。 通过重叠通信和计算，除了减少通信和争用之外，还期望大的加速比。 在分布式内存多计算机上，粗粒度SPMP方案和细粒度MPMP方案的算法将在实际机器上实现。 一般稀疏性和可伸缩性将在所有实现中考虑。 ***

9503757 Hu This project will investigate efficient parallel algorithms to find all numerical solutions for large-scale nonlinear systems of equations in a given domain with mathematical certainty, even in the presence of uncertainty in the data, roundoff error, and nonlinearities by finite digit computations. The basic algorithm to be used is based on the interval Newton/Generalized bisection method. Parallel algorithms will be implemented on vector processors, shared-memory multiprocessors, and distributed-memory multicomputers. On a vector processor, new data structures will be designed to take full advantage of completely pipelined functional units of vector processors. To speed memory accessing, techniques will be developed to increase cache hit ratio on machines with cache such as the IBM 3090, and to reduce bank conflict on interleaved memory systems such as the CRAY C90. On a shared memory multiprocessor, optimal partitioning schemes will be studied for given nonlinear systems based on two protocols. By overlapping communication and computation, in addition to reducing communication and contention, large speedup is expected. On distributed-memory multicomputers, algorithms on coarse grained SPMP schemes and fine-grained MPMP schemes will be implemented on realistic machines. General sparsity and scalability will be considered in all implementations. ***