*姜 刘 (上海理工大学)
In differential geometry, massive calculation involving indexed differential expressions arises from various problems, such as tensor verification problem, and the problem of finding transformation rules of indexed functions under coordinate transformation. It is a fundamental problem in symbolic computation to judge whether two indexed differentials are equal or not. The general theory for this problem (or, for finding the canonical form of a polynomial) was established in our previous work by extending Gr\"obner basis theory and constructing ``fundamental restricted ring". However, for an indexed differential monomial $f$ with $k$ lower indices and $j$ upper indices, the general theory for finding the canonical form of the monomial has the complexity of at least $O((k!)^{3}\prod\limits_{i=0}^{j}(k-i)^{3})$. In this work, a much more efficient method is put forward. First, invariance of Leibniz expansion of indexed differentials under differential operators and monoterm symmetries is investigated. More precisely, we prove that the Leibniz expansion is invariant under both differential operator and monoterm symmetries, as in the following two propositions. \begin{proposition}\label{pro1} Suppose $f*h,g*h$ are two pre-monomials in $\mathbf{E}_{\part}$, and $f$ can be rewritten as $g$ by Leibniz rule. Then \begin{enumerate} \item[(1)] $\part_{\mathcal{I}}f$ can be rewritten as $\part_{\mathcal{I}}g$ by Leibniz rule, where $\mathcal{I}$ is an index sequence. \item[(2)] $[(\part_{\mathcal{I}}f)*h]_{\text{E}}$ is identical to $[(\part_{\mathcal{I}}g)*h]_{\text{E}}$, where $[\cdot]_{\text{E}}$ denotes the Leibniz expansion of a polynomial. \end{enumerate} \end{proposition} \begin{proposition}\label{syminvariant} Suppose $m=\part_{\mathcal{I}_{1}a\mathcal{I}_{2}}^{C}\part_{s'}^{a}*f_{\text{ex}}$, and $m_1=\part_{\sigma_{1}(\mathcal{I}_1)a\sigma_{2}(\mathcal{I}_2)}^{C}\part_{s'}^{a}*g_{\text{ex}}$, where $\sigma_1, \sigma_2$ are permutations of indices which obey unifying symmetries, $g_{\text{ex}}$ is a submonomial which can be rewritten as $f_{\text{ex}}$ by unifying symmetry. \begin{itemize} \item[(1)] $[m]_{\text{Em}}=[\Ren(m)]_{\text{Em}}$, where $\Ren$ is a dummy index renaming mapping. \item[(2)] $[m]_{\text{Em}}=[\part_{\mathcal{I}_1a\sigma_{2}(\mathcal{I}_2)}^{C}\part_{s'}^{a}*g_{\text{ex}}]_{\text{Em}}$. And if $\mathcal{I}_2\neq \emptyset$, then $[m]_{\text{Em}}=[m_1]_{\text{Em}}$, where $[\cdot]_{\text{Em}}$ denotes the mono-normal form of the Leibniz expansion of a polynomial.\end{itemize}\end{proposition} Then, much simpler generators of the ideal generated by the basic syzygies are found, as follows. \begin{theorem}\label{newform} Let $\Omega$ be the set $$\{[m_1]_{\text{Em}}-[m_2]_{\text{Em}}\mid(m_1)_{mon}=(m_2)_{mon}, m_1,m_2\in \mathbf{E}_{\part}\}.$$ The ideal generated by $\Omega$ can be generated by $\Theta$, where $\Theta$ is a set consisting of polynomials in the form of $[\part_{\mathcal{I}_{1}ab\mathcal{I}_{2}}^{C}\part_{s'}^{a}*f_{\text{ex}}]_{\text{Em}}- [\part_{\mathcal{I}_{1}ba\mathcal{I}_{2}}^{C}\part_{s'}^{a}*f_{\text{ex}}]_{\text{Em}}$. \end{theorem} Consequently, the properties of reductions with respect to the generators are explored. \begin{proposition} Let $P_1$ and $P_2$ be both op-monomials in $\Theta$, and $Q$ be a linear combination of cl-monomials in $\Theta$. \begin{itemize} \item[(1)] $\mathrm{spol}(P_1,P_2)$ can be reduced to 0 by $\Theta$. \item[(2)] $\mathrm{spol}(P_1,Q)$ can be reduced to 0 by $\Theta$. \end{itemize} \end{proposition} Finally, a normalization algorithm of indexed differentials with much lower complexity is provided. Especially, it has polynomial complexity $O(k^2)$ for op-monomials.
Math formula preview: