疎行列

同義語:sparse matrixスパース行列

概要

疎行列(sparse matrix)とは、成分のほとんどが 0 で、非零成分の個数と位置を利用して記憶と計算を節約する行列のことである。圧縮行形式では行列とベクトルの積が非零成分の個数に比例する手間で計算できる。非零パターンは有向グラフで表され、行列の冪の非零成分は長さの決まった歩道に対応する。行の入れ替えのない LU 分解の因子の非零パターンは、成分の値によらない記号的な消去で上から押さえられ、帯行列では帯が保たれるが、番号の付け方によっては因子が密になり、疎な行列の逆行列も密になりうる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 行列, LU分解, 有向グラフ

疎行列(sparse matrix)とは、成分のほとんどが $0$ である行列のことである。偏微分方程式の離散化、グラフやネットワーク、回路や構造物のモデルから出る行列は、大きさが $10^6$ を超えても 1 行に数個の非零成分しかないことが多い。そうした行列は $0$ を記憶せず、$0$ との演算を飛ばすことで、普通の(密な)行列としては扱えない大きさでも計算できる。
疎行列には成分の個数についての厳密な定義はなく、Saa03 は、成分の多くが $0$ であることとその位置を利用する特別な技法が使えるときに疎と呼ぶ、という趣旨で導入している(第 3 章冒頭、p. 75)。数学的には、非零成分の個数と位置(非零パターン)を主役にして考えるのがよい。この記事では、非零パターンの記録の仕方、非零パターンと有向グラフの対応(thm-sp-walks)、Gauss の消去法で $0$ が非零に変わる fill-in の規則(thm-sp-fill)とその帰結としての帯行列の保存(cor-sp-band)、疎な行列の逆行列が密になる例(prop-sp-inverse)を述べる。

定義

非零パターンと疎行列

体 $\mathbb{K}$($\mathbb{R}$ または $\mathbb{C}$)の成分の $m\times n$ 行列 $A=(a_{ij})$ について、
$$ \mathcal{P}(A):=\{(i,j)\mid a_{ij}\ne0\},\qquad \operatorname{nnz}(A):=\#\mathcal{P}(A) $$
を $A$ の 非零パターン と 非零成分の個数 という。$\operatorname{nnz}(A)$ が $mn$ に比べてずっと小さく、それを計算に利用する行列を 疎行列 といい、そうでない行列を 密行列 という。とくに、大きさ $N$ が増える正方行列の族 $(A_N)$ で、$N$ によらない定数 $c$ があって $\operatorname{nnz}(A_N)\le cN$ となるものは疎行列の族の典型である。

「ずっと小さい」に決まった閾値はない。疎であることは 1 つの行列の性質というより、行列の族と、それを使うアルゴリズムとの組の性質である。

差分法とグラフから出る疎行列
  1. 1 次元の差分行列:$T_N$ を、対角成分が $2$、そのすぐ上と下の成分が $-1$、ほかが $0$ の $N$ 次正方行列とする。区間上の $-u''$ を等間隔の格子で差分近似すると、間隔の 2 乗を除いてこの行列が出る(有限差分法)。$\operatorname{nnz}(T_N)=N+2(N-1)=3N-2$ である。
  2. 2 次元の 5 点差分行列:$n\times n$ の格子点 $N=n^2$ 個を未知数とし、各点の行に、その点(係数 $4$)と上下左右の隣の点(係数 $-1$)を置く。対角が $n^2$ 個、左右の隣の組が $n(n-1)$ 組、上下の隣の組が $n(n-1)$ 組で、各組は 2 つの成分を与えるので、$\operatorname{nnz}=n^2+4n(n-1)=5N-4\sqrt N$ である。密に記憶すれば $N^2$ 個の成分が要る。
  3. グラフ Laplacian:孤立点のない有限単純グラフ $G=(V,E)$ の グラフLaplacian $L=D-A_G$($D$ は次数の対角行列、$A_G$ は 隣接行列)は $\operatorname{nnz}(L)=\lvert V\rvert+2\lvert E\rvert$ を満たす。平面グラフでは $\lvert E\rvert\le3\lvert V\rvert-6$($\lvert V\rvert\ge3$)なので、$\operatorname{nnz}(L)\le7\lvert V\rvert$ である。

記憶の仕方と行列とベクトルの積

非零成分だけを記憶する代表的な形式は次の 3 つである(Saa03 §3.4, pp. 92–93)。以下、添字は 1 から数える。

  • 座標形式(COO):非零成分の値・行番号・列番号を、長さ $\operatorname{nnz}(A)$ の 3 本の配列に任意の順で並べる。
  • 圧縮行形式(CSR, Compressed Sparse Row):値の配列 $\mathrm{AA}$ と列番号の配列 $\mathrm{JA}$ に、非零成分を行の順に並べ、長さ $m+1$ の配列 $\mathrm{IA}$ に各行の始まりの位置を入れる。第 $i$ 行の非零成分は $\mathrm{AA}$ の第 $\mathrm{IA}(i)$ から第 $\mathrm{IA}(i+1)-1$ までの位置にある。
  • 圧縮列形式(CSC):CSR の行と列の役割を入れ替えたもの。$A$ の CSC は $A^{\top}$ の CSR と同じ配列である。
4 次の行列の圧縮行形式

$$ A=\begin{pmatrix}5&0&0&1\\0&3&2&0\\0&0&0&0\\4&0&0&6\end{pmatrix} $$
では $\operatorname{nnz}(A)=6$ で、圧縮行形式は
$$ \mathrm{AA}=(5,1,3,2,4,6),\quad \mathrm{JA}=(1,4,2,3,1,4),\quad \mathrm{IA}=(1,3,5,5,7) $$
である。第 3 行は $\mathrm{IA}(3)=\mathrm{IA}(4)=5$ なので非零成分をもたない。圧縮列形式では、値 $(5,4,3,2,1,6)$、行番号 $(1,4,2,2,1,4)$、列の始まり $(1,3,4,5,7)$ となる。

圧縮行形式での積の手間

$m\times n$ 行列 $A$ が圧縮行形式で与えられているとき、$A$ の記憶には実数 $\operatorname{nnz}(A)$ 個と整数 $\operatorname{nnz}(A)+m+1$ 個が要り、$x\in\mathbb{K}^n$ について $y=Ax$ は
$$ y_i=\sum_{k=\mathrm{IA}(i)}^{\mathrm{IA}(i+1)-1}\mathrm{AA}(k)\,x_{\mathrm{JA}(k)}\qquad(1\le i\le m) $$
で計算でき、乗算はちょうど $\operatorname{nnz}(A)$ 回、加算は $\operatorname{nnz}(A)$ 回以下である。

第 i 行の非零成分だけを足す

記憶の量は配列の長さそのものである。$y_i=\sum_ja_{ij}x_j$ で $a_{ij}=0$ の項は $0$ なので、和は第 $i$ 行の非零成分だけでとればよく、それが上の式である。各非零成分は乗算を 1 回ずつ受けるので乗算は合計 $\operatorname{nnz}(A)$ 回で、第 $i$ 行に $r_i\ge1$ 個の非零成分があれば加算は $r_i-1$ 回なので、合計は $\operatorname{nnz}(A)$ 以下である。$\square$

密な行列では乗算が $mn$ 回要るのに対し、疎行列の族では $\operatorname{nnz}(A_N)\le cN$ なので積の手間は $N$ に比例する(BV04 §C.1.2, p. 663 も、非零成分が $N$ 個の行列とベクトルの積を $2N$ flops と数える)。共役勾配法 や Krylov部分空間法 は係数行列を行列とベクトルの積を通してだけ使うので、1 回の反復の主な手間が $O(\operatorname{nnz}(A))$ になる。大きな疎行列の連立 1 次方程式に反復法が使われる理由の 1 つである(反復法(連立1次方程式))。

非零パターンとグラフ

隣接グラフ

