Computational tropical geometry and its applications

热带几何是一个年轻的数学领域，它研究由多项式方程产生的组合对象。这些所谓的热带变种自然地出现在许多数学及其他领域，如生物学中的系统发育学、物理学中的天体力学和经济学中的拍卖理论。无论它们出现在哪里，热带的变种常常允许新的计算方法来解决现有的问题。在英国，自金融危机以来，英国央行（Bank of England）一直在使用热带几何来为英国金融体系配置资金。在法国，热带几何被用于优化移动网络的负载平衡和紧急呼叫中心的性能分析。该研究项目旨在将热带几何作为一种强大而通用的工具，用于应用科学和工业中的计算问题，而不是优化。为此，我们追求具体的应用以及计算方法的改进。最终的交付成果是一个用于热带代数几何的全面的开源软件系统，强调其广泛的应用范围。我们专注于三个主要问题，选择这些问题是为了最大限度地发挥它们所包含的影响和技术范围。第一个问题围绕着多项式方程组展开，它在应用科学中无处不在。它们描述了化学反应网络的稳定状态，机械臂的运动范围，或者生化系统中配体的结合行为。二十多年来，解决这类系统的技术状态一直是同伦延拓，它通过仔细地将一个容易启动的系统变形为目标系统，同时跟踪沿途的所有解来工作。我们寻求改进现有的能力，特别是在上述应用中出现的多项式系统的类型。虽然已经研究了将热带几何应用于同伦延拓的想法，但由于效率问题，所有过去的方法都失败了。然而，在过去的几年里，热带几何的算法取得了重大突破，我们将利用并建立在此基础上。第二个问题涉及到p进数，它是数论中不可缺少的一类域。这不仅使它们对热带几何在数论中的应用很重要，而且还需要大量的数论工具。因此，对p-adics数的热带几何的良好把握对于理论和实践都是必要的。话虽如此，在计算上，p进数上的热带几何由于它们带来的独特算法挑战而被忽略了。我们试图纠正这种情况，并探索热带几何的计算方面，特别是在p进数上，由计算机代数的最新趋势促进。第三个问题涉及Gröbner基，它在计算代数几何和密码学等邻近领域有着悠久的历史。此外，在过去的十年里，代数几何技术在数学以外的领域出现了爆炸式的发展。因此，Gröbner基作为研究多项式系统的工具和本身感兴趣的对象（例如，代数统计中的马尔可夫基）获得了吸引力。然而，Gröbner碱基是出了名的难以计算，这严重限制了它们在实际应用中的使用。我们将调查所谓的饱和Gröbner碱。一般来说，多项式未知数表示系数域的任意元素，并且Gröbner基计算中的所有操作都尊重这种模糊性。在实践中，人们通常只对特解感兴趣，例如严格正实解。饱和Gröbner基算法是一种符号算法，它能够利用在许多应用中丰富的数值信息并利用它来加快其性能。

Tropical geometry is a young area of mathematics which studies combinatorial objects arising from polynomial equations. These so-called tropical varieties arise naturally in many areas of mathematics and beyond, such as phylogenetics in biology, celestial mechanics in physics, and auction theory in economics. Wherever they arise, tropical varieties often allow new computational approaches to existing problems. In the UK, the Bank of England has been using tropical geometry since the financial crises to allocate money to the UK financial system. In France, tropical geometry is used for optimisation of load balancing of mobile networks, and performance analysis of emergency call centres.This research projects aims at establishing tropical geometry as a powerful and versatile tool for computational questions in applied sciences and industry beyond optimisation. To this end, we pursue concrete applications as well as improvements of computational methods. The final deliverable is a comprehensive open source software system for tropical algebraic geometry with strong emphasis on its wide spectrum of applications. We focus on three main problems, which were chosen to maximise the impact and the range of techniques that they encompass.The first problem revolves around systems of polynomial equations, which are ubiquitous in applied science. They describe the steady states of chemical reaction networks, the range of movement of a robot arm, or the binding behaviour of ligands in a biochemical system. For over two decades, the state of the art for solving such systems has been homotopy continuation, which works by carefully deforming an easy start system to the target system while tracing all solutions along the way.We seek to improve the existing capabilities, in particular for the type of polynomial systems which arise in the aforementioned applications. While ideas to apply tropical geometry to homotopy continuation have already been studied, all past approaches have failed due to questions of efficiency. However, the last couple of years have seen significant algorithmic breakthroughs in tropical geometry, which we will exploit and build upon.The second problem involves p-adic numbers, which are an indispensable class of fields for number theory. This not only makes them important for the applications of tropical geometry in number theory, but also entails a vast array of number theoretic tools available exclusively over them. Hence a good grasp on tropical geometry over p-adics numbers is an imperative for both theory and practice.That being said, computationally, tropical geometry over p-adic numbers has been neglected due to the unique algorithmic challenges they pose. We seek to remedy this situation and explore computational aspects of tropical geometry specifically over p-adic numbers, facilitated by recent trends in computer algebra.The third problem involves Gröbner bases, which have long history in computational algebraic geometry and adjacent fields such as cryptography. Furthermore, the past decade featured an explosion of algebro-geometric techniques in areas outside of mathematics. As such, Gröbner bases have gained traction both as tool for studying polynomial systems and as object of interest themselves, e.g., as Markov bases in algebraic statistics. However, Gröbner bases are notoriously hard to compute, which severely inhibits their use in practical applications.We will investigate so-called saturating Gröbner bases. In general, polynomial unknowns represent arbitrary elements of the coefficient field, and all operations within a Gröbner basis computation respect this ambiguity. In practice, one is often only interested in specific solutions, e.g. strictly positive real solutions. Saturating Gröbner basis algorithm are symbolic algorithms which are capable of exploiting this numerical information that is abundant in many applications and use it to speed up its performance.