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

该项目将研究有效的并行算法，以在给定的数学确定性域中找到大规模非线性方程组的所有数值解，即使存在数据的不确定性，舍入误差和有限数字计算的非线性。所使用的基本算法是基于区间牛顿/广义对分法。并行算法将在矢量处理器、共享内存多处理器和分布式内存多计算机上实现。在矢量处理器上，新的数据结构将被设计为充分利用矢量处理器的完全流水线功能单元。为了加快内存访问速度，将开发一些技术，以提高具有缓存的机器（如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. ***