（计算数学专业论文）代数多重网格法研究及在信号完整性分析系统中的应用.pdf

代数多重网格法研芄及在信号完整性分析系统中的应用 摘要 本文对代数多重网格法 a m g 在求解由偏微分方程有限元离散得到的大 型稀疏对称线性方程组上的应用进行了研究 特别针对信号完整性 s i 分析 系统中 对m a x w e l l 方程在时间域和频率域进行边型有限元 e d g ef i n i t e e l e m e n t 离散后得到的大型稀疏对称线性方程组上代数多重网格法的应用进行 了研究 针对s 1 分析系统中特殊的三棱柱网格结构提出了经过修改的a m g 算 法 s i a m g 并和k r y l o v 子空问法结合来求解s 1 分析系统中碰到的超大规 模线性方程组 s i a m g 算法中 由于三维有限元网格是由多层具有完全相同结构的二维 有限元网格相互连接组成 因此只需对一层网格进行租化 其中辅助矩阵的传 递算子的构造与普通a m g 法一样 系数矩阵的传递算子按照普通a m g 中方 法构造后再沿拓到整个三维有限元网格 粗网格上辅助矩阵和系数矩阵的计算 仍采用g a l c r k i n 方法 本文也对经典的迭代算法进行了描述 其中有g a u s s s e i d e t 法 实系数共 轭梯度法 c g 复系数共轭梯度法 c o m p l e xc g b i c g b i c o n j u g a t eg r a d i e n t 法 b i c g s t a b b i c o n j u g a t eg r a d i e n ts t a b i l i z e d 法 并且推导了实系数预处 理共轭梯度法 p c g 和预处理b i c g s t a b 法 针对s 1 分析系统在时间域生成的实对称正定 s p d 线性方程组 我们将 s i a m g 作为预处理共轭梯度法 p c g 中的预处理算子 针对频率域生成的 复系数稀疏对称线性方程组 将s i a m g 作为预处理b i c g s t a b 法中的预处理 算子 当然 后者也可用于求解s p d 线性方程组 最后 我们给出了s 1 分析系统碰到的一些实例 给出了网格粗化结果 并 对不同的迭代法进行了比较 相对于其它迭代方法 s i a m g 预处理方法具有 非常快的收敛速度 关键词 代数多重网格法 s i a m g s i a m g 预处理方法 信号完整性分 析系统 代数多重网格法研究及在信号完整性分析系统中的应用 a b s t r a c t i nt h i st h e s i st h ea l g e b r a i cm u l t i g r i dm e t h o di sc o n s i d e r e df o rs o l v i n gs y s t e m e q u a t i o n sw h i c ha r i s ef r o maf m i t ee l e m e n td i s c r e t i z a t i o no fp a r t i a ld i f f e r e n t i a i e q u a t i o n s i np a r t i c u l a rw ec o n s i d e rs y s t e me q u a t i o n st h a to r i g i n a t ef i o m a l le d g e f i n i t ee l e m e n td i s o r e t i z a t i o no fm a x w e l l se q u a t i o ni nt i m ea n df i e q u e n c yd o m a i n w h i c hi sw i d e l yu s e di ns i g n a li n t e g r i t ya n a l y s i ss y s t e x a s 1 1 1 eg e n e r a la l g e b r a i c m e t h o di sm o d i f i e dt of i tt h es p e c i a lm e s hs t r u c t u r ew ee l l c o u n t e ri np r a c t i c e a n d t h e ni su s e da sap r e c o n d i t i o n e ri ns e v e r a lp r e c o n d i t i o n e dg r y l o vs u b s p a e em e t h o d s t os o l v et h es y s t e me q u a t i o n si ns i g n a li n t e g r i t ya n a l y s i ss y s t e me f f i c i e n t l y i nt h em o d i f i e da l g e b r a i cm u l t i g r i dm e t h o d a st h e3 df i n i t ee l e m e n tm e s hi s c o m p o s e do fs e v e r a l2 df i n i t ee l e m e n tm e s h e sw h i c hh a v et h es a m es t r u c t u r e o n l y o n e2 dm e s hn e e dt ob ec o a r s e n e d t h ec o n s t r u c t i o no f a u x i l i a r ym a t r i c e sa n dt h e i r p r o l o n g a t i o no p e r a t o r si st h es a m ea si nt h eg e n e r a la l g e b r a i cm u l t i 鲥dm e t h o d b u t a f t e rt h es y s t e mm a t r i xp r o l o n g a t i o no p e r a t o r sb e i n gd e f i n e dv i a t h em e t h o d p r o p o s e di ng e n e r a lm u l t i 鲥dm e t h o d t h e yh a v et ob ee x t e n d e dt ot h e3 dm e s h a u x i l i a r ym a t r i c e sa n ds y s t e mm a t r i c e so nt h ec o a r s c f ll e v e l 躺c o m p u t e db yt h e g a l e r l d nm e t h o da su s u a l i i lt l l i st h e s i s s g v e r a ic l a s s i c a li t e r a t i v em e t h o d sa l ei n t r o d u c e d s u c ha s g a u s s s e i d e lm e t h o d c o n j u g a t eg r a d i e n tm e t h o d c o n j u g a t eg r a d i e n tm e t h o df o r c o m p l e xm a t r i c e s b i c gm e t h o da n db i c g s t a bm e t h o d p r e c o n d i t i o n e dc o n j u g a t e g r a d i e n tm e t h o da n dp r e c o n d i t i o n e db i c g s l a bm e t h o da r cd e r i v e df r o mt h e c o n j u g a t eg r a d i e n tm e t h o da n db i c g s t a bm e t h o d b o t ht h ea m gp r e c o n d i t i o n e dc o n j u g a t eg r a d i e n tm e t h o da n da m g p r e c o n d i t i o n e db i c g s t a bm e t h o dc a ne f f i c i e n t l ys o l v es y s t e me q u a t i o n si nt h e t i m ed o m a i n 1 1 1 ef o r m e rm a yf a i li nt h ef r e q u e n c yd o m a i n b u tt h el a t e ri sa l s oa l l e f f i c i e n ts o l v e r f i n a l l y n u m e r i c a ls t u d i e sa r cg i v e nf o rp r o b l e m si ns i g n a li n t e g r i t ya n a l y s i s s y s t e m 砀ec o a r s e n e dm e s h e sa r eg i v e ni nf i g u r e s s e v e r a ls o l v e r sa r ca p p l i e da n d t h e i rc o n v e r g e n c eb e h a v i o r sa r ec o m p a r e d a m gp r e c o n d i t i o n e dm e t h o d sh a v e m u c hh i g h e rc o n v e r g e n c et h a no t h e rm e t h o d s k e y w o r d s a l g e b r a i cm u l t i g r i dm e t h o d s i a m gs i a m gp r e c o n d i t i o n e d m e t h o d s s i g n a li n t e g r i t ya n a l y s i ss y s t e m 代数多重网格法研究及在信号完整性分析系统中的应用 致谢 首先非常感谢我的导师吴庆标教授 感谢他从我本科阶段开始一直到硕士 毕业在各方面对我的关怀 指导和帮助 特别是在学术上对我的指导 同时也非常感谢杭州讯美科技有限公司给我提供了代数多重网格法开发的 项目 非常感谢张中庆博士在开发过程中给予的指导和帮助 非常感谢我的同学徐伟权一直以来对我的帮助 特别是在我硕士论文完成 阶段对我的帮助 感谢师兄盛爱荣 同学何睿 张文 项目所在公司的同事罗 升阳 吴杭恩 蒋毅 张凌对我的帮助 最后 我要感谢我的父母以及粱婷 谢谢他们一直以来对我的支持和照顾 让所有的感谢归给那配得感谢的 i l l 代数多重网格 圭研究及在信号完整性分析系统中的应用 第一章绪论 随着微电子技术和计算机技术的不断发展 在涉及通信 国防 航空航天 工业自动化 仪器仪表等领域的电子系统设计工作中 集成规模越来越大 f o 数越来越多 单板互连密度不断加大 时钟速率越来越高 信号边缘速率越来越 快 产品研发周期的不断缩短 使得一次性设计的成功非常重要 信号完整性分 析的应用已经成为解决高速系统设计的唯一有效途径 目前 大多数的信号完整 性问题是电磁场问题 3 9 它可由m a x w e l l 方程表述 图1 1 为时间域和频率域 的m a x w e l l 方程 3 6 1 时间域频率域 v e e 旦v e 旦 岛毛 v b 0v 血日 0 甲 e 里 o v e j o j g h 2 0 a t 飞x h j 6 e j v x b 一丁p e 百o e 岛 图1 i 时间域和频率域m a x w e l l 方程 这些方程描述了电场和磁场在介质上 通过时同和空间的相互作用 数值仿真已成为信号完整性分析的强有力工具 它在计算机上模拟电子系统 的设计 并且给出信号完整性分析 给设计者以准确 直观的设计结果 可以极 大地缩短设计时间 降低设计成本 为了进行电磁场仿真 需要对 时间域或频率域 m a x w e l l 方程在仿真区域 上进行离散 以便计算机求解 主要的离散方法为有限元法和有限积分法 3 7 3 8 本文接下来的讨论都是基于m a x w e l l 方程边型有限元 e d g ef i n i t ee l e m e n t 离 散 离散后 我们得到如下线性方程组 a x b 1 1 对于从时间域m a x w e l l 方程离散得到的线性方程组 系数矩阵a er 雌 嵋是 对称正定的稀疏矩阵 b r 啊是给定的右端向量 x r 啊是需要求解的向量 对于从频率域m a x w e l l 方程离散得到的线性方程组 系数矩阵一 c 雌州是 代数多重网格法研究及在信号完整性分析系统中的应用 复系数的稀疏对称矩阵 右端向量b c 啊 解向量x c 坷 这里孵为离散区域有限元网格边的条数 一般有 譬 o h 其中 d 1 2 3 为空间维数 h 为网格参数 通常非常小 因此线性方程组的规模通 常是非常大的 而且系数矩阵a 的条件数往往是 一 o h 2 因此经典迭代法 收敛速度非常慢 可喜的是 多重网格法 m g 和k r y l o v 子空间法的有效结合 是求解这类方程组的高效方法 多重网格法是在离散区域有限元网格的基础上构造出多个层次的网格 这些 网格随着层数的增加越来越租 点和边的数量越来越小 线性方程组经过迭代 光滑后 其高频部分误差会很明显地被削减 但低频部分误差很难被削减 但是 当我们把迭代光滑后的误差通过一定机制传递到下一层网格上后 又变成既包含 高频误差又包含低频误差 因此可以在下一层上继续光滑迭代 再把误差传递到 更下一层网格 这样一直到最后一层网格 由于规模已经很小 就可以用直接 法求解 然后将结果返回到上一层网格 作为该层解的修正 再作光滑迭代 把 结果返回到更上一层网格 直到第一层网格 解修正后再作光滑迭代 我们就 得到了线性方程组的近似解 其结果误差会比经典迭代法求得的误差小很多 在实际应用中 多重网格法不仅直接用来求解线性方程组 而且作为预处理 迭代法的预处理步骤更是个理想的选择 可以达到很好的收敛速度 可用来求解 大规模线性方程组 多重网格法根据网格层次的构造方法又分为凡何多重网格法 g m g 和代 数多重网格法 a m g 最开始提出的是g m g 后来发展出a m g a m g 将网格 层次的构造完全数值化 通过引入辅助矩阵来代表虚拟的网格 替代了g m g 的 实际网格 极大地扩大了多重网格法的适用范围 在实际开发中 我们碰到了一种特殊的网格结构 三棱柱网格 针对这样 的特殊结构 本文提出了分层构造网格层次的算法 既保证了多重网格法的高效 性 又提高了网格层次构造速度 本论文第二章讨论了大型稀疏线性方程组的迭代解法 并推导了预处理方 法 第三章讨论了通用的代数多重网格法 第四章讨论了三棱柱网格结构的代数 多重网格法及其与预处理方法的结合 第五章给出了数值算例 代数多重同格法研究及在信号完整性分析系统中的应用 第二章大型稀疏矩阵迭代法 随着计算技术的发展 计算机的存储量日益增大 计算速度也迅速提高 直 接法 如g a u s s 消去法 平方根法等 在计算机上可以求解的线性方程组的规模 也越来越大 但直接解法大多数均需对系数矩阵爿进行分解 因而一般不能保持 彳的稀疏性 而实际应用中 特别是偏微分方程的数值求解 常常遇到的就是大 型稀疏线性方程的求解问题 并且绝大部分的计算都是用在求解上 因此寻求能 够保持稀疏性的有效算法就成为一个非常重要的研究内容 迭代法是在此背景下发展起来的求解稀疏线性方程组的有效方法 它按照某 种规则构造一个向量序列 使其极限刚好是线性方程组的精确解 古典的迭代法有j a c o b i 迭代和g a u s s s e i d e l 迭代 在系数矩阵满足一定性质 的条件下 具有良好的收敛性 后来有人提出对o a u s s s e i d e l 迭代进行加速的超松弛 s o r 迭代 虽然收 敛速度比o s 法和j a c o b i 法有数量级上的改进 但需要确定松弛参数 这常常 是非常困难的 5 0 年代h e s t c n e s 和s t i e f e l 提出了一种不需要确定任何参数的求解对称正定 线性方程组的方法一共轭梯度 c g 法 后续的研究也得到了前所未有的发 展 发展出了一系列的c g 方法 目前有关的方法和理论已经相当成熟 并且已 经成为求解大型稀疏线性方程组最受欢迎的一类方法 本章介绍g a u s s s e i d e l 法 实系数共轭梯度 c g 法 复系数共轭梯度 c o m p l e xc o 法 b i c g b i c o n j u g a t eg r a d i e n t 法 b i c g s t a b b i c o n j u g a t e g r a d i e n ts t a b i l i z e d 法 最后推导了实系数预处理共轭梯度法 p c g 和预处理 b i c g s t a b 法 值得一提的是 接下来两章将要介绍的代数多重网格法是预处理 方法一个非常理想的预处理算子 2 1 单步线性定常迭代 设求解的线性方程组为 出 b 2 1 1 任何一种迭代格式都是根据某种特定的规则 构造一个向量序列 一 使 代教多重同格法研究及在信号完整性分析系统中的应用 其极限为线性方程组的解 一般可以表示成 工 m 耵 一 g 2 1 2 其中m 仆 分成别为第k 步迭代矩阵和常数项 如果迭代矩阵和常数项 均和迭代次数无关 那么迭代是单步线性定常迭代 石 幻 f 工 叫 g 2 1 3 有关单步线性定常迭代 2 1 3 的收敛性有下面两个定理 定理2 1 1 2 0 定理4 2 1 单步线性定常迭代 2 1 3 收敛的充分必要条件 是迭代矩阵肘的谱半径p m l 算法2 1 2 为g a u s s s e i d e l 迭代的算法描述 给定初值x o 力r 女 l 2 向 i l 2 埘 工 0 力r 1 2 9 o o i i i l 厅 而 蔚 嘞矿 e n d x i i 伯l x 1 f n h e n d 工 如果收敛 停止迭代 e n d 算法2 1 1j a f o b i 迭代 2 1 3 收敛性分析 给定初值r o 如 t l 2 力ri l 2 坍 盯 0 扣r l 2 i i o o n 口霉1 e n d f o r f l n 盯 盯 嘞矿 e n d 舛 6 一盯 如果收敛 停止迭代 e n d 算法2 1 2g a u s s s e i d e l 迭代 由于迭代矩阵的谱半径很难计算 一般采用其它途径判断迭代的收敛性 下 面给出其中两个定理 定理2 1 3 2 0 定理4 2 6 若系数矩阵 对称 对角线元素吼 0 f l 2 j 则j a c o b i 迭代收敛的充要条件是4 和2 d a 都正定 定理2 1 4 2 0 定理4 2 7 若系数矩阵彳正定 则g a u s s s e i d e l 迭代收敛 代数多重同格法研究及在信号完整性分析系统中的应用 定理2 1 5 2 0 定理4 2 9 若系数矩阵a 是严格对角占优的或不可约对角 占优的 则j a c o b i 和g a u s s s e i d e l 迭代收敛 2 1 4 其它迭代方法 1 9 此外还有超松弛迭代 s o r 法 对称超松弛迭代法 s s o r 法 见文献 2 2 线性非定常迭代 线性非定常迭代和线性定常迭代不同的是每一步迭代的迭代矩阵或常数项 不一样 一般地 常数项会在迭代过程中不断被更新 像共轭梯度法就属于这一 类方法 2 2 1 共轭梯度法 共轭梯度法 c g 为求解对称正定线性方程组的有效方法 它可由多种途 径引入 像 2 0 就从较为直观的最优化问题引入该方法 在此不赘述 算法2 2 1 为共轭梯度法的算法描述 2 2 2 复系数共轭梯度法 上一小节提出的共轭梯度法只适应对称正定矩阵 我们采用 3 1 中的适用于 复系数矩阵的共轭梯度法 算法2 2 2 为复系数共轭梯度法算法描述 代数多重同格法研究及在信号完整性分析系统中的应用 给定初值x b a x p r r r 加k l 2 k m 3 x i fk 1 p e l s e 9 p lp p r p p e n d 1 和 口 p p r w 工 x 4 口p 一a w i f 0 r l l l l b l is s b r e a k e n d p p 口 r e n d 算法2 2 1 共轭梯度法 适用于一是对称正定矩阵的情况 2 2 3 适用于对称矩阵的b i c g 法 给定初值 r b a x 一8 r l l l y f p p l f o ri l 2 j a t a t c 1 和 口 一i w 工2 z 十a p 4 口1 i f i r 酬 b r e a k e n d 彳日 一矿0 妒0 2 p p b i l e n d 算法2 2 2 复系数共轭梯度法 适用于 4 是复系数对称矩阵的情况 其中a 为a 的共轭转置 通用的b i c g b i c o n j u g a t eg r a d i e n t 算法是适用于系数矩阵是非对称矩阵 的情况 但这里只介绍适用于系数矩阵是对称矩阵的算法 具体见算法2 2 3 更 具体的描述见 2 2 1 2 2 4b i c g s t a b 法 下面介绍适应复系数矩阵的b i c g s t a b b i c o n j u g a t eg r a d i e n ts t a b i l i z e d 它比b i c g 具有更好的收敛速度 且不需要计算矩阵的共轭转置 具体见算法 2 2 4 更具体的描述见 2 2 代数多重罔格法研究及在信号完整性分析系统中的应用 给定初值x b a x p r p r e r f o rk k 2 k a 正4 y w 却 口 p r e 一 善 x 口p r 一洲 i f i i v l l b l l s b r e a k e n d p p p r c o b p 5 p r 七 b p e n d 算法2 2 3 对称矩阵的b i c g 法 2 2 5 收敛性分析 给定初值x r 6 一a x p 口 p i v p 0 屹 如 i l 2 k m a x p 瓴 口 呈 竺 p p p p d p w v p 却 瑾 p t o n s 一鲫 t a s w f 曲l t f x x 口p w s j w t i f l h i u b n s b r e a k e n d e n d 算法2 2 4 b i c g s t 舳法 定理2 2 1 2 0 定理5 3 2 如果a i b r a n k b k 则共轭梯度法至多 k l 步即可达到方程组的精确解 定理2 2 2 2 0 l 定理5 3 3 用共轭梯度法求锝的 z 有如下的误差估计 一毛j a 2 蒜归 吼 叫 其中心 爿 圳爿一也为j 4 的条件数 五为线性方程组 2 1 1 的精确解a 虽然这是一个十分粗糙的估计 而且计算时其收敛速度往往那个要比这个估 计快得多 但是它却揭示了共轭梯度法的一个重要性质 只要系数矩阵是十分良 代数多重网格法研究及在信号完整性分析系统中的应用 态的 即tz 1 则共轭梯度法就会收敛得很快 2 2 6 其它迭代方法 还有其它一系列迭代方法在本章中没有介绍 如用于求解对称不定线性方程 组的残量极小化法和s y m m q 法 2 8 复系数对称q m r 法 4 1 用于求 解非对称线性方程组的g m r e s 法 2 9 a m o l d i 法 2 9 q m r 法 4 0 c g n r 1 9 1 c g sq 1 9 等 2 3 预处理方法 当线性方程组 2 1 1 的系数矩阵仅有少数几个互不相同的特征值或者非常 良态时 共轭梯度法就会收敛得非常快 这就促使我们在应用共轭梯度法时 首 先应设法将 2 1 1 转化为一个系数矩阵只有少数几个互不相同的特征值或非常 良态的等价方程组 然后应用共轭梯度法进行求解 预处理共轭梯度法正是基于 这个基本思想产生的 它是先将 2 1 1 转化为 血 b 2 3 1 其中j c a c 白 5 c b 这里要求c 是对称正定的 我们的目的是 选择适当的c 使a 具有所期望的良好性质 注 上面的转化是 2 0 里提出的 此外 ys a m 在 3 0 里提出另一个类似的预处理二i l 1 a r 石 5 l 一6 其中m 厶矿为对称正定矩阵 这只是中间过程 两者的推导结果是一样的 2 3 1 预处理共轭梯度法 我们分别用c a c 一 c x c b c 1 印替换算法2 2 1 里的4 x b p 并记 c 2 整理后就得到预处理共轭梯度 p c g 算法 见算法2 3 1 代数多重同格法研究及在信号完整性分析系统中的应用 2 3 2 预处理b i c g s t a b 法 我们分别用c 1 a c 一 c x c b c 1 r c c v o c 1 t 替换算法2 2 4 里的a x b p v j t 并记m c 2 整理后就得到预处理b i c g s t a b 法 见算法2 3 2 我们再用 代替m 1 代入算法2 3 2 就得到实用的预处理b i c g s t a b 法 见算法2 3 3 给定初值x r b a x 给定初恤 p 口 w l 7 2 6 一血 v p 0 加t 2 l2 胁彻 r 求解胞 他 力七 1 办刎 叭一 p 瓴 m i e 1 二 p 兰 p 2p 阳 j p 励 p m l r 触啪d i v 却a p 1 a m 三0 萼二 x x c t p f a s i f h l l b l l s f w t s t m 1 b 坤a k z x 口p 坩 e n d m 1 j w m 一1 t p i f i r v a b l l 占 p r r g e n d b 触 end 算法2 3 1 预处理 共轭梯度法 算法2 3 2 预处理 b i c g s t a b 法 l o 给定初值x b a x m 一 p 口 w p l v p 0 o rk l2 x m a x p 瓴 口 p 堡 pw p 2p p f l p w v 1 求解胁 却得v 口 r o r j 一鲫 t a s 求解m z f 得z 1 r f s t z x x 4 口p w r j w z i f 忪一b h l l b i 占 b r e a k e n d e n d 算法2 3 3 实用预处理 脚c g s t a b 法 代数多重同格法研究及在信号完整性分析系统中的应用 2 3 3 分析 预处理共轭梯度法中 矩阵m 称为预处理矩阵 预处理共轭梯度法近似解向量x n 满足 卜囊8 4 删 且 f n s t 3 t j e n t i s j c n 嵋 n 以 其中 是节点i 的邻接点集合 是强连接点集合 是强连接到i 的点 的集合 截断函数定义如下 代数多重网格法研究及在信号完整性分析系统中的应用 8 甄风 口 m a x 占 说明 如果截断函数取第二项 则s 叮 s 取第一 三项 则 粗网格的构造可以在以下两个准则的指导下完成 c 1 对每个f 嵋 e 要么属于嵋 要么至少强连接到c 中的一个点 c 2 畦是其中任何两点都互不形成强连接的最大子集 下面介绍r u g e 和 t t l b e n 提出的粗化算法 8 1 算法分为两阶段 第一阶段 快速选取尽可能多的记点 以尽量满足 c 2 起初 选取s 盯最大的f 作为磁点 而s 叮置入衅中 之后 算法趋向于选取强影响更多 p i i 弘7n 嵋i 最大 的顶点为嵋点 这样可以减少 畦一嵋连接 以尽量满足 c 2 而且 算法保证了每个嵋点至少强依赖于一个嵋点 见算 法3 2 1 和算法3 2 2 算法3 2 1 粗化第一阶段算法 代数多重罔格法研究及在信号完整性分析系统中的应用 算法3 2 2 与算法 a 等价的算法 3 2 1 更容易理解3 2 2 更容易实现 第二阶段 对余下的顶点进行检测 算法3 2 3 为第二阶段算法的具体描述 其中 州 歪一岛悔蚓 j e 1 7 代数多重网格 去研究及在信号完整性分析系统中的应用 算法3 2 一 c 粗化第二阶段算法 图3 2 为网格粗化的一个示意图 可以帮助理解租化算法 在对第 层粗化后 将嵋中点设为第 1 层网格节点集t 即峨 卜 畦 注 1 实际粗化只需要辅助矩阵占就可以进行 并不需要几何网格 2 这里嵋中保存的是第 层网格上的节点索引 如图3 2 中的f e w 而以 保存的是第 l 层网格上的节点索引 如图3 2 中的 嵋 因此 嵋 卜嵋后 网格节点会被赋于新的索引值 代数多重罔格法研究及在信号完整性分析系统中的应用 3 1 3 传递算子 细网格节点吖口粗网格节点 1 k f e w e 嵋i 图3 2 网格粗化示意图 同一个节点 在细网格中编号为f 但在粗网格中编号为 像算法3 1 所描述的 粗网格上矩阵 包括辅助矩阵和系数矩阵 的构造完 全取决于传递算子和当前网格的矩阵 第一层网格上辅助矩阵是z 矩阵 系数矩 阵也有很好的性质 比如在时间域上离散m a x w e l l 方程得到的系数矩阵是对称正 定的 因此我们必须对传递算子加一些限制条件 使得粗网格上矩阵同样具有 当前网格矩阵的性质 下面介绍r e i t z i n g e r 和s c h s b e r l 提出的传递算子 1 2 3 细网格到粗网格映射 在上一小节的最后我们提到 在对第f 层有限元网格w f w 研 粗化后 将 畦中点设为第 l 层网格节点集以 节点会被赋予新的索引值 像图3 2 的情 况 同一个节点在w 中的索引为f 而在嵋 中的索引为 因此 当我们对第 l 层网格节点指定新的索引值后 就可以得到从嵋到吆 的一对一映射珊c i d x 嵋 吆l 或者 代数多重网格法研究及在信号完整性分析系统中的应用 例如图3 2 中 i d x i 峨 胁 嵋 我们将w 归类到互不相交的聚类 酱 吆l 中 其中 幔 n 7 a u w t i 图3 3 为节点归类示意图 这里涉及到如何归类 像图3 3 中 既可以令 e i 也可以令 e i t 这可 以采用一个很简单的策略解决 一般地 如果f 是细节点 我们采取与f 邻接的 所有粗节点中与 距离最近的节点所在聚类作为f 的聚类 比如在图3 3 中 离 f 的距离比 离t 的距离小 因此令 i 有了上面的归类 我们就可以把从嵋到心 f 恻i a x 沿拓到从 f t 到以 i a k w 一嵋l 或者 嵋 矗 w 例如图3 3 中 f i d x r i d x s 映射肠c 沿拓之后 聚类 嚣 也可以表示为 i w 豇扣u f 粗网格节点集合可以表示为 吆l i d x o f e 辅助矩阵传递算子 从第 层到第 l 层的辅助矩阵传递算子日 r 町 喝 1 w i 仁 i 9 所有元素为i 或0 定义如下 c 矗卢 f e 嵋7 键 代敛多重网格法研究及在信号完整性分析系统中的应用 粗网格辅助矩阵 i k 细网格节点w口粗网格节点w 九 j e w f j k e l l e i s e 图3 3 粗化后网格节点归类示意图 离f 距离比离 更近 因此 e i i 根据g a l e r k i n 方法计算 即 日 卑 7 4 毋 爵圃 3 3 n x n kn k x n n x n n x n k 图3 4 辅助矩阵g a l e r k i n 方法示意图 下面证明 马 代表第 l 层虚拟有限元网格且马 是z 矩阵 引理3 1 式 3 3 与下式等价 局 f 弓 目 弓 掣 3 4 r e rs e l l 2 1 代数多重同格法研究及在信号完整性分析系统中的应用 证明 马 f 异 7 蜀弓1 f 彳 7 马 弓 毋4 7 马 c ri f 马 甲 f 根据定义式 3 2 知 彳 o 当且仅当r 甲 d o 当且仅当s i 因此 3 4 式成立 引理3 2 若对所有的r s e l 骂 0 则 钆b o 证明 本引理从引理3 1 可以直接得到 定理3 1 对于 屹 f 当且仅当至少存在一条细边连接聚类 和j 7 f 时 粗边 f 存在 证明 若存在一条细边连接聚类 和j 7 即j r e i c s e l 7 t 1 i j 使得 局 o 又由引理3 1 及定义式 3 1 得 马 f 马 因此 瓯 口 o e o 即粗边 f 存在 反之 若粗边 f 存在 则由定义式 3 1 知 且 o 再由引理3 2 知 3 r i f w s i jc w r s 使得 马 0 例如图3 3 中 细边 s r e j e i j 存在 因此租边 f 存在a 定理3 2 日 满足定义式 3 1 即马 是z 矩阵 证明 见定理3 1 的证明 在计算得目 后 我们就可以确定粗网格边哌 因此就得到了虚拟粗网格 喝 幢 见图3 4 我们给出了一张由2 2 个点 5 0 条边组成的有限元网格的粗化结果 见图3 5 代数多重网格法研究及在信号完整性分析系统中的应用 细网格节点口粗网格节点 f 之 e 吖细网格边 u 矗 噍 粗网格边 图3 4 虚拟粗网格 a 细网格 2 3 b 粗化后得到的相节点 代数多重同格法研究及在信号完整性分析系统中的应用 c 细节点到粗节点的映射 d 通过辅助矩阵得到的粗网格 粗线表示映射关系 e 细网格节点和边的编号 o 粗网格节点和边的编号 图3 5 a f 一张由2 2 个点 5 0 条边组成的有限元网格的租化结果 2 4 代敦多重同格法研究及在倌号完整性分析系统中的应用 系数矩阵传递算子 从第 层到第 l 层的系数矩阵传递算子异 r 唧 嵋 吖 i 吖1 1 w i 对于细网格边f 2 吖 f 2 和粗网格边 止 e 屹 j l j 2 彳定义如 下 f l 当 工 五 硒r 胤1 2 曰 口 卜1 当u 1 2 鼬c 磁c 3 5 0 其它 例 图3 4 中 弓 1 粗网格系数矩阵 根据g a l e r l d n 方法计算 即 4 彳 1 4 耳 引理3 4 式 3 6 与下式等价 4 f 彳 4 彳 疗 r e l l3 d 证明 见引理3 1 对系数矩阵传递算子的性质分析可见文献 3 团 圃 3 6 3 7 n a x n 厶n k x n n x n n x n k 图3 6 系数矩阵g a l e f l d n 方法 代数多重网格法研究及在信号完整性分析系统中的应用 3 2 代数多重网格法的求解 v 循环 3 2 1 算法描述 在构造了多重网格后 我们就可以进行求解 我们这里只介绍v 循环 见 算法3 3 描述 更多的方法见文献 1 3 1 第1 6 页 这里不赘述 算法3 3 代数多重网格法求解 v 循环 算法 3 2 2 光滑迭代算子 对于系数矩阵是实系数对称正定 s p d 的情况 经典的迭代法都可以作为 光滑迭代算子 比如j a c o b i 迭代 g a u s s s e i d e l 迭代等 也可采用a r n o l d 光滑算 子 见文献 4 以及h i p t m a i r 光滑算子 见文献 5 对于系数矩阵是复系数的情况 可以采用复数版本的a r n o l d 光滑算子 见 文献 4 如果矩阵g a u s s s e i d e l 迭代收敛 当然也可采用g a u s s s e i d e l 迭代 g a u s s s e i d e l 的前向和后向迭代见算法3 4 和算法3 5 代数多重同格法研究及在信号完整性分析系统中的应用 给定初值x o f o rk l 2 f o r l 2 一坍 仃 0 如 j l 2 i 1 t l r 盯 妒 e n d f o r f 1 n 口 盯 q 乎枷 e n d 6 一t r a e n d 给定初值 加k 1 2 向ri n n i 1 盯 0 加 1 2 i i 盯 盯 嘞够 e n d 蹄 i k 撑 矿 盯 嘞 山 e n d 举 一盯 口f i e n d 算法3 4g a u s s s e i d e l 前向迭代算法3 5g a u s s s e i d e l 后向迭代 3 2 3 直接解法的选取 由于最后一层的线性方程组的规模很小 比如未知数个数为5 0 0 因此一 般的直接解法都适用 而且求解速度很快 我们在数值实现时采用的是多重前线 解法 3 2 4 收敛性说明 文献 2 6 3 l 中给出了特定的多重网格法的收敛性分析 文献 3 2 1 给出了 p e t r o v g a l e r k i n 代数多重网格法的收敛性分析 具体见相关文献 虽然无法在理论上给出代数多重网格法收敛性普遍性的证明 但大量的数值 实验显示代数多重网格法的收敛速度可以和几何多重网格法相媲美 代数多重网 格法在各个工业领域里的应用可见文献 9 1 0 1 5 1 6 1 代数多重网格法研究及在信号完整性分析系统中的应用 第四章代数多重网格法在信号完整性分析系统中的 应用研究 迭代法与直接法比较的一大优势是只需要0 的内存空间 但是经典的迭 代算法收敛速度取决于线性方程组系数矩阵的条件数 我们期望找到最佳的解 法 其收敛速度与线性系统的网格尺寸等参数无关的 现行系统的解是有限元法 的一个很重要的方面 几何和代数 多重网格法法和以多重网格法作为预处理 步骤的k r y l o v 子空间方法满足了这样的最佳解法的要求 由于后者稳定性和有 效性比前者好 因此在实际应用中普遍采用后者 在信号完整性分析系统中 要求解的线性方程组的规模经常会非常大 有些 情况下未知数的个数会达到千万甚至上亿的规模 但是在目前的硬件条件下 直接解法由于受空间和时间的限制 一般只能求解到几十万个未知数的规模 并 且 有些情况下系数矩阵的条件数并不好 经典的迭代算法收敛性会非常慢 因此 多重网格法和k r y l o v 子空间法的结合自然成为信号完整性分析系统 中理想的求解方法 信号完整性分析系统中普遍采用非常灵活的非结构网格剖分 几何多重网格 法就失去了其用武之地 我们自然把目光投向代数多重网格法 我们碰到了一类特殊的网格结构 三棱柱网格 不能将第三章中所描述的 代数多重网格法直接拿来用 因此我们针对这样的区域提出了特殊的代数多重网 格法 我们称之为s i a m g 算法 本章主要介绍s i a m g 与第三章中描述的一般代数多重网格法不同的地方 4 i 介绍特殊的网格结构 4 2 介绍s i a m g 的构造 4 3 介绍两个以s i a m g 作 为预处理步骤的k r y l o v 子空间方法一预处理共轭梯度法和预处理b i c g s t a b 法 4 1 特殊的网格结构 在我们的信号完整性分析系统中 由于三维区域的特殊结构 剖分后得到的 有限元三维网格具有如下特点 代教多重同格法研究及在信号完整性分析系统中的应用 a 三维网格由一定数量 一般小于2 5 的完全相同的平面三角网格组成 并且每张平面网格的几何结构完全一样 b 每两张平面网格的节点对之间有垂直边相连 这样的网格可以看成是很多个三棱柱拼接而成的 见图4 1 4 2s i a m g 的构造 4 2 1 粗化算法 图4 1 三棱柱网格 s r e t z i n g e r 和j s c h 6 b e r l 提出的粗化算法 见第三章 为方便 以后称为 i 峪粗化 适用于二维三角网格或三维四面体网格 但对于像图4 1 这样的三棱 柱网格来说并不是理想的方法 这是因为r s 粗化会在垂直方向上对点进行删选 而这样做可能会引起网格结构的混乱 粗化后得到的不再是三棱柱网格了 并 且还会使得传递算子的定义变得复杂 其实我们可以利用网格的几何特性瓴b 设计更为合理的租化算法 我们先提 取出三棱柱网格w 矿 w 的第一水平层三角网格 记为 矽 w 例如 图4 2 网格为从图4 i 网格中提取出的水平层网格 图4 2 从三维网格 图4 1 提取出的水平层网格 然后对 进行i l s 粗化 这个过程采用算法3 2 即可 令蔬 品 在对第 层有限元网格动 研 薪 粗化后 将c 中点设为第 l 代数多重阿格法研究及在信号完整性分析系统中的应用 层网格节点集孑卫 这样我们就可以按照和r s 粗化中完全一样的方法定义映射 菇 i 品 图4 3 粗化后水平层网格 其中正方形点表示粗节点 4 2 2 辅助矩阵及其传递算子 由于粗化只在一水平层网格上进行 因此从第z 层到第1 i 层的辅助矩阵传 递算子异 r 矶碥 耐 i 讲l 为 p 1 4 1 3 2 一样的定义即可 即 聊 卢似吐旭峨 魂 其中i 丢为上一节定义的从细节点品 到粗节点观 的映射 粗网格辅助矩阵根据g a l c r k i n 方法计算 即 巩 f 7 马异 4 2 类似于定理3 1 3 2 马 代表第1 1 层虚拟有限元网格且马 是z 矩阵a 计算得辅助矩阵后 我们就得到了第1 1 层的虚拟有限元网格 w i l 诫l w i 1 见图4 4 图4 4 水平层虚拟粗网格 辅助矩阵具有和第三章中所描述的一样性质 即 马 代表第 1 层虚拟有限元网格且马 是z 矩阵 4 2 3 系数矩阵及其传递算子 辅助矩阵及其传递算子与网格节点对应 由于三棱柱网格每一个水平层网格 代数多重同格法研究及在信号完整性分析系统中的应用 一一 接下来我们就可以将磊 并呻诫一沿拓到浊 w 一幢 其中w 为第 层三 棱柱网格节点集合 我们假设计中节点是按照水平层网格依次排列的 并且不 同水平层网格节点在本层中相对位置是一样的 触 可通过下式得到 i a b c n 女一1 卫 胁 i 垆l 研 o 丽 o s s 胛 4 3 其中 1 w l 为第 层三棱柱网格点数 帮苫p f 为第 层水平层网格点数 我们假设研中边也是按照水平层网格依次排列的 并且不同水平层网格边 在本层中相对位置是一样的 则从第1 层到第l 1 层的系数矩阵传递算子 彳 r 研 峨 孵 l k i 吆 对于细网格边f e 吖 和粗网格边 五 吒 五