一些HomotopyContinuation求解器

bertini、Julia-HomotopyContinuation、GPU-HC、PHCpack

HomotopyContinuation求解器是一种用于求解多项式方程组的工具，它们可以用于求解SLAM中的非线性方程组，这里介绍一些常用的HomotopyContinuation求解器以方便作对比试验。这里主要是求解器的介绍和使用，不作原理阐述和详细的对比

bertini/bertini2

bertini下载地址

bertini是一个开源的linux程序（win下使用会比较麻烦），只能用一个文本文件输入多项式，不能在程序里用API进行使用；而bertini2则可以在python里直接调用。

使用bertini

bertini一般只在linux下使用，首先从下载地址下载下bertini程序。

想要具体使用bertini可以看它的手册。

这里直接给出一个Zero-dimensional的例子（Zero-dimensional指的是一个多项式方程系统的解的数量是有限的）:

首先创建一个文本文件input
在这个input文件中输入多项式方程组，如下：

CONFIG
END;
INPUT
variable_group z1, z2;
function f1, f2;
f1 = (29/16)*z1^3 - 2*z1*z2;
f2 = z2 - z1^2;
END;

把input文件放到bertini的目录下，然后在命令行输入./bertini input
因为一般SLAM系统中需要求解的东西都是实根，所以直接解析real_finite_solutions这个文件即可

显然，这种方式要求我们创建一个input文件，然后在命令行输入./bertini，然后再解析一个文本，中间需要经过多次IO操作，不够方便。而且bertini同一时间只能存在一个input和real_finite_solutions文件，所以很难做并行化，不过胜在使用简单。不过一般只能求解方阵系统(square system，即未知数和方程数目一致)。

使用bertini2

bertini2基本就是暴露了API接口的bertini，安装按照github上的说明即可。

不过bertini2需要安装boost库，而且需要boost>=1.83，目前好像没法直接通过apt安装这个版本的boost，只能从源码安装，这就挺麻烦的。

关于文档可以参考这里

Julia HomotopyContinuation

Julia HomotopyContinuation 官网

Julia HomotopyContinuation是一个用julia语言开发的HomotopyContinuation库，julia是一个编程语言，可以直接在jupyter中使用。安装julia和HomotopyContinuation可以直接参考官网即可。

由于这个库的文档实在是做的太好了(对比之下其他的文档界面都如此复古)，就直接给一个简单的例子。

using HomotopyContinuation 
@var x y; 
f = System([x^2 + 2y, y^2 - 2]) 
result = solve(f)

另外，这个库还可以求monodromy、Polyhedral方法构成的start system，当然一般也仅限于方阵系统(square system)。

GPU-HC

GPU-HC repo

GPU-HC是一个基于GPU的HomotopyContinuation求解器，它首先使用monodromy方法计算出多项式系统的start-system，然后用GPU并行计算出所有解。

GPU-HC的使用方法比较复杂，另外值得一提的是，这个repo的release和master分支有很大的不同：release中的代码是比较早的版本，并且具有CPU版本(额，名字叫GPU-HC，但是提供了纯CPU的版本)。而且release中的代码例子更多，当然使用时要改的东西也更多就是了。

由于GPU-HC的使用比较复杂，这里以master分支进行简单阐述。

安装环境和编译

之前为了跑这个代码，还写了一个好几百字的文档用来记录里面的坑，但是后来找不到了，所以后面的叙述可能有一些遗漏。

另外，当时给配好的GPU-HC环境做了个autodl的镜像，有需要的人可以联系我共享给你。

GPU-HC的环境配置非常非常麻烦，首先要安装GPU环境，包括CUDA、cuBlas之类的。

然后安装MAGMA这个线性代数库，虽然readme中说MAGMA>=2.6.1，但是实测只有2.6.1版本的能用，更高版本的MAGMA会报错。

然后安装openBlas库，这个直接用sudo apt-get install libopenblas-dev安装即可。

接下来就需要编译GPU-HC的代码了，不过这个repo里很多地方也是要改的。

首先需要给magmaHC/gpu-kernels/下的多个文件里添加上#define ADD_，然后需要把magmaHC/CMakeLists.txt中的include_directories改成本机上已经安装好的MAGMA、CUDA的路径，还要把对应的target_link_libraries改成本机上已经安装好的MAGMA、CUDA、openblas库的路径，并链接上pthread库。

同样需要修改的还有根目录下的CMakeLists.txt，也是需要把include_directories改成本机安装的MAGMA、CUDA的路径。

至此应该就可以正常编译本项目了。

使用GPU-HC解多项式

这里按照readme中步骤来，先在matlab中生成一个多项式方程组，求解出雅可比矩阵的txt，这里的matlab中的路径也需要注意自己去修改。然后用julia的homotopycontinuation库来解monodromy，Julia语言写的脚本可以用jupyter来运行。

新写好的多项式问题后还需要把他们加入到CMakeLists.txt里才能正常编译。

最后，HC的配置比如hc_step、newton_iter之类的配置都在magmaHC/definitions.hpp中，需要根据实际情况修改。

PHCpack

我们用PHCpack的python接口，也就是phcpy，安装这个库，需要首先把安装alr，可以从alr的release中下载对应的压缩包，解压后把alr程序移动到/bin目录下即可。

然后把PHCpack的源码下载下来，并用alr编译即可

sudo apt install gnat gprbuild
git clone https://github.com/janverschelde/PHCpack.git
cd PHCpack
alr install

然后把编译好的libPHCpack.so复制到需要安装的目录下

cp lib/libPHCpack.so src/lib
cp lib/libPHCpack.so src/Python/PHCpy/lib/
cp lib/libPHCpack.so src/Python/PHCpy/phcpy/

cd src/Python/PHCpy/
python3 setup.py install

这样就安装好了，下面给一个简单的例子，更多例子可以参考文档

from phcpy.solver import solve
p = ['x + y - 1;', 'x - y - 1;']
s = solve(p)
print(s[0])