ABSメソッド

ABS メソッド (頭字語には Jozsef Abaffy、 Charles G. Broyden、Emilio Spedicatoのイニシャルが含まれています) は、次のアプリケーション用の 大規模なアルゴリズムを生成するために 1981 年以来開発されています。

• 一般線形代数系の解（決定系または劣決定系）
• 完全なランクまたは不十分なランク。
• 線形ディオファントス方程式の解、すなわち係数行列と右辺が整数値で整数解が求められる方程式の解。これはヒルベルトの第 10 問題の特殊だが重要なケースであり、実際に解ける唯一の問題である。
• 非線形代数方程式の解;
• 連続的な制約なしまたは制約付き最適化のソリューション。

2007 年の初めの時点で、ABS の文献は 400 を超える論文とレポート、および 2 つのモノグラフ (1 つは Abaffy と Spedicato が 1989 年に出版したもの、もう 1 つは Xia と Zhang が 1998 年に中国語で出版したもの) で構成されていました。さらに、中国で 3 つの会議が開催されました。

ABS法に関する研究は、イタリアのベルガモ大学のスペディカートが調整する国際共同研究の成果です。ハンガリー、イギリス、中国、イランなどの国々から40人以上の数学者が参加しています。

このような手法の中心的な要素は、ハンガリーの数学者イェネー・エゲルヴァーリに由来する特殊な行列変換の利用です。彼はいくつかの論文でその主要な性質を研究しましたが、それらは注目されませんでした。n変数のm個の線形方程式系（ただし ）を解くという基本問題に対して、ABS法では次のような単純な幾何学的概念が用いられます。 ${\displaystyle \scriptstyle m\,\leq \,n}$

1. 解の任意の初期推定値が与えられた場合、 最初の方程式の次元n − 1 の線形多様体を定義する無限解の 1 つを見つけます。
2. 最初の方程式の解でもある 2 番目の方程式の解を見つけます。つまり、別々に検討した最初の 2 つの方程式の解の線形多様体の交点にある解を見つけます。
3. 上記のアプローチをm'ステップごとに繰り返すことで、最後の方程式の解が得られます。この解は前の方程式の解でもあるため、システム全体の解となります。さらに、冗長な方程式や互換性のない方程式を検出することも可能です。

これまでに得られた主な結果は次のとおりです。

• 線形、非線形代数方程式および線形制約非線形最適化（ LP問題を特別なケースとして含む）のアルゴリズムの統一。
• ガウス法は、必要なメモリを削減し、ピボットの必要性を排除することで改善されました。
• new methods for nonlinear systems with convergence properties better than for Newton method;
• derivation of a general algorithm for Hilbert tenth problem, linear case, with the extension of a classic Euler theorem from one equation to a system;
• solvers have been obtained that are more stable than classical ones, especially for the problem arising in primal-dual interior point method;
• ABS methods are usually faster on vector or parallel machines;
• ABS methods provide a simpler approach for teaching for a variety of classes of problems, since particular methods are obtained just by specific parameter choices.

Knowledge of ABS methods is still quite limited among mathematicians, but they have great potential for improving the methods currently in use.

Bibliography

• Jozsef Abaffy, Emilio Spedicato (1989): ABS Projection Algorithms: Mathematical Techniques for Linear and Nonlinear Algebraic Equations, Ellis Horwood, Chichester.   The first monograph on the subject
• Jozsef Abaffy, Charles G. Broyden, Emilio Spedicato (1984): A class of direct methods for linear equations, Numerische Mathematik 45, 361–376. Paper introducing ABS methods for continuous linear systems.
• H. Esmaeili, N. Mahdavi-Amiri, Emilio Spedicato: A class of ABS algorithms for Diophantine linear systems, Numerische Mathematik 90, 101–115. Paper introducing ABS methods for integer linear systems.