In this paper, we study the hardness of solving graph-structured linear systems with coefficients over a finite field $\mathbb{Z}_p$ and over a polynomial ring $\mathbb{F}[x_1,\ldots,x_t]$. We reduce solving general linear systems in $\mathbb{Z}_p$ to solving unit-weight low-degree graph Laplacians over $\mathbb{Z}_p$ with a polylogarithmic overhead on the number of non-zeros. Given the hardness of solving general linear systems in $\mathbb{Z}_p$ [Casacuberta-Kyng 2022], this result shows that it is unlikely that we can generalize Laplacian solvers over $\mathbb{R}$, or finite-element based methods over $\mathbb{R}$ in general, to a finite-field setting. We also reduce solving general linear systems over $\mathbb{Z}_p$ to solving linear systems whose coefficient matrices are walk matrices (matrices with all ones on the diagonal) and normalized Laplacians (Laplacians that are also walk matrices) over $\mathbb{Z}_p$. We often need to apply linear system solvers to random linear systems, in which case the worst case analysis above might be less relevant. For example, we often need to substitute variables in a symbolic matrix with random values. Here, a symbolic matrix is simply a matrix whose entries are in a polynomial ring $\mathbb{F}[x_1, \ldots, x_t]$. We formally define the reducibility between symbolic matrix classes, which are classified in terms of the degrees of the entries and the number of occurrences of the variables. We show that the determinant identity testing problem for symbolic matrices with polynomial degree $1$ and variable multiplicity at most $3$ is at least as hard as the same problem for general matrices over $\mathbb{R}$.

翻译：在本文中, 我们研究解析以固定字段 $\ mathbb ⁇ p$ 和多数值环 $\ mathbb{F} [x_ 1,\ldots,x_t]$] 解决图形结构线性系统的难度。 我们减少以$\mathb ⁇ p$ 解决普通线性系统的难度, 以解决单位重量低度图$ mathbb ⁇ p$, 并解决非零数的多元线性管理费。 鉴于解析普通线性系统非常困难 $\ mathb ⁇ p$ [Casacuberta- Kyng 2022] [Casacuberta- kyng 美元 美元环 [xxx_mathbbb{Flock] 美元[xxxxxxxxxxxxxxx] 的难度。 我们不可能将一般线性解决的普通线性系统一般的通用线性系统, 而我们最接近的线性矩阵的系统 也比我们更需要一个直数。