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

QR分解について

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

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

よろしくお願いします。

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の成分の値の計算を、中間結果を保存するのではなくて、その値が完全に決まる段階まで計算を始めないようにすりゃ良い（これは簡単）わけです。