Unstructured Multi-Grid method and the efficient implementation technique on parallel machines

共轭梯度法的有效预处理要求并行化和良好的收敛加速。这两件事往往是不相容的。因此，作者提出了同时满足这两个条件的多网格预处理方法，并证明了该方法的有效性。在本研究中，我们考虑了具有大各向异性的非结构化网格问题。SA-AMG方法是一种多网格方法，它计算较小的矩阵，并利用较小的矩阵有效地达到收敛。但对于各向异性问题，SA-AMG方法的效率有所下降。结果表明，基于域边界信息的较小矩阵生成方法使该方法具有较好的收敛性。我们还研究了SA-AMG方法的矢量化实现技术。三次矩阵乘法的计算量最大。对于这一部分的矢量化，我们测试了稀疏矩阵和更多数据结构的各种组合，并证明了基于JDS和CRS数据结构的方法对三维弹性问题是最有效的。另一个相关的实现技术研究，作者创建了分布式稀疏矩阵的重分布和重排序库。这个库提供了动态重新分发和重新排序的框架，并且很容易实现这些事情。对于其他基本并行实现技术的研究，作者研究了有限大小多主可分负载问题的重分配调度问题。通过对部分参数的辨识，仿真结果与实际系统的行为基本一致。研究了并行分子动力学的数据分布问题，研究了在计算机节点间通信带宽和时延不均匀的情况下的最佳数据分布方法。如何将这些基本技术应用于多网格方法在各种计算机平台上的并行实现，是未来的一个挑战。少

Efficient preconditioning for Conjugate Gradient method requires parallelization and good acceleration of convergence. These two things are often incompatible. Thus, the authors proposed the Multi-Grid preconditioning, which satisfies both of two things, and have demonstrated the efficiency of the method.In this study, we considered the problems with unstructured grids and with a big anisotropy. SA-AMG method, which is one of the multi-grid methods, calculates the smaller matrix and reaches the convergence efficiently utilizing that smaller matrix. But the SA-AMG method's efficiency deteriorates for anisotropic problems. The authors have shown that the smaller matrix creation method based on domain border information enables the method efficient convergence.We also studied the vectorization of the SA-AMG method for the implementation technique. Three matrix multiplications occupy the most calculation cost. For vectorization of this part, we tested various combinations of sparse matrix … More data structures and demonstrated the method based on the JDS and the CRS data structures is the most efficient for 3-Dimentional elastic problems. For another related study of the implementation technique, the authors created the re-distribution and re-ordering library for distributed sparse matrix. This library offers the frame work of the dynamic re-distribution and re-ordering, and enables those things easily.For other study of basic parallel implementation technique, the authors have studied the redistribution scheduling problem for finite sized multi-master divisible load problem. By identification of some parameters the authors showed that the simulation duplicates the behavior of the real system. We have also studied data distribution problem of the parallel molecular dynamics, and researched the best data distribution method in the case that the communication band-width and latency between computer nodes are not uniform. It is a challenge for the future to apply these basic techniques for parallel implementation of multi-grid method on various computer platforms. Less