（计算机应用技术专业论文）线性规划并行化若干问题的研究.pdf

上海人学硕b 孚q 节论文 摘要 线性规划问题最早是由g e o r g e bd a n t z i g 在1 9 4 7 年以前设想出来的。1 9 4 9 年 g b d a n t z i g 提出了用于求解线性规划问题的一个有效的方法一单纯形方法。在1 9 8 4 年，n ，k a r m a r k a r 的“投影尺度法”使线性规划出现真f 的突破。这种新算法4 ：仅在理 论上优越于单纯形法，而且也显示出对求解火规模实际问题的巨大潜力。k a n n a r k a r 算 法再一次真正地不同于单纯形法，它是从可行域的内部逼近一个最优解。这一内点法已 成为近几年来令人感兴趣的研究焦点。自k a n n a r k a r 算法产生起，不断有许多学名致力于 改进，完善及推广这一类方法，并统称这种类型的算法为内点算法。 本文主要做了以下几方面工作： ( 1 ) 介绍了并行编程的环境包括集群系统简介，自强2 0 0 0 简介和m p i 简介。 ( 2 ) 介绍了线性规划的历史，线性规划的数学模型，以及如何把一般线性规划问 题转换成线性规划的标准型，并详细分析了一个原一对偶内点算法的计算步 骤。 f 3 1 提出了一种基于q r 分解的并行原一对偶内点算法，包括原一对偶内点算法 的基本思想，q r 分解，利用q r 分解并行原一对偶内点算法，并详细列出 了实验结果。 ( 4 ) 最后我们提出了一种基于嵌套分块的并行原一对偶内点算法，该算法首先将 大型稀疏矩阵转化为若干低阶矩阵，然后再解之。 关键词：线性规划，并行化，原一对偶内点算法 0 上海大学硕士学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。除 了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰 写过的研究成果。参与同一工作的其他同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：e t 期 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定。 即：学校有权保留论文及送交论文复印件，允许论文被查阅和借 阅；学校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：导师签名：日期： i 海人学颂卜、纠论文 a b s t r a c t t h ep r o b l e mo fl i n e a rp r o g r a m m i n gh a df i r s t l yb e e np r o p o s e db yg e o r g e b d a n t z i g b e f b r e19 4 7 i n19 4 7 ，g b d a n t z i gh a dp r e s e n t e dt h es i m p l e xm e t h o du s e dt os o l v et h el i n e a r p r o g r a m m i n g ，i n1 9 8 4 ，t h e l i n e a rp r o g r a m m i n gp r o b l e mw a s r e a l l ys o l v e du s i n gt h ep r o j e c t i v e r e s c a l i n ga l g o r i t h mg i v e nb yn k a m m r k a l t h i sn e wa l g o r i t h m n 0 1o n l yp r e c e d e st h es i m p l e x m e t h o do nt h et h e o r y ，b u ta l s os h o w st h et r e m e n d o u sp o t e n t i a li ns o l v i n gt h el a r g er e a lp r o b l e m w h a tt h ek a m l a r k a ra l g o r i t h md i f f e r sf r o mt h es i m p l e xm e t h o di st h a ti ta p p r o a c h e st h eb e s t s o l u t i o ni nt h ei n t e r i o ro ff e a s i b l e r e g i o n t h i s i n t e r i o r p o i n ta l g o r i t h m h a sb e c o m et h e r e s e a r c hf o c u si nr e c e n ty e a r s m a n ys c h o l a r sa p p l yt h e m s e l v e st o i m p r o v e ，p e r f e c ta n d p o p u l a r i z e t h i sk i n do fa l g o r i t h ms i n c et h ek a r m a r k a ra l g o r i t h ma p p e a r e d t h i st y p eo f a l g o r i t h mi sg e n e r a l l y n a m e da st h ei n t e r i o rp o i n ta l g o r i t h m i nt h ed i s s e r t a t i o no u rw o r ki sa sf o l l o w s ： ( 1 ) t h ec i r c u m s t a n c eo f p a r a l l e lp m g r a m m i n g ，c l u s t e rs y s t e m ，z i q i a n 9 2 0 0 0 a n d m p l a r ei n t m d u c e d ( 2 ) t h eh i s t o r y ，t h em a t h e m a t i cm o d e l o f t h el i n e a rp r o g r a m m i n ga sw e l la sh o wt o c h a n g et h eg e n e r a ll i n e a rp r o g r a m m i n gi n t ot h e 蛐d a r dl i n e a rp r o g r a m m i n ga r e p r e s e n t e d a n dt h e nw ea n a l y z et h es t e p so fp r i m a l d u a li n t e r i o rp o i n ta l g o r i t h n 3 c a r e f u l l y ( 3 ) b r i n g i n g f o r w a r da p a r a l l e lp r i m a l d u a li n t e r i o rp o i n ta l g o r i t h mb a s e d o nt h eq r d e c o m p o s i t i o ni n v o l v i n gb a s i ci d e ao f t h ep r i m a l d u a li n t e r i o rp o i n ta l g o r i t h m ，q r d e c o m p o s i t i o n ，a n dp a r a l l e l i z a t i o no f t h ep r i m a l - d u a li n t e r i o rp o i n ta l g o r i t l n n a n d t h e nl i s t i n gt h er e s u l t so f e x p e r i m e n ti nd e t a i l ( 4 ) a tl a s t ，p u t t i n gf o r w a r dap a r a l l e lp r i m a l - d u a li n t e r i o rp o i n ta l g o r i t h mb a s e d o n t h ee m b e d d e d p a r t i o n n i n gb ym e a n s o f c h a n g i n gal a r g es p a r s em a t r i xi n t os e v e r a l 】o w e rr a n km a t r i c e s k e y w o r d s ：l i n e a r p r o g r a m m i n g ，p a r a l l e l i z a t i o n ，p r i m a l _ d u a li n t e r i m p o i n t a l g o r i t h m 上海大学硕士学位论文 第1 章线性规划及算法简介 1 1 线性规划的历史 线性规划问题最早是由g e o r g e b d a n t z i g 在1 9 4 7 年以前设想出来的。他当时作为 联邦空军审计员的一名数学顾问，开发一个数学规划工具，用于制定部署，训练、后勤 保障的方案。由于该项工作，他于1 9 4 8 年出版了线性结构的规划一书。稍后，在 1 9 4 8 年夏天t c k o o p m a n s 和g b d a n t z i g 提出“线性规划”的名称。1 9 4 9 年g b d a n t z i g 提出了用于求解线性规划问题的一个有效的方法单纯形方法。在1 9 4 7 到1 9 4 9 年短短的时期中，线性规划基础的主要部分被展开。早在1 9 4 7 年以前，t c k o o p m a n s 就曾指出：线性规划为古典经济学理论的分析提供了一个极好的框架。 必须懂得，与其他科学领域一样，线性规划的诞生也不是一个晚上的事情。早在 1 9 4 7 年以前，数学工作者就研究了线性不等式系统，它是线性规划的数学理论的核 心。对这些系统的研究，可以追溯到1 8 2 6 年f o u r i e r 的工作。从那以后，相当数量的 数学工作者就考虑了有关的课题。尤其是，于1 9 3 9 年在w k a r u s h 的硕士论文中出现了 有限维空间不等式约束函数的最优性条件，以及由其他作者提出的线性规划的基础对偶 理论的各种特殊实例。早在1 9 3 9 年以前，l v k a n t o r o v i c h 曾指出了一类有限界的线 性规划模型对于生产计划的实际意义，并提出了一个求解线性规划的基础算法。可惜， k a n t o r o v i c h 的工作在前苏联被忽视了，以至于直到线性规划为d a n t z i g 等人确定以后 很久，在别处仍不为人所知。 在1 9 5 0 年到1 9 6 0 年之间，线性规划理论得到进一步发展和丰富，亦有成功的应用 见诸报道。在1 9 7 5 年，它真正受到公众的关注，因为在这一年，瑞典皇家科学院把经 济科学的诺贝尔奖授予l v k a n t o r o v i c h 和t c k o o p m a n s ，以奖励他们对资源最优分 配理论的贡献。另一受到公众关注的线性规划的重大事件发生在1 9 7 9 年， l g k h a n c h i a n 证明了s h o r ，7 u d i n 和n e m i r o v s k ii 的“椭球法”。这种方法与单纯形 法是根本不同的。在理论上，它应当是优于单纯形法的。单纯形法采用指数的逐次迭代 去寻找一个最优解。与单纯形法不同，椭球法则在一个多项式的时间内找到线性规划的 一个最优解。围绕着这一结果向世界公众做, m 4 e 告，似乎这新的算法能够快速地求解最 上海大学硕士学位论文 复杂的，很大规模的分配问题。遗憾的是椭球法在理论上的优越并不能在实践应用中得 以实现。 在1 9 8 4 年，n k a r m a r k a r 的“投影尺度法”使线性规划出现真正的突破。这种新 算法不仅在理论上优越于单纯形法，而且也显示出对求解大规模实际问题的巨大潜力。 k a r m a r k a r 算法再一次真正地不同于单纯形法，它是从可行域的内部逼近个最优解。 这一内点法已成为近几年来所感兴趣的研究焦点。 自k a r m a r k a r 算法产生起，不断有许多学者致力于改进，完善及推广这一类方法，并 统称这种类型的算法为内点算法。到目前为止，关于内点算法的研究成果不下数万种，并 不断有新的成果出现。 1 2 线性规划的意义 线性规划主要用在运输问题，生产组织问题，分配问题，合理下料等。 提高企业的经济效益是现代化管理的根本任务，各个领域中的大量问题都可以归结 为线胜规划问题。近几十年来，纷胜规划在各个行业中都得到了广泛的应用。根据美国 财富杂志对全美前b o o 家大公司的调查表明，线性规划的应用程度名列前矛，有 8 5 的公司频繁地使用线性规划，并取得了显著提高经济效益的效果。 线性规划可以应用子具有下列一般特征的问题： ( 1 ) 有可定义的目标( 诸如利润、成本与在一定时间期内最大的生产量) 。 ( 2 ) 有许多可用的替代解。例如，可以不同成本在一个生产单元上运行或在另一 生产单元上运行；或可以不同制造成本与运输成本从不同制造厂获得补充的仓库补货订 货。 ( 3 ) 资源是有限的。例如，成本最低的设施其能力不足以生产全部所需产品。 ( 4 ) 重要的成本与绩效变量之间的关系是线性( 一次) 代数方程式表达。 1 3 本研究的意义 自从n k a r m a r k a r 提出内点算法后，求解线性规划问题的算法从指数时问算法发 展到了多项式时间算法。但如果线性规划问题的规模很大，求解纷f 生规划问题所需的时 间也是巨大的。 上海大学硕士学位论文 因此，当前国际国内的许多高校和科研机构都在改进内点算法或发展内点算法的并 行算法，希望发展出一个在较短时间内求出线性规划的解的算法。 本文通过理论分析，提出了两个并行的原一对偶内点算法。并对并行内点算法进行 了实验，实验结果表明，并行内点算法具有较好的加速比。当前，国际国内许多专家学 者都在致力于内点算法的研究，我希望我的研究能为他们的研究提供一些参考。 1 4 本章小节 本章首先介绍了线性规划的历史，线性规划问题的求解算法经历了单纯型法和内点 算法。接着介绍了线性规划的意义，线性规划可以用在工业生产的许多方面。最后介绍 了本次研究的意义。 上海大学硕士学位论文 第2 章自强2 0 0 0 及m p i 简介 2 1 自强2 0 0 0 简介 自强2 0 0 0 高性能计算机，由中国工程院院士、上海大学计算机学院院长李三立带 领的课题组花了一年时间研制完成，主要为民用科学研究和工程计算服务。该计算机不 仅价格性能比优越，而且具有很好的扩展性。自强2 0 0 0 的价格仅为国际上同类产品售 价的三分之一。 本次研究就是将我校的自强2 0 0 0 作为测试平台，所以有必要在这里介绍一下自强 2 0 0 0 这个集群式高性能计算机系统。 2 1 1 系统结构 自强2 0 0 0 系统共有7 2 个结点，每个结点配有p e n f i u mm m i - u 或p e n t i u mm 7 0 0 m m 的c p u 、5 1 2 m 或3 8 4 m 内存、1 0 0 m 网卡、1 5 g 硬盘，其中1 6 个结点同时配有 m y r i n e t 的专用网卡。两套网络设备：以太网和m y r i n e t ，以太网由一个1 6 口和三个 2 4 口的s w i t c h 组成，m y r i n e t 由一个1 6 口的m y r i n e t 的s w i t c h 组成。一台p e n t i u m i i i 1 g h z i 的单c p u 主机，配有2 5 6 m 内存、1 0 0 m 网卡、6 0 g 的s c s i 硬盘，作为系统的 数据库服务器。另有两台单机分别负责路由和防火墙。 2 1 2 软件配置 自强2 0 0 0 的软件配置： ( 1 ) l i n u xr e d h a t8 0 操作系统 ( 2 ) m p i 和p v m 并行编程环境 ( 3 ) c 、f o r t r a n7 7 和f o r t r a n9 0 、j a v a 高级语言 ( 4 ) h p f ( h i g hp e r f o r m a n c ef o r t r a n ) 并行编译器 ( 5 ) 并行计算性能评价工具软件 ( 6 ) 关系型数据库 ( 7 ) 网络远程登录和管理软件系统( c a i ) 上海大学硕士学位论文 2 1 3 注能 自强2 0 0 0 系统的峰值速度已达每秒4 5 0 0 亿次，是目前我国集群式高性能计算机系 统中计算速度最高的。现已同清华大学咖s c - _ 2 通过因特网连接，构成了上海和北 京之间的先进计算基础设施的实验床。 与向量式和大规模并行处理型高性能计算机系统相比，集群式高性能计算机系统具 有运算速度高、性能价格比好、易于推广应用等优点，基本上可以满足民用科学技术的 计算需要。它可以运用于新材料分子结构计算、飞行物流体或固体力学的计算、高精度 石油勘探的计算等，在开展大规模科学与工程计算中发挥重要作用。集群式高性能计算 机在国际上已被广泛应用于人类基因、宇宙n 体运动、海洋循环研究以及核爆炸模拟 等。 2 2 m p i 简介 m p i ( m e s s a g ep a s s i n gi n t e r f a c e ) 是目前发展较快、使用面较广的一个公共的消 息传递库，顾名思义，就是在现有机器的软硬件通信基础上，实现了并行应用程序中各 并行任务之间的相互通信、协调和同步功能，并对这些并行任务进行管理。 2 2 1m p l 的诞生 随着并行计算技术的不断发展，人们已经意识到良好的软件开发环境和大量的应用 程序是推广和普及并行计算技术的关键。因此，针对n o w 系统的开发应用，一批基于 消息传递机制的并行程序开发平台相继问世，如p v m ，e x p r e s s ，l i n d a 等。人们利用这 些平台开发了许多应用并行程序，证明效果良好。当然，在这些软件开发过程中也暴露 出程序可重用性低，可移植性差，执行差，执行效率不稳定等些问题，这样并行库 ( p a r a l l e ll i b r a r y ) 的研制开发开始受到人们的重视。为了统一和完善消息传递机制， 1 9 9 2 年1 1 月在美国成立了旨在建立一个标准的可移植的并行程序开发平台的m p i 论坛 ( m e s s a g ep a s s i n gi n t e r f a c ef o r u m ) 。经过一年多的工作，该论坛于1 9 9 4 年5 月公布了 m p i 标准。 消息传递模式的吸引力部分地根源于它的大范围的可移植性。表达这种方式的程序 可以运行在分布存储多处理器上，工作站网络上，也可以在这些组合上运行。另外，共 享存储的实现也是可能的。组合共享和分布存储体系结构，或增加网络速度使这种模式 上海大学硕士学位论文 将不过时，所以在大范围的机器上实现这个标准是可能的和有用的，这包括由通信网络 联接的并行的或非并行的各种机器。 m p i 提供许多特点，这将在拥有特定处理器间通信硬件的可扩展并行计算机上提高 性能。同时，在标准u n i x 处理器间通信协议的上层实现的m p i 将给工作站机群系统 和不同种类的工作站网络提供可移植性。 m p i 具有可移植性、高效性、灵活性和易用性的特点，不仅适用于具有分布式内存 的大型机、工作站机群，也可用于具有共享内存的大型机。 2 2 2m p i 的主要特征 2 2 2 1 点对点通讯 m p i 有两种发送和接收方式：阻塞和非阻塞。阻塞发送到完成意味着数据已拷贝出 缓冲区，即通信缓冲区可以重新分配。阻塞接收到完成意味着到来的消息已拷贝入用户 的接收缓冲区，即接收方已可以使用。但是，发送到完成并不意味着一个匹配的接收已 发生，发送的消息可能被缓冲到系统的缓冲区中。这样，发送可以在匹配接收发生之前 完成。非阻塞操作可以使得计算与通信重叠( 必须有系统硬件支持) ，m p i 的非阻塞操 作立即返回一个句柄，这不意味着数据拷贝出发送缓冲区( 或数据已拷贝入用户接收缓 冲区) ，该旬柄可用来在适当的时候完成( m p i _ w a i t ) 或检测( m p i t e s t ) 对应的非阻 塞操作。m p i 提供具有以下语义的阻塞和非阻塞发送：标准发送、就绪发送、同步发 送。 2 2 2 2 数据类型 为了支持异构环境和易于编程，m p i 定义了精确数据类型参数而不使用字节。对于 c 和f o r t r a n ，m p i 均预定义了一组数据类型( 如m p i f l o a t 、m p ic h a r 等) ，这些与 语言中的数据类型相对应。另外，用户可以自定义其他的数据类型，如多维向量和类c 语言中的结构。m p i 还允许发送和接收不同的数据类型，使得数据重映射方便灵活。 2 2 2 3c o m m u n i c a t o r m p i 的一个关键特征就是c o m m u n i c a t o r ，以对象形式存在，作为通信操作的附加参 数。c o m r a u n i c a t o r 为开发消息传递程序提供了模块化的支持，从而强有力的支持并行 库和大规模代码。m p i 提供了各种机制用于创建和管理c o m m u n i c a t o r 。 上海大学硕士学位论文 2 2 2 4 全局通讯 m p i 有一组丰富的全局通信函数，包括b a r r i e rs y n c h r o n i z a t i o n 、b r o a d c a s t 、 s c a t t e r 、g a t h e r 和各种规约操作。c o m m u n i c a t o r 用来标识参与全局通信的进程组，这 样全局通信可以包括任意预定义的进程子集。 2 2 3m p i ：具体内容 m p i 标准1 1 中包含了以下内容： 1 f o r t r a n7 7 和c 语言形式的m p i 函数的语言规范 2 点一点通信 3 集群通信 4 进程组 5 通信上下文 6 进程拓扑结构 7 并行环境管理和查询 8 程序剖析接口 2 2 3 1c 语言形式的m p i 函数的语言规范 c 语言形式的m p i 函数的语言规范： ( 1 ) 所有关键字以m p i 一开头。其中，常量全为大写字母，函数和类型名中紧跟 在一后的第一个字母大写，其余小写； ( 2 ) 程序中要包含头文件m p i h ： ( 3 ) 几乎所有c 函数都有返回码，不同的返回码有不同的含义。使用 m p i _ e r r o r _ c l a s s 和m p i e r r o r _ s t r i n g 函数可以获取它们的意义： ( 4 ) 布尔变量：0 表示假，非0 表示真； ( 5 ) 函数说明中c h o i c e 类型的参数相当于v o i d ： ( 6 ) m p i _ a i n t 代表执行环境中的合法地址类型： ( 7 ) m p i i n i t 有两个参数，分别指向整数和字符数组。通过这两个参数可以读 入命令行参数。 上海大学硕士学位论文 2 2 3 2f o r t r a n 语言形式的m p i 函数的语言规范 f o r t r a n 语言形式的m p i 函数的语言规范： ( 1 ) 所有关键字均以m p i 一开头，且全为大写字母； ( 2 ) 程序中要包含头文件m p i f h ； ( 3 ) 几乎所有f o r t r a n 子程序的最后一个参数都包含返回码，其中： m p i _ s u c c e s s 表示成功，其它表示失败。句柄( h a n d l e s ) 用i n t e g e r 表 示，布尔值用l o g i c a l 表示。m p i 标识符最多可容纳3 0 个字符，字符可 为字母、数字和下划线。m p i _ a d d r e s s 表示地址类型，其大小可以容纳执 行环境中的数据和程序地址。 2 2 4m p i 程序设计 我们使用a n s i c 说明格式 2 2 4 1 点对点通讯基础 由进程完成的消息的发送和接收是基本的m p i 通信机制。基本的点对点通信操作 是s e n d 和r e c e i v e 。他们的用法在下面例子中解释。 # i n c l u d e ”d o _ m p i h “ m a i n ( a r g o ，a r g v ) i n ta r g o ； c h a r * * a r g v ； ( c h a rm e s s a g e 2 0 】； i n tm y r a n k ； m p i _ i n i t ( & a r g c ，& a r g v ) ； m p i _ c o m mr a n k ( m p i _ c o m m _ w o r l d ，& m y r a n k ) ； i f ( m y r a n k = = 0 ) 对0 进程的程序+ 0 ) 非空。 ( 2 ) 集合t = ( w ，s ) r “叫a t w + s = c ，s 0 非空 ( 3 ) 约束矩阵a 行满秩。 在这些假设前提下，由对偶理论可以容易地看出，问题( p ) 和( d ) 都有一个数 值相同的最优解，并且( p ) 和( d ) 的最优解的集合是有解的。 对于( p ) 中的x o ，可以应用对数壁垒函数技术，考虑下列非线性规划问题 ( p ，) ： m i n c r x - , u l o g 。一 ，= i a x = b s t x 0 其中， o 是壁垒b a r r i e r 或罚参数( p e n n t yp a r a m e t e r ) 。 当，f 斗0 ，我们希望( 只) 的最优解收敛于原线性规划问题( p ) 的一个最优解， 为证明这一点，首先观察到问题( c ，) 的目标函数是严格凸函数，由此可知( f ，) 至多 有一个全局极小点。凸规划理论进一步说明，如果全局极小点存在，则完全符合k u h n ， t u c k e r 条件： a x = b x 0 ( 原可行性)( 3 2 a ) w + s = c ，s 0( 对偶可行性)( 3 ，2 b ) x s e - ，fe = 0( 补偿松弛) ( 3 2 c ) 这里，x 和s 是分别以向量x 和s 的分量为对角元素的对角矩阵。 在( 1 ) 和( 2 ) 的前提下，再假设( p ) 有一个有解的可行域，可见问题( p ) 必是 可行的，且对每个，f o ，有一个唯一的极小点x ( ) 。因此，方程组( 3 2 ) 有一个唯 一解 上海人学硕十学位论文 ( x w s ) r ”r ”r “ 于是有以下引理： 引理3 2 1 在假设( 1 ) 和( 2 ) 下问题( z ，) 和方程组( 3 2 ) 都有唯一解。 方程组( 3 2 ) 还为下面的规划( d 。，) 的最大值解 w ( ) ，s ( ) 】提供了充分必要条件 ( k k t 条件) ： m a x b r w + t l o g 。5 ， i = 1 a7 w + s = o s t j 0 ，w 无约束 注意到方程组( 3 2 c ) 可以写为分量形式 x j s = t ；j 2 l ，n ( 3 2 c ) 因此，当假设( 3 ) 满足时，由方程( 3 2 c ) 和( 3 2 b ) x 可唯一地确定w 。设 x ( t ) ，w ( t ) ，s ( 肛) 为对每个 o 的方程组( 3 2 ) 的唯一解。显然，x ( ) s ，且 【w ( t t ) ，s ( ，z ) t 。此外，对偶间隙为 g ( t t ) = c l x ( ) 一b 7 w o o = c7 一w ( ) 7 一 x ( )( 3 3 ) = j ( ) 。x ( ) = n t 因此，当，f 呻o ，对偶间隙g ( ，f ) 收敛于零，这就说明x ( ) 和w ( ) 的确分别收敛于问 题( p ) 和( d ) 的最优解。于是我们有如下结论： 引理3 2 2 在假设( 1 ) ( 3 ) t ，当t t 寸0 时，x ( u ) 收敛于规划( p ) 的最优解， w ( p ) , s o t ) 收敛于规划) 的最优解。 对于 o ，设r 为有方程组( 3 2 ) 的解构成的曲线，或路径，即 r 2 “x ( ) ，w ( ) ，s ( t ) l x ( t ) ，w ( , t t ) ，s ( ) 】解( 2 4 ) ，对 o )( 3 4 ) 当，f 专0 ，路径r 引出了原最优解x + 和对偶最优解( w + ，s ) 。这样，跟随着路径 r 就为线性规划的一类原一对偶内点方法提供了一个理论模型。 上海大学硕士学位论文 给定一个初始点( p ，w o ，s o ) s t ，通过每步迭代中适当地选择移动方向 ( dk , 九。，以。) 和每步的步长，原一对偶算法产生了一个点的序列 ( x ，w k , s ) s x t ) 。为了测量各点( ，w kj 。) 与曲线f 的“偏差”，我们引入如下符 号( k _ o ，1 “2 ) ： g ，。= 薯s i ；扛1 ，2 ，胛( 35 a ) 一2 吉善 ( 3 5 b ) 囝。= r n i n 3 气f = 1 ，2 ，月) ( 3 5 c ) 吼= 寒 ( 3 5 d ) 显然，有o k 1 ，且只有当且仅当o = 1 时，才有( x kw k , 矿) f 。当初始点 ( x 0 ， w 0s o ) s x t 的偏差目。较大的，原一对偶算法不仅减小对偶间隙，同时也减小偏 差，适当地选择参数，原一对偶算法产生的点的序列 ( ，w k 矿) s x t ) 满足如下不等 式： c t x “l b r w “= 1 - 2 ( n o ) ( c x 一b r w )( 3 6 a ) 曰。+ 1 - 2 1 - 1 ( n + 1 ) ( 目一2 ) ，2 o 和s 。 o ，并选择三个 充分小的正数e 。，e ：，e 。这三个参数的选取请参阅文献 1 2 。 上海大学硕十学位论文 步骤2 ：中i 叫计算。计算 u k 鲨些j ，t “：ba x k ，扛c a w - 一s - v k = p e x k s k e ，p “= x k l v 。，d k = x 。s k e 是n 维全1 向量，x 。和s 。是对角矩阵，其相应对角元素分别为x “和s k j 。 步骤3 ：检查最优性。若 船”揣，且揣“， 则停止，解即为最优解。否则转下一步。 步骤4 ：计算转移方向。计算 以= ( a d 。a ) “ a d 。( u k - - p 。) + t “ d 、“= u 。一a d 匕 d ，k d k ( p - d “、) 步骤5 ：检查无解性。 若t k = o 以 o 且c t d 。 0 且bj d k o ，则对偶问题( d ) 是无解的。 若上述两者之一发生，则停止：否则转下一步。 步骤6 ：找出步长。计算原的和对偶的步长 艮5 忑石方习雨 bn 2 0 ： ， 门 ， ： ，卵 oo；嘶o，0o0 上海人学硕 。学位论文 这旱o a l ，如可取0 9 5 。 步骤7 ：移动到新点。更新解向量 x “一。 一 1 3 。d “。 w ” w “+ d ) d “。 s ”】 一s + 口) d “ s ” s 。+ bu d ，“ 令k = k + l ，并转步骤2 。 原一对偶内点算法的详细内容请参考文献 3 2 0 ， 2 4 ， 2 5 ， 2 6 ， 2 7 ， 2 8 ， 2 9 。 从上面的计算步骤可以看出，大部分计算时间都花在一个矩阵的求逆上。可以看出 以= ( a d 。) 1 a d 。( u l 矿) + t 。 等阶于( a e a 。) d k , = a d 。( u l p 。) + t 。 。而这个等式可以利用q r 分解求解。从而也可以把它并行化。 3 4 矩阵的q r 分解 矩阵的q r 分解将非奇异系数矩阵a 分解为正交矩阵与上三角矩阵r 的积 a = q r 从而使方程组求解转化为三角方程组求解。 矩阵的q r 分解可以用h a u s e h o l d e r 变换或g i v e n s 变换来实现，假设矩阵a 为 n # n 矩阵，元素用a ，( o i ，j n ) 来表示。 标准的g i v e n s 变换通过适当选择甜使其成为一有限的平面旋转变换序列的乘积，其 中每一个变换消去a 的主对角线下一个元素而不破坏先前形成的零元素，从而得d a = r ， 为消去a 的第( p ，q ) 个元素，只须对a 的第p - 1 ，p 两行进行以下变换 f 卅n 1a p - t , i “p - l , 2 l 一胛，胛j l 盘川“，2 其中 a , - l ? 上海人学硕十学位论文 此置换矩阵记为g 。，意即该变换作用于pi ，p 两行而消去第( p ，q ) 个元素。 g i v e n s 变换中消去第( p ，q ) 个元素，也可以作用于任一i 行和p 行( i p ) ，只 要i 行满足：第( i ，j ) ( o s j q ) 个元素为o ，第( i ，q ) 个元素不为0 。 g i v e n s 变换的并行算法设计 对矩阵a 进行分块：将其行和列分别k 等分，这些分割线相交，将对角线下的元 素分为三角子块或正方形形子块，然后将其中的正方形子块用从左上到右下的对角线 分为两个三角子块( 对角线元素包含在正方形子块的右三角子块中) 。这样共得到 k * k 个三角子块，我们将每个子块的消零看作一个子任务。 显然，对a 如上分块后共得到k * k 个子任务。记其第i 行块中从左至右的第j 个 三角子块对应的子任务为t i , j ( 0 = i k ，o = 0 ： ( 2 ) 计算u “，t “，u 。，v “，p 。，d 。的值： ( 3 ) 判断下列条件是否满足 出揣，且揣， 如满足则得到最优解，否则转下一步。 1 4 ) 计算d “，d ：，d “， l 海人学硕十学位论文 其中计算d “时，把它转化为( a d 。a 。) 以= l a d 。( u “一p “) + l 1 再把( a d 。a 。) 进行分块， 分成4 * 4 块按图3 2 ( 括号内的数字表示要用到的处理机号) 所示分成8 步处理。 先把1 ( 0 ) ，l ( 1 ) ，1 ( 2 ) ，1 ( 3 ) 所在的仃块发到0 ，l ，2 ，3 四个处理机【二处理，分别 对1 ( o ) ，1 ( 1 ) ，1 ( 2 ) ，1 ( 3 ) 三角子块消零。 把2 ( 0 ) ，2 ( 1 ) 所在的行块分别发到0 ，1 处理机，对2 ( 0 ) ，2 ( 1 ) 三角子块消零， 处理完后发回各自处理机。 把3 ( 0 ) 所在的行块发到处理机0 ，对3 ( 0 ) 三角子块消零，分别在2 ，3 处理机 对3 ( 2 ) ，3 ( 3 ) 三角子块消零。 在处理机o 上，对4 ( o ) 三角子块消零，把5 ( 2 ) 所在行块发到处理机3 对 4 ( 3 ) 三角子块消零，把5 ( 2 ) 所在行块发回处理机2 。 把4 ( o ) 所在行块发到处理机2 ，剥j ( 2 ) 三角子块消零。在处理机3l 对5 ( 3 ) 三角子块消零。 在处理机2 对6 ( 2 ) 三角子块消零。 把6 ( 2 ) 所在行块发到处理机3 ，对7 ( 3 ) 三角子块消零。 在处理机3 上对8 ( 3 ) 三角子块消零。 最后算出d “的值。 再计算d “。，d 。的值 ( 5 ) 判断是否t = o ，d o 且c d o 且b d o ? 若是，则对偶问题无解。 若上面两个判断有一个成立，则停止：否则转r 一步。 ( 6 ) 计算原的和对偶的步长 口一 1 队一盂丽刁巧万万 d 一 1 叭盂丽i 巧忑巧 ( 7 ) 计算x ，w “1 ，s ”，令k = k + l ，并转( 2 ) 。 3 0 上海大学硕+ 学位论文 3 6 实验结果 本次实验在上海大学自强2 0 0 0 集群式计算机上的四个节点上进行，这四个节点所 用的处理器部是p i l l 7 0 0 m z ，内存分别是5 1 2 兆，5 1 2 兆，5 1 2 兆，3 8 4 兆，。 约束条件( 行水串行时间并行时间加速比 列)( s )( s ) 2 0 0 4 0 0i 51 1 0 5 8 5i 3 5 6 3 0 0 6 0 05 23 7 0 7 8 81 4 0 2 4 0 0 8 0 01 2 28 9 0 2 0 51 3 7 4 表3 1 实验结果 3 7 本章小节 本章主要做了以下几方面工作： ( 1 ) 线性规划问题，包括线性规划问题的数学模型，如何把一般线性规划问 题转换成标准型的线性规划问题，及求解线性规划问题的两类算法。 ( 2 ) 原一对偶内点算法的基本思想，通过一系列的推导解释了求解原一对偶 内点算法的基本思想。 ( 3 ) 在上一节解释原一对偶内点算法基本思想的基础上。得出求解线性规划 问题的原一对偶内点算法的基本步骤。 ( 4 ) 提出了一种利用q r 分解进行并行计算的理论。 ( 5 ) 提出了一种基于q r 分解的并行原一对偶内点算法。 ( 6 ) 在自强2 0 0 0 上，对基于q r 分解的并行原一对偶内点算法进行了实验， 并得出实验结果。 上海火学硕+ 学位论文 第4 章一个基于嵌套分块的并行原一对偶内点算法 4 ，1 分块计算方法 假设1 1 阶大型稀疏方程组 a x = y 其中 a = a 1 1a 1 2 a 2 la 2 ： a 】m a 2 w 4 。4 ，：4 ，。 是n x n 阶的m x m 分块矩阵；a 非奇异。 a , j 是tx l ，阶子阵( i j 2 l ，2 ，m ) ； x 2 ( 五7 ，恐7 ，x m 7 ) 1 是待求的n 维列向量； 誓7 = ( 一。，x i 2 c h ) 是x 的第i 个子向量。维数是( i - l ，2 ，m ) y = ( m7 ，y 27 ，y r ) 7 是已知n 维列向量； y j 7 = ( m 1 ，y j 2 ，肌) 是y 的第i 个子向量，维数是； 记 h = 0 a l2 a 2 l 0 a i 。 爿2 。 4 ，l4 ，：0 其中 日 = h ih 2 风】 4 “ 0 4 礼 上海火学硕士学位论文 设e 中有e c 蔓t ，列全0 ，则经列置换，f ： 可化成如下形式 x 1 7 置 旦，0 0 b 2 2 x 。，。7 z 7 0 e 0 岛 00 b m n b 。 其中e 。为f 阶矩阵，b i 为一f ) 阶矩阵 忙i 由x 作相应列置换而得。 下面描述算法。因a 非奇异，故b l ，中必有f f 阶非奇异子阵b 1 ，无妨设 e ，= 罢i ，拶i 非奇异。由子系统 b i ，? + 尽z = r ( i = l ，2 ，m )( 2 ) 的前f 个方程可解出x 。 b i i x ，= 一b l ，z + y 1 。 ( i = 1 ，2 ，m ) 其中b 1 。是e 的前f 行构成的矩阵，y 1 ，是m 的前f 行构成的列向量，即有 e 铡只制 将( 3 ) 的解肖，代入( 2 ) 中b 2 。( i = 1 ，2 ，m ) 对应的方程可得z 的方程 b z = 矿 ( 4 ) ( p 是已知的( 卜f ) 维向量) f - i 如果能解出z ，则可解出( 3 ) 因( 1 ) 可解，故必可由( 4 ) 求得z = b - 1 矿。 再代回( 3 ) ，即可得出 上海大学硕士学位论文 b ? x ? = 一b ib 一p + y 1 ( i = 1 ，2 ，一，1 1 ) 从而求出了全部的x 。 上述算法仅通过简单列置换将n 阶方程组( 1 ) 的求解转化成低阶方程组( 2 ) 和 ( 4 ) 的求解，而后者的阶数依次为 i ，丘，( 一f ) 若将此算法再应用于( 2 ) 和( 4 ) 的求解，可望阶数进一步降低。 上述算法的有效性取决于( 2 ) 和( 4 ) 的方程组的阶数