QR分解について QR分解のアルゴリズムとしては少なくともギブンス回転を用いる方法ハウスホルダー

締切済

質問者：物理太郎
質問日時：2018/03/06 17:07
回答数：1件

QR分解について

QR分解のアルゴリズムとしては少なくとも
ギブンス回転を用いる方法
ハウスホルダー変換を用いる方法
グラムシュミットの直交化を用いる方法
の三通りがあると思うのですが、これらの方法はどのように使い分ければよいですか？

特に、計算量、密疎行列のいずれに向いているか、大規模エルミート疎行列にはどれを用いるべきかが知りたいです。

よろしくお願いします。

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (1件)

最新から表示
回答順に表示

No.1

回答者： stomachman
回答日時：2018/03/10 11:04

旨い手があるのかどうか知りませんけれども、回答が付かんようなので…

　スパースな行列Xを分解した結果をできるだけスパースにしたい、という話でしたら、XA = QR (Q' Q = I, Rは上三角行列、Aは列の入れ替え操作）とやるんですから、（何法を使おうとも）自由度はAの選び方にしかなく、これによってQやRがどのぐらいスパースになるかが決まる訳で、しかしXがよっぽど直交に近い場合（X' Xがスパースである場合）以外は、Aがどうあれ、結果はスパースとはとても言えないものになるでしょう。
　で、結果がスパースでないのなら、計算量を減らすために、要するに0の成分を飛ばす（=0でない成分を選ぶ処理）が素早くできるようにXを圧縮して表現しておくわけですが、結果の方が圧縮できないんだから計算の途中でぐずぐず(スパースでない状態)になってしまうのは必然でしょう。
　たとえばグラムシュミットの直交化だと、最初の単位ベクトルpを選んだ直後に他のベクトルqからpに平行な成分を引き算して中間結果を出すから、この時点で今まで0だった成分が非零になる。（pとqの第k成分がどちらも0、という場合のqの第k成分しか0のままで居られない。）これは下手な手ですね。ぐずぐず化をなるべく遅らせるのが肝要だろうと考えるなら、Qの成分の値の計算を、中間結果を保存するのではなくて、その値が完全に決まる段階まで計算を始めないようにすりゃ良い（これは簡単）わけです。