数値オプティマイザの中間ステップとしてN線形方程式の系を解く必要があります。それを正確に行うためのAFAIKの合理的に簡単なアルゴリズムはO（N^3）です（ただし、O（N^2.8）のような膨大な定数で数学論文の中で複雑に扱えるものがありました）。ある場合には、Nは、数千という巨大なものである。線形方程式に対する高速、近似解はありますか？
O（N^3）未満の線形方程式のシステムに対してまともな近似解を得る良い方法はありますか？
編集：
ここでは、それがまったく役に立った場合の詳細をいくつか示します。
私のマトリックスは、対称で、スパースではありません。
ニュートンラフソンの二次微分行列です。私は2000次元の空間で何かを最適化しようとしています。
はい、係数から得られる行列が疎であれば、そうです。 O（N）で動作する三角対角行列の場合、「正しいレイアウト」のメソッドがあります（ブルガリア語では正確な翻訳についてはわかりません）。まだO（N^3）のアルゴリズムがありますが、行列が必要な不変量（疎、対角、三角など）に準拠していると信じられない結果が得られます。
あなたのインバリアントに基づいて特定の方法に固執している場合は、さらに高速化する唯一の方法はマルチスレッドにすることです。
お試しthis検索。
対称行列の場合GMRESなどヤコビ、ガウス・ザイデル、CG、などの反復法
がありますが、conjugate gradient methodは、実装が簡単で、他のほとんどの反復法を負かす事になります（例えば、ガウス・ザイデル、SOR ）。メインループは、行列 - ベクトル乗算とその他のいくつかのベクトル演算で構成されています。
これが機能したら、preconditioningを使用してコンバージェンスをさらに向上させることができます。
LAPACKのような実績のある実装を使用しない理由：http://en.wikipedia.org/wiki/LAPACK – Andrey
はい、多くあります。どちらが適切かは、特定の係数行列に依存します。それがどのようなものかを教えていただければ、特定のアルゴリズムを提案することができます。 – Thomas
[wikipedia]（http://en.wikipedia.org/wiki/Iterative_method）にはいくつかの説明がありますが、私はそれらを一切使っていませんでした。 –