昨日の続きだが、http://www.netlib.org/lapack/lawnspdf/lawn165.pdf は非常にためになった。中身だけでなく論文の構成や数値実験についても参考になる。普通の論文だとこれだけ枚数が多いと嫌われるので、中身を削れとか言われるかもしれない。Working note だと何も制約が無いので好きなように書けるのだろう。
ところで SDPA に関しては精度の問題に関してはまず倍精度(double)の限界を疑ったので、以前のブログでも紹介したように東工大の方で Java で再インプリメントしてもらって多倍長計算に対応させて数値実験を行った(ISMP2006 で発表予定)。問題や条件によってはこれでもかなり精度が向上するが、多倍長計算だけで全ての精度を解決するのは無理なようだ。
次に疑われるのは線形方程式の誤差の影響である。内点法の中では線形方程式の行列は対称半正定値になるので普段はコレスキー分解しているが、この精度強化に Iterative refinement 法を使おうというのが狙いである。基本的なアルゴリズムは画像として貼っておいた。まずは普通に Ax = b を解いて、残差(residual) r を計算する。次に A dx = r となるような dx を求めて x = x - dx として繰り返す反復法である。基本的な方法は簡単だが、信頼性の高い error bound の計算は難しい。この辺りが論文でも苦労しているところだが LAPACK の関数として提供されることになっている。
