pivotingについて(1)

今回は真面目（？）な数学（数値計算）の話。
興味ない人はスルーしてね。。。
（呪文のような言葉が並びます）

行列のLU分解に関して、数値計算の分野ではpivotingというかなり有効なテクニックがある。
（精度が抜群に向上します）よく知られているのは、

• partial pivoting
  行列のfirst column (row)の中で絶対値の一番大きな要素を軸とする分解法
  
• complete pivoting
  行列の要素の中で絶対値の一番大きな要素を軸とする分解法

であり、行と列に意味があったりするので通常はpartial pivotingが利用されます（教科書もこちらだけよくかかれます）。上の２つの計算精度については、Wilkinsonなどが過去にやっているようです。

結果だけ見ると、partial pivotingがcomplete pivotingに比べると大分ダメみたいに見えますが、本人も結果の見積もりはよくなく、２つともそれほど変わらないよ（数値実験から）とコメント。
結局のところ、２つの方法の差の見積もり（差がない？）というのはopen problemみたいで、使うユーザとしては、partial pivotingも安定という実験観測を信じようということらしいです。

文句を言う人もいないし、私もこれはOKと思っております。
（数値計算の立場から）


しかし、数式処理の算法⇔数値計算の算法という書き換え操作・対応を考えてつつ、算法の安定化を考えようというかなりマニアックな研究スタイルを好む私からすると、

1. 要素をすべてみるという操作は数式処理の場合、係数リストをほとんど見る操作であり、無駄な操作（グレブナー基底の計算なんかは、頭稿しかみない）
   ―――
   数式処理屋さんがpartialでも十分に感じさせる一つの言いくるめ方かなと。
   
2. すべての要素を見ると数値計算と変わらなくなるので、数式処理の良さが失われる
   （私の博士論文でコメントしてたはず）
   
3. わざわざMaxをとる必要はない。
   （この辺も、博士論文でコメント済み）

とpartial pivotingでもやりすぎかなぁと思うところ（1, 2）。
3に対応する概念はないかなぁと調べてみると、

threshold pivoting

というものがあるらしい（しきい値でpivoting）。

あまり見覚えがないと思っていたら、やはりWilkinsonあたりの時代に一度研究されたみたい。
数値計算では、partial pivotingが有効で算法効率も落とさないので、あまり陽の目を見なかったのかも（要素をすべてみる時点でthreshold pivotingは意味なし）。 最近では、大きいサイズの行列を扱うため、交換操作を減らしたいということでthreshold pivotingを使うようです。

よくも悪くも解釈すると、

•  ある程度、（いろいろなことを）サボることが可能

と数式処理の解析向きのpivotingのようです。
先週はpivotingの論文ばかり読んでたので、とりあえずメモを書いてみました。
日本語の解説もあまりないし、ドキュメントを残すことは有効かなぁと思っていますが、その前にまだ情報がほしいので、とりあえずコメントくだされば嬉しいです。