标题： 霍奇分解与嵌入单纯复形的通用拉普拉斯求解器 显示英文标题

标题： Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes

摘要： 我们描述了一个几乎线性时间算法来求解由复形的第一个贝蒂数参数化的线性系统$L_1x = b$，其中$L_1$是一个单纯复形$K$的 1-拉普拉斯矩阵，该复形是线性嵌入在$\mathbb{R}^{3}$中的可收缩复形$X$的子复形。 我们的算法推广了 Black 等人~[SODA2022] 的工作，该工作解决了相同的问题，但要求$K$具有平凡的第一同调群。 我们的算法适用于具有任意第一同调群的复形$K$，其运行时间相对于复形的大小几乎是线性的，并且相对于第一贝蒂数是多项式的。 我们求解器的关键是一种新的算法，可以在几乎线性时间内计算$K$的1链的Hodge分解。 此外，我们的算法意味着对于任何嵌入在$\mathbb{R}^{3}$中的单纯复形$K$的1-Laplacian，可以得到几乎二次时间的求解器和几乎二次时间的Hodge分解，因为$K$总能被扩展为一个二次复杂度的可收缩嵌入复形。 显示英文摘要

摘要： We describe a nearly-linear time algorithm to solve the linear system $L_1x = b$ parameterized by the first Betti number of the complex, where $L_1$ is the 1-Laplacian of a simplicial complex $K$ that is a subcomplex of a collapsible complex $X$ linearly embedded in $\mathbb{R}^{3}$. Our algorithm generalizes the work of Black et al.~[SODA2022] that solved the same problem but required that $K$ have trivial first homology. Our algorithm works for complexes $K$ with arbitrary first homology with running time that is nearly-linear with respect to the size of the complex and polynomial with respect to the first Betti number. The key to our solver is a new algorithm for computing the Hodge decomposition of 1-chains of $K$ in nearly-linear time. Additionally, our algorithm implies a nearly quadratic solver and nearly quadratic Hodge decomposition for the 1-Laplacian of any simplicial complex $K$ embedded in $\mathbb{R}^{3}$, as $K$ can always be expanded to a collapsible embedded complex of quadratic complexity.