2.4.1 疎性が保存されるか

$A$ が $A=LU$ と LU 分解可能なとき、 $A$ の疎性は $L$ と $U$ に「遺伝する」、 つまり $A$ が疎行列ならば、 $L$ と $U$ も疎行列であることは比較的容易に分かる (より具体的には「バンド幅」 -- まだ説明していない概念⁹だが -- は増えない)。

これに対して、$A$ が疎行列であっても、 $A^{-1}$ が疎行列になるとは限らない (比較的有名であるので例は後回しにする -- なお、 次の例 2.2 もその例だと言えないこともない)。 $L^{-1}$ も疎行列になるとは限らないことを例で示しておこう。

この例の問題で $L$ を記憶しておいて、 (4) で解を求めるやり方と、 $L^{-1}$ を計算して $b=(b_i)$ にかけて解を求めるやり方を比べてみるのは 有益である。 前者は、$n$ に比例する計算量ですむ (疎性を有効に活かせた) が、 後者は、行列 $L^{-1}$ とベクトル $b$ の掛け算だけで、 $n^2$ に比例する計算量となってしまう (疎性を活かせなかった)。