$n$ 次正方行列 $A$ の 隣接グラフ $G(A)$ を、頂点の集合を $\{1,\dots,n\}$ とし、$a_{ij}\ne0$ のとき $i$ から $j$ への辺($i=j$ ならループ)をもつ有向グラフと定める。$G(A)$ の長さ $k$ の 歩道 とは、頂点の列 $i_0,i_1,\dots,i_k$ で、各 $1\le r\le k$ について $i_{r-1}$ から $i_r$ への辺があるものをいう。

$\mathcal{P}(A)$ が対称($a_{ij}\ne0\iff a_{ji}\ne0$)なら、向きを忘れて無向グラフとみてよい(Saa03 §3.2.1, p. 77)。差分行列 $T_N$ の隣接グラフは長さ $N$ の道(とループ)、5 点差分行列の隣接グラフは格子そのものである。

行列の冪と歩道

$A$ を $n$ 次正方行列、$k\ge1$ とする。

  1. $(A^k)_{ij}\ne0$ なら、$G(A)$ に $i$ から $j$ への長さ $k$ の歩道がある。
  2. $A$ の成分がすべて $0$ 以上の実数なら、1 の逆も成り立つ。
  3. $\sigma$ を $\{1,\dots,n\}$ の置換、$P$ を $(PAP^{\top})_{ij}=a_{\sigma(i)\sigma(j)}$ となる置換行列とすると、$i\mapsto\sigma(i)$ は $G(PAP^{\top})$ から $G(A)$ へのグラフの同型である。
冪の成分を歩道ごとの積の和に展開する

行列の積の定義を $k$ 回使うと
$$ (A^k)_{ij}=\sum_{i_1,\dots,i_{k-1}}a_{i\,i_1}a_{i_1i_2}\cdots a_{i_{k-1}j} $$
である($i_0=i$、$i_k=j$ とおく)。右辺の項が $0$ でないことは、すべての $r$ で $a_{i_{r-1}i_r}\ne0$、すなわち $i_0,\dots,i_k$ が $G(A)$ の歩道であることと同値である。
1:和が $0$ でなければ、$0$ でない項があり、それが歩道を与える。
2:成分が $0$ 以上なら各項は $0$ 以上で、歩道があればその項は正なので、和は正である。
3:$(PAP^{\top})_{ij}\ne0\iff a_{\sigma(i)\sigma(j)}\ne0$ なので、$G(PAP^{\top})$ に $i$ から $j$ への辺があることと、$G(A)$ に $\sigma(i)$ から $\sigma(j)$ への辺があることは同値である。$\square$

Saa03 §3.2.1(p. 78)は、$A^k$ のグラフを「長さ $k$ の道がある」関係として読む見方を述べている。上の 1・2 のとおり、成分に負の数や複素数があると項が打ち消し合いうるので、一般に成り立つのは 1 の向きだけである(ex-sp-claims-check の 1 行目)。3 は、行と列を同じ置換で並べ替えることがグラフの頂点の番号の付け替えにすぎないことを述べている(Saa03 §3.3, p. 82)。次の節で見るとおり、番号の付け方は消去法の手間を大きく左右する。成分が $0$ 以上の行列の隣接グラフが強連結であることは、Perron–Frobeniusの定理 の既約性にあたる。

消去法と fill-in

疎行列 $A$ に LU分解 を当てると、もとは $0$ だった位置に非零成分が現れることがある。これを fill-in という(Saa03 §3.6, p. 96)。fill-in が多いと、$L,U$ の記憶と計算の手間は密行列と変わらなくなる。どこに fill-in が起こりうるかは、成分の値によらず非零パターンだけで上から押さえられる。
$n$ 次正方行列 $A$ を、$a:=a_{11}\ne0$ として
$$ A=\begin{pmatrix}a&u^{\top}\\v&B\end{pmatrix},\qquad S:=B-\frac1a\,vu^{\top} $$
と分ける($u,v\in\mathbb{K}^{n-1}$)。$S$ は Gauss の消去法で第 1 列を掃き出した後に残る右下の $n-1$ 次の行列で、$A$ の $a$ に関する Schur補行列 である。以下、$S$ と $B$ の行と列には $A$ での番号 $2,\dots,n$ をそのまま使う。

