線形システムの解法における行列構造の活用

nAG Library for Python Example集

このページは、nAGライブラリのJupyterノートブックExampleの日本語翻訳版です。オリジナルのノートブックはインタラクティブに操作することができます。

線形システムの解法における行列構造の活用

nAGの従業員であるReid Atchesonは、彼の個人ブログの最近の投稿で、最速の数値線形代数ルーチンは通常何らかの行列構造を活用していると述べました。Reidは特にToeplitz行列について議論を続けました。Reidの投稿を読んで、専門的なソルバーを使用することでどれほどの違いが生まれるのか疑問に思いました。

私の講演の1つであるHigh Performance Computing: There’s plenty of Room at the Bottomで、Prabhuらの論文A survey of the practice of computational scienceを引用しています。彼らは「分野を超えて、研究の質に大きな変化をもたらすには1桁のパフォーマンス向上が必要とされている」と述べています。したがって、理想的には私が行う高速化は少なくとも10倍の改善をもたらすはずです。

これを探るために、現在ご覧いただいているJupyterノートブック内でnAG library for Pythonを使用しました。元のノートブックはnAGのPython Examples GitHubリポジトリの線形代数セクションで入手可能です。

Toeplitz行列の線形システムの解法 - 構造を活用する例

Toeplitz行列はさまざまな応用で発生し、その例のいくつかはhttp://jack.valmadre.net/notes/2015/03/28/symmetric-positive-toeplitz/で紹介されています。

ここでは、係数行列がToeplitz行列である線形システムを解きます。まず、基本的な構造を利用せず、汎用のdgesv関数へのnAGのインターフェースを使用します。

from naginterfaces.library.lapacklin import dgesv   # A general solver
from naginterfaces.library.linsys import real_toeplitz_solve # A toeplitz solver
from pytictoc import TicToc
import numpy as np
import scipy.linalg

timer = TicToc()

# 実数の、対称的な、正定値のテプリッツ行列を構築する 
matrix_size = 5000
t = np.arange(0, matrix_size)
a = np.exp(-np.abs(t)/10)
# トープリッツ行列はその対角線によって定義されます。scipyを使用して対角線から完全な行列を構築できます
A = scipy.linalg.toeplitz(a, a)
# ランダムな右辺を構築する
np.random.seed(2)
b = np.random.rand(matrix_size,1)

timer.tic()
asol, ipiv, x_nag_gen = dgesv(A, b)
timer.toc()
Elapsed time is 2.079083 seconds.

同じ問題を解きますが、今度はreal_toeplitz_solve関数を使用します

# nAGのテプリッツソルバーは、bの次元がN,1ではなくNであることを要求します
# そこで、正しい次元で再構築します
np.random.seed(2)
b = np.random.rand(matrix_size)

timer.tic()
x_nag_toe, p = real_toeplitz_solve(matrix_size, a, b, wantp=False)
timer.toc()
Elapsed time is 0.023880 seconds.
# トーブリッツソルバーを使用することでどれだけ高速化されるか見てみましょう
5.39/0.035
153.99999999999997

Toeplitzソルバーを使用する方が100倍以上速いです。同じ答えが得られるか確認する必要がありますね? 厄介なことに、解行列の形状が異なっています!

# 一般的なソルバーからの解
x_nag_gen.shape
(5000, 1)
# トーブリッツソルバーからの解
x_nag_toe.shape
(5000,)

しかし、値は高い精度で一致しています

np.max(abs(x_nag_gen - np.reshape(x_nag_toe, (matrix_size, 1))))
1.341149413747189e-13

nAGライブラリのPython向け他の線形ソルバー - さまざまな行列構造を利用

あなたのアプリケーションではToeplitzソルバーを利用できないかもしれませんが、nAGライブラリの他の特殊な線形ソルバーの1つを活用できる可能性があります。行列の数学的構造に加えて、他の特殊化にはパック格納混合精度演算の使用が含まれます。同じ係数行列Aで複数の右辺を計算する必要がある場合、その状況に特化したソルバーもいくつかあります。以下は、利用可能なソルバーの一部とそのPythonドキュメントへのリンクです:

実数行列

複素行列

関連情報
MENU
© 譌・譛ャ繝九Η繝シ繝。繝ェ繧ォ繝ォ繧「繝ォ繧エ繝ェ繧コ繝�繧コ繧ー繝ォ繝シ繝玲�ェ蠑丈シ夂、セ 2024
Privacy Policy  /  Trademarks