论文标题
通过零强迫集和应用程序求解线性方程的系统
Solving systems of linear equations through zero forcing set and application to lights out
论文作者
论文摘要
令$ \ mathbb {f} $为任何字段，我们考虑求解$ ax = b $，重复对矩阵$ a \ in \ mathbb {f}^{f}^{n \ times n} $ of $ m $ non-ZERO元素的$ m $ non-Zero元素，以及多个不同的$ b \ in \ Mathbb in \ Mathbb {f}^n} $。如果我们给出了$ a $ a $ a $ a $ k $的零强制集，然后我们可以在$ o（mk）$ time中构建一个数据结构，以便可以用$ a ax = b $的每个实例以$ o（k^2+m）$时间来解决。作为一个应用程序，我们在$ o（n^3）$ time中求解了$ n \ times n $网格中的灯光游戏，然后通过利用网格中的重复结构来将运行时间提高到$ o（n^ω\ log n）$。
Let $\mathbb{F}$ be any field, we consider solving $Ax=b$ repeatedly for a matrix $A\in\mathbb{F}^{n\times n}$ of $m$ non-zero elements, and multiple different $b\in\mathbb{F}^{n}$. If we are given a zero forcing set of $A$ of size $k$, we can then build a data structure in $O(mk)$ time, such that each instance of $Ax=b$ can be solved in $O(k^2+m)$ time. As an application, we show how the lights out game in an $n\times n$ grid is solved in $O(n^3)$ time, and then improve the running time to $O(n^ω\log n)$ by exploiting the repeated structure in grids.
