A Toolkit for Non-linear Algebra

本项目负责实现一个用C语言编写的代数几何工具包，它可以求解复数上的方程组和实数上的不等式。这样的工具包有很多应用，因为科学和工程的许多分支的问题可以用多项式方程和不等式系统来表述。通过几个著名的定理，特别是塔斯基的实数定理，可以在原则上解决这类问题。但最坏情况的边界是变量数量的指数或双指数，而且没有一个实际的系统能够处理超过几个特殊情况。另一方面，多项式系统可能具有一种特殊的结构，一种稀疏性，这意味着复杂度（用代数度来衡量）远低于最坏的情况。事实上，大多数重要的应用程序都属于这种类型。最近，已经开发出了可以利用这种结构的算法。这种实现是此时开发工具包的强烈动机。此外，符号确定和符号数值计算的算法也有了改进，人们认为这些方法现在已经足够先进，可以保证实现。

This project undertakes the implementation of an algebraic-geometric toolkit, written in C, which can solve systems of equations over the complex numbers, and inequalities over the reals. There are many applications of such a toolkit, since problems from many branches of science and engineering can be formulated using systems of polynomial equations and inequalities. By several well-known theorems, in particular, Tarski's theorem for the reals, it is possible to solve such problems in principle. But the worst case bounds are exponential or doubly-exponential in the number of variables, and no practical system has appeared that can deal with more than a few special cases. On the other hand, systems of polynomials may have a special structure, a kind of sparseness, that implies a complexity (measured by the algebraic degree) much lower than the worst case. Indeed, most of the important applications are of this type. Very recently, algorithms have been developed that can exploit this structure. This realization is a strong motivation for developing the toolkit at this time. In addition, there have been improvements in algorithms for sign determination and symbolic-numeric computation, and it is felt that these methods are now advanced enough to warrant implementation.