バンドマトリックス

数学、特に行列理論において、帯行列または帯行列は、非ゼロの要素が、主対角線と、両側の 0 個以上の対角線 で構成される対角帯に限定された疎行列です。

正式には、n × n行列A =( a _i,j ) を考えます。定数k ₁とk ₂によって範囲が決まる対角線で囲まれた帯域の外側のすべての行列要素がゼロである場合、

${\displaystyle a_{i,j}=0\quad {\mbox{if}}\quad j<i-k_{1}\quad {\mbox{ または }}\quad j>i+k_{2};\quad k_{1},k_{2}\geq 0.\,}$

するとk ₁とk ₂の量は帯域幅が低く、それぞれ上限帯域幅である。^[1]行列の帯域幅はk₁とk₂。言い換えれば、となる数kである。^[2]${\displaystyle a_{i,j}=0}$${\displaystyle |ij|>k}$

• k ₁ = k ₂ = 0のバンド行列は、帯域幅が 0 の対角行列です。
• k ₁ = k ₂ = 1のバンド行列は、帯域幅が 1 の三角対​​角行列です。
• k ₁ = k ₂ = 2の場合には、5 角対角行列となります。
• 三角行列
  • k ₁ = 0, k ₂ = n −1のとき、上三角行列の定義が得られる。
  • 同様に、k ₁ = n −1、k ₂ = 0の場合には下三角行列が得られます。
• 上側ヘッセンベルク行列と下側ヘッセンベルク行列
• 帯域幅が制限されている場合のテプリッツ行列。
• ブロック対角行列
• シフト行列とせん断行列
• ジョルダン正規形の行列
• スカイライン行列は「可変バンド行列」とも呼ばれ、バンド行列の一般化である。
• Lehmer 行列の逆行列は定数三角行列であり、したがって帯行列です。

数値解析では、有限要素法や有限差分法の問題からの行列は、多くの場合、帯状になっています。このような行列は、問題の変数間の結合の記述として考えることができます。帯状の特性は、変数が任意の大きな距離にわたって結合されていないという事実に対応しています。このような行列はさらに細分化できます。たとえば、帯内のすべての要素がゼロでない帯状の行列が存在します。

高次元の問題でもバンド行列が発生しますが、その場合、バンド自体もスパースになる傾向があります。たとえば、正方領域での偏微分方程式 (中心差分を使用) では、行列次元の平方根に等しい帯域幅を持つ行列が生成されますが、バンド内では 5 つの対角要素のみが非ゼロです。残念ながら、このような行列にガウス消去法(または同等のLU 分解) を適用すると、バンドが多くの非ゼロ要素で埋められてしまいます。

バンド行列は通常、バンド内の対角要素を格納することによって格納され、残りは暗黙的にゼロになります。

例えば、三角行列の帯域幅は1です。6行6列の行列

${\displaystyle {\begin{bmatrix}B_{11}&B_{12}&0&\cdots &\cdots &0\\B_{21}&B_{22}&B_{23}&\ddots &\ddots &\vdots \\0&B_{32}&B_{33}&B_{34}&\ddots &\vdots \\\vdots &\ddots &B_{43}&B_{44}&B_{45}&0\\\vdots &\ddots &\ddots &B_{54}&B_{55}&B_{56}\\0&\cdots &\cdots &0&B_{65}&B_{66}\end{bmatrix}}}$

6行3列の行列として保存される

${\displaystyle {\begin{bmatrix}0&B_{11}&B_{12}\\B_{21}&B_{22}&B_{23}\\B_{32}&B_{33}&B_{34}\\B_{43}&B_{44}&B_{45}\\B_{54}&B_{55}&B_{56}\\B_{65}&B_{66}&0\end{bmatrix}}.}$

行列が対称であれば、さらに節約できます。たとえば、上側帯域幅が 2 の対称 6 行 6 列の行列を考えてみましょう。

${\displaystyle {\begin{bmatrix}A_{11}&A_{12}&A_{13}&0&\cdots &0\\&A_{22}&A_{23}&A_{24}&\ddots &\vdots \\&&A_{33}&A_{34}&A_{35}&0\\&&&A_{44}&A_{45}&A_{46}\\&sym&&&A_{55}&A_{56}\\&&&&&A_{66}\end{bmatrix}}.}$

この行列は 6 行 3 列の行列として保存されます。

${\displaystyle {\begin{bmatrix}A_{11}&A_{12}&A_{13}\\A_{22}&A_{23}&A_{24}\\A_{33}&A_{34}&A_{35}\\A_{44}&A_{45}&A_{46}\\A_{55}&A_{56}&0\\A_{66}&0&0\end{bmatrix}}.}$

計算の観点から見ると、バンド行列を扱うことは、同様の次元の正方行列を扱うことよりも常に優先されます。バンド行列の複雑さは、行の次元がバンド行列の帯域幅に等しい長方形行列に似ています。したがって、乗算などの演算を実行するために必要な作業が大幅に減少し、多くの場合、計算時間と複雑さの面で大きな節約につながります。

疎行列は密行列よりも計算効率が高く、コンピュータストレージの利用効率も高いため、行列に順列を適用したり、その他の等価性や相似性の変換を適用したりして、帯域幅を最小化（またはフィルインを直接最小化）する方法を見つけることに重点を置いた研究が数多く行われてきました。^[3]

Cuthill -McKee アルゴリズムは、疎対称行列の帯域幅を削減するために使用できます。ただし、逆 Cuthill-McKee アルゴリズムの方がパフォーマンスが良い行列もあります。使用されている方法は他にも多数あります。

行と列の順列によって最小の帯域幅を持つ行列の表現を見つける問題はNP困難である。^[4]

• 対角行列
• グラフ帯域幅

• アトキンソン、ケンドール E. (1989)、数値解析入門、ジョン・ワイリー・アンド・サンズ、ISBN 0-471-62489-6。
• デイビス、ティモシー A. (2006)、スパース線形システムの直接法、産業応用数学協会、ISBN 978-0-898716-13-9。
• フェイジ、ウリエル (2000)、「グラフ帯域幅問題の NP 困難性への対処」、アルゴリズム理論 - SWAT 2000、コンピュータ サイエンスの講義ノート、第 1851 巻、pp. 129–145、doi :10.1007/3-540-44985-X_2。
• ゴルブ、ジーン H. ;ヴァン・ローン、チャールズ F. (1996)、マトリックス計算(第 3 版)、ボルチモア: ジョンズ・ホプキンス、ISBN 978-0-8018-5414-9。
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007)、「セクション 2.4」、Numerical Recipes: The Art of Scientific Computing (第 3 版)、ニューヨーク: Cambridge University Press、ISBN 978-0-521-88068-8。

• LAPACKとバンド行列に関する情報
• 帯状行列とその他の疎行列形式に関するチュートリアル