Institutional Repository
| 并行ILU分解及其在迭代法上的应用 | |
| 李李 | |
| Major | 计算机软件与理论 |
| 2000 | |
| Degree Grantor | 中国科学院软件研究所 |
| Degree Level | 博士 |
| Place of Degree Grantor | 中国科学院软件研究所 |
| Keyword | 迭代法 不完全lu分解（ilu） 多消去的不完全lu分解（ilum) 最大独立集（mis）排序 多级p-路图划分 |
| English Abstract | 本文的研究对象是不完全LU分解预处理技术和其在迭代法上的应用。首先我们介绍预条件子产生的背景－Krylov子空间迭代法的主要思想，对其中两种具有代表性的算法CG法和GMRES法的实现框架以及敛特性做一简要回顾。预条件子的几种选取方法我们也做了简要介绍，其中不完全LU分解是讨论的重点，我们给出一章专门叙述其基本思想和形式。对于不完全LU分解并行化的研究，我们从矩阵排序和矩阵划分入手，因为矩阵划分的好坏直接关系到并行算法和通讯量大小，而排序是目前开发并行性的主要途径。多消去的ILU算法（ILUM）利用独立集排序的思想－独立集节点对应的矩阵行在一次消去操作中可以同时消去，因为它们相互之间没有关系－在一定程度上提高了分解的并行性。ILUM并行实现的困难在于矩阵的有效划分和并行寻找最大独立集，这两个阶段将为以后的迭代打下基础；在并行迭代的过程中，三角系统的并行求解效率对迭代的时间影响最大，而它的实现方式与不完全LU分解阶段的通讯模式和数据结构直接相关。我们对它们的并行实现做了详细讨论，并给出了可行的方案。最后，数值实验的结果证明了我们的并行ILU算法可以有效地应用到迭代法上。 |
| Abstract | In this paper we focus on Incomplete LU preconditioners and its applications on iterative methods. Firstly, we introduce main ideas of Krylov subspace iterative methods, which are background of preconditioners' emergence. Two algorithms, CG and GMRES as representative of this class of iterative methods are briefly reviewed. Several available preconditioners are also mentioned, among which Incomplete LU preconditioners(ILU) is our key point and we devote a whole chapter to it. We make matrix partitioning and matrix reordering as starting points of research on parallelization of ILU, because the quality of partition has direct effects on the overhead of communication, and reordering is one of key tools for attaining parallelism. ILU with multi-elimination(ILUM) which utilize idea of maximal independent set ordering can greatly improve the parallelism of factorization, multi-elimination means that matrix rows corresponding to independent vertices can be eliminated at the same time. The difficulties of parallelizing ILUM lie in matrix partitioning and finding maximal independent set, these two phases are bases of following iterative methods; During the process of parallel iterative, the efficiency of solving triangular system has critical impact on the whole execution time, and at the same time, how to realize forward and backward substitutions is dependent on the communication pattern and data structure of parallel ILU. We give all of them respective and detailed discuss, and at last present practical schemes for execution. Results from numerical experiments indicate that our parallel ILU can efficiently apply on iterative methods. |
| Pages | 48 |
| Language | 中文 |
| Content Type | 学位论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/6704 |
| Collection | 中科院软件所_中科院软件所 |
| Recommended Citation GB/T 7714 | 李李. 并行ILU分解及其在迭代法上的应用[D]. 中国科学院软件研究所. 中国科学院软件研究所,2000. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| LW002165.pdf（1507KB） | 限制开放 | -- | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment