卷帘行存储下的一种并行Cholesky分解及其在PAR95上的实现

Ｃｈｏｌｅｓｋｙ 分解在科学与工程计算中占有重要的地位，串行的 Ｃｈｏｌｅｓｋｙ 分解已有成熟的方法，但并行的 Ｃｈｏｌｅｓｋｙ 分解方法要充分考虑机器体系的结构，在拥有共享内存的 Ｍ Ｉ Ｍ Ｄ 型多处理机、 Ｓ Ｉ Ｍ Ｄ 型向量机系统上前人已有较好的工作，本文给出适用于 Ｍ Ｐ Ｐ 大规模并行计算机的卷帘行存储行格式的并行 Ｃｈｏｌｅｓｋｙ 分解算法，该算法使用了优先计算优先发送的策略，减少了结点机之间相互等待的时间，建立了结点机之间用于通讯的通讯数组，避免了使用撒播这一通讯模式，减少了通讯时间，通过在 Ｐ Ａ Ｒ９５ 上的数值试验表明，随着问题规模的扩大，并行效率越来越高，并且该法容易推广到多行卷帘存储的形式。

An Algorithm of Cholesky Decomposition at the Storage Pattern of Wrapped Interleaved Row Storage and Its Implementation on PAR95

Cholesky method is in a high position in scientific and engineering calculation. Sequential Cholesky decomposition has been fully developed, but parallel Cholesky decomposition method must take the structure of the computer into account. The former researchers have achieved satisfying result on MIMD with shared memory and SIMD vector computer. This paper gives a parallel Cholesky method suitable to MPP parallel computer under the storage pattern of wrapped interleaved row storage. With the strategy of compute ahead and send ahead, the method reduces the waiting time, defines a communicating dimension used for communication between node computer, avoid broadcasting, so the time need for the communication has been reduced. The numerical experiment on PAR95 shows that the larger the scale, the higher the efficiency. The algorithm can be easily generalized to the storage pattern of multiple rows wrapped interleaved storage.