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.