1 段の消去での fill-in

$i,j\ge2$ について次が成り立つ。

  1. $s_{ij}\ne0$ なら、$b_{ij}\ne0$ であるか、$v_i\ne0$ かつ $u_j\ne0$ である。
  2. $b_{ij}=0$、$v_i\ne0$、$u_j\ne0$ なら $s_{ij}\ne0$ である(fill-in が起こる)。
成分の式を見る

$s_{ij}=b_{ij}-v_iu_j/a$ である。1 は、$b_{ij}=0$ かつ $v_iu_j=0$ なら $s_{ij}=0$ であることの対偶である。2 では $s_{ij}=-v_iu_j/a\ne0$ である。$\square$

$b_{ij}\ne0$ かつ $v_iu_j\ne0$ のときだけ、打ち消し合いで $s_{ij}=0$ となりうる。グラフで言えば、頂点 $1$ を消去すると、頂点 $1$ へ辺をもつ頂点 $i$ から頂点 $1$ が辺をもつ頂点 $j$ への辺が新しく生じうる。$\mathcal{P}(A)$ が対称なら、頂点 $1$ の隣の頂点どうしがすべて辺で結ばれる。これを繰り返して得る次の集合を、記号的な消去で求める非零パターンという(Saa03 §3.6 の symbolic factorization)。

記号的な消去

$\{1,\dots,n\}^2$ の部分集合 $\mathcal{F}_1:=\mathcal{P}(A)$ から始めて、$k=1,\dots,n-1$ について
$$ \mathcal{F}_{k+1}:=\mathcal{F}_k\cup\{(i,j)\mid i>k,\ j>k,\ (i,k)\in\mathcal{F}_k,\ (k,j)\in\mathcal{F}_k\} $$
と定め、$\mathcal{F}(A):=\mathcal{F}_n$ を $A$ の 埋められたパターン という。$\mathcal{F}(A)$ は $\mathcal{P}(A)$ だけで決まり、$\mathcal{P}(A)\subset\mathcal{P}(A')$ なら $\mathcal{F}(A)\subset\mathcal{F}(A')$ である(各段の定義が包含を保つ)。

LU 分解の因子の非零パターン

$A$ を正則な $n$ 次正方行列とし、$A=LU$ で、$L$ は対角成分が $1$ の下三角行列、$U$ は上三角行列とする(行の入れ替えのない LU 分解)。このとき、$i>j$ で $l_{ij}\ne0$ なら $(i,j)\in\mathcal{F}(A)$ であり、$i\le j$ で $u_{ij}\ne0$ なら $(i,j)\in\mathcal{F}(A)$ である。

第 1 段を剥がして Schur 補行列に帰納する

$n$ についての帰納法による。$n=1$ では $u_{11}=a_{11}$ で、$u_{11}\ne0$ なら $(1,1)\in\mathcal{P}(A)$ である。$n\ge2$ とし、$L,U$ を $A$ と同じ形に
$$ L=\begin{pmatrix}1&0\\\ell&L'\end{pmatrix},\qquad U=\begin{pmatrix}a'&w^{\top}\\0&U'\end{pmatrix} $$
と分ける。$LU$ を計算して $A$ と比べると $a'=a$、$w=u$、$a\ell=v$、$\ell u^{\top}+L'U'=B$ である。$0\ne\det A=\det U=a\det U'$ なので $a\ne0$、$\det U'\ne0$ である。よって $\ell=v/a$ で、$L'U'=B-vu^{\top}/a=S$ であり、$\det S=\det U'\ne0$ から $S$ も正則である。$L$ の第 1 列の非零成分 $l_{i1}=v_i/a$ の位置 $(i,1)$ と、$U$ の第 1 行の非零成分の位置 $(1,j)$ は $\mathcal{P}(A)=\mathcal{F}_1$ に入る。$L'$ は対角成分が $1$ の下三角行列、$U'$ は上三角行列なので、帰納法の仮定を $S=L'U'$ に使うと、$L',U'$ の非零成分の位置は $\mathcal{F}(S)$($S$ の記号的な消去を $k=2,\dots,n-1$ で行ったもの)に入る。prop-sp-one-step の 1 により、$\mathcal{P}(S)$ は
$$ \{(i,j)\in\mathcal{F}_2\mid i,j\ge2\}=\{(i,j)\mid i,j\ge2,\ (i,j)\in\mathcal{P}(A)\ \text{または}\ (i,1),(1,j)\in\mathcal{P}(A)\} $$
に含まれる。この集合から $k=2,\dots,n-1$ の段を行ったものは $\mathcal{F}(A)$ の $i,j\ge2$ の部分なので、包含の保存により $\mathcal{F}(S)\subset\mathcal{F}(A)$ である。$\square$

