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

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