強制疎化、LU分解の並列計算の研究

强制稀疏与LU分解并行计算研究

基本信息

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

项目摘要

強制疎化LU分解はオリジナルのアルゴリズムである。本研究ではLU分解や連立一次方程式の解法など関連するアルゴリズムの最新の並列処理技術について調査し、強制疎化LU分解法の並列処理の方針については知見が得られた。これらの知見およびそれに基づく強制疎化LU分解法の並列処理については、本年度中に発表することができなかったが、近いうちに研究発表をしたいと考えている。本研究では、研究テーマの周辺に位置する、線形計算の高速・並列アルゴリズムについても成果が得られた。まず、固有値解法についてはダブルシフトQR法の並列処理についてさらに研究を進めた。並列化オーバーヘッドの解析を行い、マルチシフトアルゴリズムと漸近的な並列化効率について比較を行なった。その結果についての論文を現在投稿中である。また、最近注目を集めている高速計算法に、高速多重極子展開法(FMM)がある。これは特殊な行列とベクトルの積の高速計算アルゴリズムであるが、本研究では多項式の内挿を経由させることによりこれまでよりも広い範囲の行列にこの解法が利用できることを示した。これにより球面調和関数変換などの応用上重要な変換計算がFFT並みのオーダーで計算できるようになることが分かった。今後この手法をさまざまな計算に応用し、アプリケーションに適用して評価をして行く予定である。FFTもある種の行列とベクトルの積の高速計算アルゴリズムであるが、これについてもルジャンドル変換への応用やブロックサイクリック分割を用いた並列処理などについて研究を進めている。また、連立一次方程式については非等間隔格子や球面格子上でのポアソン方程式に対する高速アルゴリズムについても研究を行ない、一部発表も行なった。

强制稀疏LU分解是一种原始算法。在本研究中，我们研究了LU分解和求解联立线性方程等相关算法的最新并行处理技术，并获得了关于强制稀疏LU分解的并行处理策略的知识。虽然我们今年未能展示这些发现以及基于它们的强制稀疏 LU 分解方法的并行处理，但我们希望在不久的将来展示我们的研究。这项研究还产生了用于线性计算的高速并行算法的成果，这些都是该研究主题的外围内容。首先，针对特征值求解方法，我们进一步研究了双移QR方法的并行处理。我们分析了并行化开销，并比较了多移位算法和渐近并行化效率。目前正在提交有关结果的论文。另一种最近引起关注的高速计算方法是快速多极展开法（FMM）。这是一种用于矩阵和向量乘积的特殊高速计算算法，但在本研究中，我们通过使用多项式插值表明，该解决方案可以用于比以前更广泛的矩阵。人们发现，这使得可以为诸如与 FFT 相同阶数的球谐变换等应用执行重要的变换计算。未来，我们计划将这种方法应用到各种计算中，并在应用中进行评估。 FFT也是一种矩阵和向量乘积的高速计算算法，我们目前正在研究其在勒让德变换和使用块循环分区的并行处理中的应用。关于联立线性方程组，我们还对非均匀网格和球形网格上泊松方程的高速算法进行了研究，并做了一些介绍。