正則性の仮定は $L$ の第 1 列を $A$ から決めるために使った。$A$ が正則でないと、たとえば第 1 列が $0$ の行列では $L$ の第 1 列を任意にとれ、$L$ の非零成分は $\mathcal{F}(A)$ に入るとは限らない。$\mathcal{F}(A)$ は成分の値を使わずに求まるので、実際の疎な直接法では、まず $\mathcal{F}(A)$ を求めて $L,U$ の記憶場所を用意し、その後で数値を計算する(BV04 §C.3.2, p. 671 は正定値対称行列の Cholesky 分解について、この 2 段を記号的な分解と数値的な分解と呼んでいる)。

帯行列の LU 分解

$p,q\ge0$ とし、正則な $n$ 次正方行列 $A$ が、$i-j>p$ または $j-i>q$ なら $a_{ij}=0$ を満たす(下の帯幅 $p$、上の帯幅 $q$ の帯行列)とする。$A=LU$ を thm-sp-fill の LU 分解とすると、$L$ は $i-j>p$ で $l_{ij}=0$、$U$ は $j-i>q$ で $u_{ij}=0$ を満たす。また、分解の計算の乗除算は $n(pq+p)$ 回以下である。

新しい位置は帯の中にしか生じない

帯 $\mathcal{B}:=\{(i,j)\mid -q\le j-i,\ i-j\le p\}$ について、$\mathcal{F}_k\subset\mathcal{B}$ を $k$ についての帰納法で示す。$\mathcal{F}_1=\mathcal{P}(A)\subset\mathcal{B}$ である。$\mathcal{F}_k\subset\mathcal{B}$ とし、$i,j>k$、$(i,k),(k,j)\in\mathcal{F}_k$ とすると、$i-j< i-k\le p$、$j-i< j-k\le q$ なので $(i,j)\in\mathcal{B}$ である。よって $\mathcal{F}(A)\subset\mathcal{B}$ で、thm-sp-fill から主張が従う。
手間:第 $k$ 段で更新するのは、$v$ の非零になりうる成分 $i=k+1,\dots,\min(k+p,n)$ と、$u$ の非零になりうる成分 $j=k+1,\dots,\min(k+q,n)$ の組だけである。割り算 $v_i/a$ が $p$ 回以下、更新 $s_{ij}=b_{ij}-(v_i/a)u_j$ の乗算が $pq$ 回以下なので、$n-1$ 段の合計は $n(pq+p)$ 回以下である。$\square$

密な LU 分解の乗除算がおよそ $n^3/3$ 回なのに対し、帯幅が一定なら手間は $n$ に比例する。三重対角行列($p=q=1$)では $2n$ 回以下である。部分ピボット選択で行を入れ替えると、$U$ の上の帯幅は $q$ を超えうる(ex-sp-claims-check の 4 行目。BV04 §C.3.1, p. 669 は、帯幅 $k$ の帯行列の部分ピボット選択つきの LU 分解で $U$ の帯幅が $2k$ 以下になると述べている)。

