中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 中科院软件所  > 中科院软件所
题名:
并行ILU分解及其在迭代法上的应用
作者: 李李
答辩日期: 2000
专业: 计算机软件与理论
授予单位: 中国科学院软件研究所
授予地点: 中国科学院软件研究所
学位: 博士
关键词: 迭代法 ; 不完全LU分解(ILU) ; 多消去的不完全LU分解(ILUM) ; 最大独立集(MIS)排序 ; 多级p-路图划分
摘要: 本文的研究对象是不完全LU分解预处理技术和其在迭代法上的应用。首先我们介绍预条件子产生的背景-Krylov子空间迭代法的主要思想,对其中两种具有代表性的算法CG法和GMRES法的实现框架以及敛特性做一简要回顾。预条件子的几种选取方法我们也做了简要介绍,其中不完全LU分解是讨论的重点,我们给出一章专门叙述其基本思想和形式。对于不完全LU分解并行化的研究,我们从矩阵排序和矩阵划分入手,因为矩阵划分的好坏直接关系到并行算法和通讯量大小,而排序是目前开发并行性的主要途径。多消去的ILU算法(ILUM)利用独立集排序的思想-独立集节点对应的矩阵行在一次消去操作中可以同时消去,因为它们相互之间没有关系-在一定程度上提高了分解的并行性。ILUM并行实现的困难在于矩阵的有效划分和并行寻找最大独立集,这两个阶段将为以后的迭代打下基础;在并行迭代的过程中,三角系统的并行求解效率对迭代的时间影响最大,而它的实现方式与不完全LU分解阶段的通讯模式和数据结构直接相关。我们对它们的并行实现做了详细讨论,并给出了可行的方案。最后,数值实验的结果证明了我们的并行ILU算法可以有效地应用到迭代法上。
英文摘要: 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.
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/6704
Appears in Collections:中科院软件所

Files in This Item:
File Name/ File Size Content Type Version Access License
LW002165.pdf(1507KB)----限制开放-- 联系获取全文

Recommended Citation:
李李. 并行ILU分解及其在迭代法上的应用[D]. 中国科学院软件研究所. 中国科学院软件研究所. 2000-01-01.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[李李]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[李李]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace