zhongzihao/gauss_grid

四（八）连通网格图上的高斯消元

假设我们在一个网格图上定义了一些转移，我们要对这个线性方程组做高斯消元。注意到这个矩阵非常稀疏，即每个方程至多只有 \(5(9)\) 个变元。因此我们可以只维护非零的系数。我们证明，如果按照 \((0,0),\cdots,(0,m-1),\cdots,(n-1,0),\cdots,(n-1,m-1)\) 的顺序消元的话，时间复杂度为 \(\mathcal{O}(nm^{3})\)。

以四连通为例，我们很容易归纳地证明，每个点所代表的方程在任何时刻都只有不超过 \(\mathcal{O}(m)\) 的变元，\((x,y)\) 最终被前面的方程消完后，剩下的变元是 \((x,y),(x,y+1),\cdots,(x,m-1),(x+1,0),(x+1,1),\cdots,(x+1,y)\)。

八连通也是类似的，最后剩下的变元还要加上一个 \((x+1,y+1)\)。

在消元的过程中我们还会发现，一个方程最多也只需要去消后面的 \(\mathcal{O}(m)\) 个方程（大约是 \(2m\) 个），因此总复杂度是 \(\mathcal{O}(nm^{3})\)。

事实上，我们可以将矩阵转置，将复杂度降为 \(\mathcal{O}(nm\min^{2}(n,m))\)。