矢印行列と番号の付け方

$n\ge3$ とし、$A$ を、第 1 行・第 1 列・対角に非零成分をもち、ほかは $0$ の正定値対称行列とする(矢印行列)。正定値対称行列とその行と列を同じ置換で並べ替えた行列は、行の入れ替えなしの LU 分解をもつ(Cholesky分解)。$G(A)$ は頂点 $1$ を中心とする星形のグラフ(とループ)である。

  1. 頂点 $1$ を最初に消去すると、$\mathcal{F}_2$ はすべての $(i,j)$($i,j\ge2$)を含み、$\mathcal{F}(A)$ は $\{1,\dots,n\}^2$ 全体になる。たとえば $n=4$、対角成分が $4$、第 1 行と第 1 列の非対角成分が $1$ の行列では $S=4I_3-\frac14J$($J$ はすべての成分が $1$ の行列)で、$S$ の非対角成分はすべて $-\frac14\ne0$ であり、prop-sp-one-step の 2 のとおり fill-in が実際に起こり、この例では $L$ の下三角部分と $U$ の上三角部分の成分はすべて $0$ でない。
  2. 置換で頂点 $1$ を最後に回した $PAP^{\top}$(thm-sp-walks の 3)では、頂点 $k< n$ の隣は中心だけなので、各段で新しく加わる組は $(n,n)$ だけで、これは初めから $\mathcal{P}$ に入っている。よって $\mathcal{F}(PAP^{\top})=\mathcal{P}(PAP^{\top})$ で、fill-in は起こらない。
    同じ現象は Saa03 Example 3.3(p. 82)に述べられており、正定値対称行列の Cholesky 分解での数値例は Cholesky分解 の例「矢印行列と並べ替え」(BV04 Example C.1, pp. 670–671 の形)にある。番号の付け方で fill-in を減らす方法(最小次数順序・入れ子分割)は Saa03 §3.6.1–3.6.2(p. 97)にあるが、最も fill-in の少ない順序を求めることは一般に難しい。

疎な行列の逆行列

$Ax=b$ を解くのに $A^{-1}$ を作るのは、疎行列ではとくに避けるべきである。逆行列は一般に密になるからである。

差分行列の逆行列

ex-sp-examples の 1 の $T_N$ について、
$$ (T_N^{-1})_{ij}=\frac{\min(i,j)\,\bigl(N+1-\max(i,j)\bigr)}{N+1}\qquad(1\le i,j\le N) $$
である。とくに $T_N^{-1}$ の成分はすべて正で、$\operatorname{nnz}(T_N)=3N-2$ に対し $\operatorname{nnz}(T_N^{-1})=N^2$ である。

各列が折れ線であることを使う

右辺の行列を $G$ とし、$T_NG=I$ を示す。$j$ を固定し、$g_i:=G_{ij}$ を $i=0,1,\dots,N+1$ で同じ式で定めると $g_0=g_{N+1}=0$ であり、$i\le j$ では $g_i=i(N+1-j)/(N+1)$、$i\ge j$ では $g_i=j(N+1-i)/(N+1)$ と、$i$ の 1 次式である($i=j$ で両方の式は一致する)。$T_N$ の第 $i$ 行と $G$ の第 $j$ 列の積は $-g_{i-1}+2g_i-g_{i+1}$ である($i=1,N$ でも $g_0=g_{N+1}=0$ によりこの式でよい)。$i\ne j$ なら $i-1,i,i+1$ は同じ 1 次式の側にあるので、この 2 階差分は $0$ である。$i=j$ なら
$$ -g_{j-1}+2g_j-g_{j+1}=\frac{-(j-1)(N+1-j)+2j(N+1-j)-j(N-j)}{N+1}=\frac{(j+1)(N+1-j)-j(N-j)}{N+1}=1 $$
である(分子は $(N+1)(j+1)-j(j+1)-jN+j^2=N+1$)。よって $T_NG=I$ で、$G=T_N^{-1}$ である。$1\le i,j\le N$ では $\min(i,j)\ge1$、$N+1-\max(i,j)\ge1$ なので成分は正である。$\square$

