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

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

• 批准号: 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分解; Nested dissection; 最小自乗最小ノルム; ニュートン法

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

这项研究的重点是两个主要主题。首先，我们使用强制稀疏LU分解进行了对平行电路分析的研究。由于强迫稀疏的LU分解方法与直接方法有着密切的关系，以研究其有效的实施，因此有必要首先阐明直接方法并行实施的可能性和局限性。因此，使用嵌套解剖在平行计算机AP1000+上实施了LU分解方法，目前被认为是不规则稀疏矩阵问题的标准实践。结果，可以发现，无论问题的规模如何，线性溶液的速度提高速率的速度提高速率极为严重。发现这是因为在嵌套的解剖中，根部附近的计算复杂性，在该根附近的计算复杂性，当通过二进制树向后时，并行性较低，无论问题的规模如何，都占总数的一定百分比，从而限制了并行性。为了克服这个问题，必须在根附近并行进行相对较小的近距离矩阵。关于这一点，我们目前正在研究小型密集矩阵的有效平行实施的研究。其次，我们研究了使用约束和优化电路参数支持电路设计时必须解决的大规模非线性方程。在这样的问题下，条件可能会急剧恶化，或者可能会降低等级，在这种情况下，有必要找到最小二乘最小正方形方程的解决方案，其中具有大规模的稀疏矩阵作为牛顿方法中的系数。基于单数值分解或QR分解的方法通常用于此类问题，但是这些解决方案很难使用稀疏矩阵，并且对于大规模问题而言非常慢。相反，这项研究研究了基于LU分解的方法。结果，发现LU分解很快，因为它可以保留稀疏的矩阵，并且与密集的矩阵不同，稀疏矩阵的误差没有致命的增加。还通过实施此方法来解决大规模问题并将其与现有方法进行比较，还可以证明解决方案的有效性。