高効率な並列回路解析手法の研究

高效并联电路分析方法研究

基本信息

批准号：
08780245
负责人：
須田礼仁
金额：
$ 0.64万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1996
资助国家：
日本
起止时间：
1996 至无数据
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-08780245/
关键词：
回路解析並列処理 LU分解 Nested dissection 最小自乗最小ノルムニュートン法

项目摘要

本研究では主に二つのテーマで研究を行なった。第一に強制疎化LU分解法による並列回路解析の研究を行なった。強制疎化LU分解法は直接法との関連が深いため、その効率的な実装の研究のためにはまず直接法の並列実装の可能性と限界とを明らかにする必要がある。そこで、不規則疎行列問題に対して現在定石とされるNested dissectionを用いて並列計算機AP1000+上にLU分解法を実装、評価した。その結果、線形解法部分の速度向上率に対し問題規模によらず3から4倍という極めて厳しい限界があることが明らかとなった。この原因はNested dissectionにおいて二分木をさかのぼる際に並列性の低くなる根の付近の計算量が問題規模によらず全体の一定の割合を占めるため、並列性に限界が生じることであることがわかった。この問題を克服するには根の付近において比較的小規模の密に近い行列を効率良く並列に処理しなければならない。これに関し小規模密行列の効率的な並列実装の研究を現在進めている。第二に、制約条件を用いた回路設計支援や回路パラメタの最適化などの際に解く必要のなる大規模非線形方程式について研究を行なった。このような問題では条件が極度に悪化したりランクが落ちたりすることがあり、その場合ニュートン法内で大規模疎行列を係数とする最小自乗最小ノルム方程式の解を求める必要がある。通常はこのような問題には特異値分解またはQR分解に基づく方法が用いられているが、これらの解法は疎行列性を活用しにくく大規模問題ではかなり遅い。これに対し本研究ではLU分解に基づく方法について研究した。その結果、LU分解は疎行列性をよく保存するため高速であり、また密行列と違って疎行列では致命的な誤差の拡大が生じないことが分かった。またこの方法を実装して大規模問題を解いて既存の方法と比較することにより、解法の有効性を実証した。

这项研究主要集中在两个主题上。首先，我们利用强制稀疏LU分解方法进行并联电路分析研究。由于强制稀疏LU分解方法与直接法密切相关，为了研究其高效实现，首先需要明确直接法并行实现的可能性和局限性。因此，我们在并行计算机AP1000+上使用嵌套剖析实现并评估了LU分解方法，该方法是目前解决不规则稀疏矩阵问题的标准方法。结果表明，无论问题大小如何，线性求解部分的速度提高率都存在极其严格的限制，为 3 至 4 倍。我们发现，造成这种情况的原因是，在嵌套剖析中回溯二叉树时，无论问题大小如何，靠近根部并行度较低的计算量都占总计算量的一定比例，这就限制了计算量。并行性。为了克服这个问题，必须在根附近有效地并行处理相对小规模的稠密矩阵。对此，我们目前正在进行小规模密集矩阵的高效并行实现的研究。其次，我们对使用约束支持电路设计和优化电路参数时需要求解的大规模非线性方程进行了研究。在此类问题中，条件可能会变得极其恶劣，或者秩可能会下降，在这种情况下，需要在牛顿法中求解使用大规模稀疏矩阵作为系数的最小二乘最小范数方程。通常，基于奇异值分解或QR分解的方法用于解决此类问题，但这些解决方案没有利用稀疏矩阵的特性，并且对于大规模问题来说速度相当慢。相反，在本研究中，我们研究了一种基于 LU 分解的方法。结果，我们发现 LU 分解速度很快，因为它很好地保留了稀疏性，并且与稠密矩阵不同，稀疏矩阵不会导致致命的误差扩展。我们还通过解决大规模问题并将其与现有方法进行比较来证明了该方法的有效性。