一方、$T_N$ の LU 分解は cor-sp-band により二重対角の因子をもち、前進代入と後退代入はそれぞれ $O(N)$ の手間で済む。疎行列の連立 1 次方程式は、逆行列ではなく、疎な因子への分解か反復法で解く。

成り立ちそうで成り立たないこと

疎であることは、積・冪・分解・逆行列で保たれるとは限らない。

主張反例正しい形
$(A^k)_{ij}\ne0$ と、長さ $k$ の歩道があることは同値$A=\begin{pmatrix}1&1\\1&-1\end{pmatrix}$、$k=2$歩道があることは必要条件。成分が $0$ 以上なら同値(thm-sp-walks)
疎行列の積は疎で、$\operatorname{nnz}(AB)\le\operatorname{nnz}(A)+\operatorname{nnz}(B)$$A$ は第 1 列だけ、$B$ は第 1 行だけがすべて $1$ の $N$ 次行列$\mathcal{P}(AB)\subset\{(i,j)\mid\text{ある }k\text{ で }(i,k)\in\mathcal{P}(A),\ (k,j)\in\mathcal{P}(B)\}$
疎行列の LU 分解の因子は疎ex-sp-arrow の 1因子の非零パターンは $\mathcal{F}(A)$ に入る(thm-sp-fill)。番号の付け方で大きく変わる
部分ピボット選択つきでも、$U$ の上の帯幅は $A$ の $q$ のまま$A=\begin{pmatrix}1&1&0\\2&1&1\\0&1&1\end{pmatrix}$($p=q=1$)帯幅の保存は行の入れ替えのない場合(cor-sp-band)
疎な正則行列の逆行列は疎$T_N$(prop-sp-inverse)逆行列を作らず、分解か反復法で解く
表の確かめ
確かめを開く

1 行目:$A^2=2I$ なので $(A^2)_{12}=0$ だが、$a_{11}\ne0$、$a_{12}\ne0$ なので $1,1,2$ は長さ $2$ の歩道である。$(A^2)_{12}=a_{11}a_{12}+a_{12}a_{22}=1-1$ で、2 つの歩道の項が打ち消し合っている。

2 行目:$\operatorname{nnz}(A)=\operatorname{nnz}(B)=N$ だが、$(AB)_{ij}=a_{i1}b_{1j}=1$ なので $\operatorname{nnz}(AB)=N^2$ である。$N\ge3$ で $N^2>2N$ である。

3 行目:ex-sp-arrow の $n=4$ の行列は $\operatorname{nnz}=10$ で、$L$ と $U$ の非零成分は合わせて $16$ 個($L$ の狭義下三角 $6$ と $U$ の上三角 $10$)である。

4 行目:第 1 列で絶対値の最大は第 2 行の $2$ なので第 1 行と第 2 行を入れ替え、$U$ の第 1 行は $(2,1,1)$ となる。$u_{13}=1\ne0$ で $j-i=2>q=1$ である。

5 行目:prop-sp-inverse のとおり $\operatorname{nnz}(T_N^{-1})=N^2$ で、$N\ge2$ なら $N^2>3N-2$ である。

関連項目

参考文献

[1]
Yousef Saad, Iterative Methods for Sparse Linear Systems, SIAM, 2003, 第 3 章冒頭(p. 75)、§3.2.1(隣接グラフ、pp. 77–78)、§3.3(置換と隣接グラフ・Example 3.3、p. 82)、§3.4(座標形式・CSR・CSC、pp. 92–93)、§3.6(fill-in と記号的な分解、p. 96)、§3.6.1–3.6.2(p. 97)
[2]
Stephen Boyd, Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004, §C.1.2(疎行列とベクトルの積、p. 663)、§C.3.1(帯行列・疎行列の LU 分解、p. 669)、§C.3.2(Example C.1、記号的な分解、pp. 670–671)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する