A hybrid approach to conjugate gradient algorithms for nonlinear systems of equations with applications in signal restoration

1.   Introduction

Let $V$ be an $\ell$-dimensional vector space over a field $\mathbb {K}$ of characteristic 0. An arrangement of hyperplanes ${\cal A}$ is a finite collection of codimension one affine subspaces in $V$. An arrangement ${\cal A}$ is called central if every hyperplane $H \in {\cal A}$ goes through the origin.

Let $V^*$ be the dual space of $V$, and $S = S(V^*)$ be the symmetric algebra over $V^*$. A $\mathbb{K}$-linear map $\theta :S \to S$ is called a derivation if for $f, g \in S$,

Let ${\rm{De}}{{\rm{r}}_\mathbb{K}}\left(S \right)$ be the $S$-module of derivations. When ${\cal A}$ is central, for each $H\in {\cal A}$, choose $\alpha_H\in V^{*}$ with $\ker(\alpha_H) = H$. Define an $S$-submodule of ${\rm{De}}{{\rm{r}}_\mathbb{K}}\left(S \right)$, called the module of ${\cal A}$-derivations by

The arrangement ${\cal A}$ is called free if ${\cal D}\left({\cal A} \right)$ is a free $S$-module. Then, ${\cal D}\left({\cal A}\right)$ has a basis comprising of $\ell$ homogeneous elements. For an affine arrangement $\mathcal A$ in $V$, $\bf{c}\mathcal A$ denotes the cone over $\mathcal A$ ^[7], which is a central arrangement in an $(\ell + 1)$-dimensional vector space by adding the new coordinate $z$.

Let $E = {\mathbb{R}}^\ell$ be an $\ell$-dimensional Euclidean space with a coordinate system ${x_1}, \ldots, {x_\ell }$, and let $\Phi$ be a crystallographic irreducible root system in the dual space $E^*$. Let ${\Phi }^+$ be a positive system of $\Phi$. For $\alpha \in {\Phi }^+$ and $k \in \mathbb{Z}$, define an affine hyperplane ${H_{\alpha, k}}$ by

The ${\rm{Shi}}$ arrangement ${\rm{Shi}}\left(\ell \right)$ was introduced by Shi in the study of the Kazhdan-Lusztig representation theory of the affine Weyl groups in ^[9] by

when the root system is of type ${A}_{\ell-1}$.

For $m\in \mathbb{Z}_{\geq 0}$, the extended Shi arrangement $\mathrm{Shi}^{k}$ of the type $\Phi$ is an affine arrangement defined by

There are a lot of researches on the freeness of the cones over the extended Shi arrangements ^[1,3,4]. The first breakthrough was the proof of the freeness of multi-Coxeter arrangements with constant multiplicities by Terao in ^[13]. Combining it with algebro-geometric method, Yoshinaga proved the freeness of the extended Shi arrangements in ^[15]. Nevertheless, there has been limited progress in constructing their bases, and a universal method for determining these bases remains elusive. For types ${A}_{\ell-1}$, $B_\ell$, $C_\ell$, and $D_\ell$, explicit bases for the cones over the Shi arrangements were constructed in ^[6,10,11]. Notably, a basis for the extended Shi arrangements of type $A_2$ was established in ^[2]. Recently, Suyama and Yoshinaga constructed explicit bases for the extended Shi arrangements of type ${A_{\ell-1}}$ using discrete integrals in ^[12]. Feigin et al. presented integral expressions for specific bases of certain multiarrangements in ^[5]. In these studies, Suyama and Terao first constructed a basis for the derivation module of the cone over the Shi arrangement, as detailed in ^[11], with Bernoulli polynomials playing a central role in their approach. The following definitions are pertinent to this result.

For $\left({k_1, k_2} \right) \in {\left({{\mathbb{Z}_{ \ge 0}}} \right)^2}$, the homogenization polynomial of degree $k_1+k_2+1$ is defined by

where ${B_k}\left(x \right)$ denotes the $k$-th Bernoulli polynomial and ${B_k}\left(0 \right) = {B_k}$ denotes the $k$-th Bernoulli number. Using this polynomial, the basis for ${\cal D}\left({\rm{{\bf{c}}Shi}\left(\ell \right) } \right)$ was constructed as follows.

Theorem 1.1. [11, Theorem 3.5] The arrangement ${\rm{{\bf{c}}Shi}\left(\ell \right) }$ is free with the exponents $\left({0, 1, {\ell^{\ell - 1}}} \right)$. The homogeneous derivations

form a basis for ${\cal D}\left({\rm{{\bf{c}}Shi}\left(\ell \right) } \right)$, where $1 \le j \le \ell - 1$ and ${\partial _i}\left({1 \le i \le \ell} \right)$, ${\partial _z}$ denote $\frac{\partial }{{\partial {x_i}}}$, $\frac{\partial }{{\partial z}}$ respectively. $I_{\left[{u, v} \right]}^k$ represents the elementary symmetric function in the variables $\left\{ {{x_u}, {x_{u + 1}}, \ldots, {x_v}} \right\}$ of degree $k$ for $1 \le u \le v \le \ell$.

The above conclusion was reached by using Saito's criterion, which is a crucial theorem for determining the basis of a free arrangement.

Theorem 1.2. [8, Saito's criterion] Let ${\cal A}$ be a central arrangement, and $Q\left({\cal A} \right)$ be the defining polynomial of ${\cal A}$. Given ${\theta _1}, \ldots, {\theta _\ell } \in {\cal D}\left({\cal A} \right)$, the following two conditions are equivalent:

$\left(1 \right)\; {\rm{detM}}\left({{\theta _1}, \ldots, {\theta _\ell }} \right)\doteq Q\left({\cal A} \right),$

$\left(2 \right)\; {\theta _1}, \ldots, {\theta _\ell }$ form a basis for ${\cal D}\left({\cal A} \right)$ over $S$,

where ${\rm{M}}\left({{\theta _1}, \ldots, {\theta _\ell }} \right) = {\Big({{\theta _j}\left({{x_i}} \right)} \Big)_{\ell \times \ell }}$ denotes the coefficient matrix, and $A\doteq B$ means that $A = cB$, $c \in \mathbb{K}\setminus\{0\}$.

This theorem provides a useful tool for determining when a set of derivations forms a basis for the module of derivations associated with a central arrangement.

Let ${\alpha _\ell} = {\left({1, \ldots, 1} \right)^T}$ and ${\beta _\ell } = {\left({{x_1}, \ldots, {x_\ell }} \right)^T}$ be the $\ell \times 1$ column vectors, and define $\psi _{i, j}^{(\ell)} : = \psi _j^{(\ell)}\left({{x_i}} \right)$ for $1 \le i \le \ell$, $1 \le j \le \ell - 1$. Suyuma and Terao in ^[11] proved the equality

which yields

A graph $G = \left(V, E \right)$ is defined as an ordered pair, where the set ${V} = \left\{ 1, 2, \ldots, \ell \right\}$ represents the vertex set, and ${E}$ is a collection of two-element subsets of ${V}$. If $\left\{ i, j \right\} \in {E}$ for some $i, j \in {V}$, then $\left\{ i, j \right\}$ is referred to as an edge. Writing $\left\{ i, j \right\} \in G$ implies $\left\{ i, j \right\} \in {E}$. Let ${U} \subseteq {V}$, and define ${E}\left({U} \right) = \left\{ \{i, j\} \mid i, j \in {U}, \{i, j\} \in{E} \right\}$. We say ${U}$ induces a subgraph $G_{{U}} = \left({U}, {E}\left({U} \right) \right)$. Specifically, we use the symbol $K_{{U}}$ for the induced subgraph of the complete graph $K_{\ell}$. For $i < j$, the interval notation $\left[i, j \right]$ represents $\left\{ i, i + 1, \ldots, j \right\}$.

For a graph $G$ on the vertex set $\left\{ {1, 2, \ldots, \ell} \right\}$, the arrangement ${\rm{Shi}}\left(G \right)$ was defined in ^[14] by

Then, ${\rm Shi}\left(G \right)$ is an arrangement between the Linial arrangement

and the Shi arrangement ${\rm{Shi}}\left(\ell \right)$. Write $\mathcal{A}\left(G \right) : = \mathbf{c}{\rm Shi}\left(G \right)$. It was classified to be free according to the following theorem.

Theorem 1.3. [14, Theorem 3] The arrangement ${\cal A}\left({G} \right)$ is free if and only if $G$ consists of all edges of three complete induced subgraphs ${G_{\left[{1, s} \right]}}, {G_{\left[{t, \ell} \right]}}, {G_{\left[{2, \ell - 1} \right]}}$, where $1 \le s \le \ell$, $t \le s + 1.$ The free arrangement ${\cal A}\left({G} \right)$ has exponents $\left({0, 1, {{\left({\ell - 1} \right)}^{\ell + t- s - 2}}, {\ell^{{s-t + 1}}}} \right)$ for $s < \ell$ and $t > 1$, and $\left({0, 1, {\ell^{\ell - 1}}} \right)$ for $s = \ell$ or $t = 1$.

For $s, t\in \mathbb{Z}^{+}$, we may define the arrangement

By Theorem 1.3, for $1 \le s \le \ell$ and $t \le s+1$, the arrangement ${\cal A}\left[{s, t} \right]$ is free with exponents $\left({0, 1, {{\left({\ell - 1} \right)}^{\ell + t - s - 2}}, {\ell^{{s-t+ 1}}}} \right)$ for $s < \ell$ and $t > 1$, and $\left({0, 1, {\ell^{\ell - 1}}} \right)$ for $s = \ell$ or $t = 1$.

For $0 \le q \le \ell-2$, we write ${\cal A}\left[{q} \right]: = {\cal A}\left[{\ell - 1, \ell - q} \right]$, then ${\cal A}\left[{q} \right]$ is free with exponents $\left({0, 1, {{\left({\ell - 1} \right)}^{\ell - q - 1}}, {\ell ^q}} \right)$.

2.   Main results

In this section, based on the conclusions of Suyama and Terao, we provide an explicit construction of the basis for ${\cal D}\left({{\cal A}\left[q \right]} \right)$, ${0 \le q \le \ell-2}$. First, we shall establish a basis for ${\cal D}\left({{\cal A}\left[0 \right]} \right)$, which is the ingredient of the basis for ${\cal D}\left({{\cal A}\left[q \right]} \right)$.

Theorem 2.1. For $1 \le j \le \ell - 2$, define homogeneous derivations

where

Then, the derivations $\eta _1, \eta _2, \varphi _1^{\left(0 \right)}, \ldots, \varphi _{\ell - 1}^{\left(0 \right)}$ form a basis for ${\cal D}\left({{\cal A}\left[0 \right]} \right)$.

Proof. Write ${\varphi^{\left(0 \right)} _{i, j}}: = \varphi _j^{\left(0 \right)}\left({{x_i}} \right), 1 \le i \le \ell, 1 \le j \le \ell - 1$, and from the definitions of $\varphi_j^{(0)}$ and ${\psi _j^{(\ell)}}$, we can get

for $1 \le i \le \ell-1$, $1 \le j \le \ell-2$. Consequently, for $1 \le m < n \le \ell-1$, it follows that ${\varphi _j^{\left(0 \right)}} \left({{x_m} - {x_n}} \right)$ is divisible by ${{x_m} - {x_n}}$, and ${\varphi _j^{\left(0 \right)}}\left({{x_m} - {x_n} - z} \right)$ is divisible by ${{x_m} - {x_n} - z}.$ For $1 \le m \le \ell-1$, let the congruence notation $\mathop \equiv \limits^{\left({m, k} \right)}$ in the subsequent calculation denote modulo the ideal $\left({{x_m} - {x_\ell} - kz} \right).$ We derive

which implies that ${\varphi _j^{\left(0 \right)}\left({{x_m} - {x_\ell} - z} \right)}$ is divisible by ${{x_m} - {x_\ell} - z}.$ Thus, $\varphi _j^{\left(0 \right)} \in {\cal D}\left({{\cal A}\left[0 \right]} \right)$ for $1 \le j \le \ell-2$. Therefore, we have $\eta _1, \eta _2, \varphi _1^{\left(0 \right)}, \ldots, \varphi _{\ell-1}^{\left(0 \right)}\in {\cal D}\left({{\cal A}\left[0 \right]} \right)$. Additionally, we obtain

According to the equalities (1.1) and (2.1), we have

Hence, we obtain

By applying Theorem 1.2, we conclude that the derivations $\eta _1, \eta _2, \varphi _1^{\left(0 \right)}, \ldots, \varphi _{\ell-1}^{\left(0 \right)}$ form a basis for ${\cal D}\left({{\cal A}\left[0 \right]} \right)$. □

Definition 2.1. For $1 \le q \le \ell - 2$, $1 \le j \le \ell - 1$, define the homogeneous derivations

To prove the derivations $\eta _1, \eta _2, \varphi _1^{\left(q \right)}, \ldots, \varphi _{\ell - 1}^{\left(q \right)}$ form a basis for ${\cal D}\left({{\cal A}\left[q \right]} \right)$, first we prove all such derivations belong to the module ${\cal D}\left({{\cal A}\left[q \right]} \right).$

Theorem 2.2. For $1 \le m \le \ell - 1$, $1 \le j \le \ell - 2$, we have

Proof. We have the following congruence relation of polynomials modulo the ideal $\left({{x_m} - {x_\ell} } \right).$

We complete the proof. □

Remark 2.1 In equality (2.2), we observe that $\prod\limits_{s = j + 2}^{\ell - 1} {\left({{x_s} - {x_m }} \right)} = 0$ for $j+2 \le m \le \ell-1$. This implies that $\varphi _j^{\left(0 \right)}\left({{x_m} - {x_\ell}} \right)$ is divisible by ${{x_m} - {x_\ell}}$ for $1 \le j \le \ell-3$ and $j+2 \le m \le \ell-1$.

According to Remark 2.1, for $1 \le j \le \ell-q-2$, we have $\varphi_{j}^{(0)}\left(x_{m}-x_{\ell}\right)$ is divisible by $x_{m}-x_{\ell}$ for $\ell-q \leq m \leq \ell-1$, which implies that $\varphi _j^{\left(q \right)} = \varphi _j^{\left(0 \right)} \in {\cal D}\left({{\cal A}\left[q \right]} \right)$. Therefore, to prove the derivations belong to the module ${\cal D}\left({{\cal A}\left[q \right]} \right)$, it suffices to prove $\varphi _j^{\left(q \right)} \in {\cal D}\left({{\cal A}\left[q \right]} \right)$ for $\ell-q-1 \le j \le \ell-1$.

For the sake of convenience in the proof, let us introduce the notations for $f, g, h\in \mathbb{Z}^{+}$,

If $g > h$, we agree that ${\rm{A}}_f^{\left[{g, h} \right]} = {\rm{B}}_f^{\left[{g, h} \right]} = 1$.

Lemma 2.1. For any $u, v, w \in \mathbb {Z}^+$ that satisfy $4 \leq \ell-j+1 \leq u \leq \ell-2$, $3 \leq v \leq \ell-2$, and $3 \leq w \leq \ell-2$, we have the following three equalities:

Proof. We will only prove equality (2.5) by induction on $w$. The proofs of equalities (2.3) and (2.4) are similar. For $w = 3$,

and the equality holds. Assume that for $w = k\le \ell-3$, the equality holds. Then, we replace ${x_{\ell-k-1}}$ with ${x_{\ell-k-2}}$, and multiply both sides of the equality by $({x_{\ell-k-1}} - {x_{\ell-k-2}} - z)$ to get

We have completed the induction. □

Lemma 2.2. The derivation $\varphi _j^{\left(q \right)}$ belongs to the module ${\cal D}\left({{\cal A}\left[q \right]} \right)$ for ${2 \le q \le \ell-2}$ and $\ell-q-1 \le j \le \ell-3$.

Proof. For $2 \le q \le \ell-2$ and $j = \ell-q-1$, it is evident from Remark 2.1 that

For $3 \le q \le \ell-2$ and $\ell-q \le j \le \ell-3$, we will establish this by induction on $q$. From Theorem 2.2, for $\ell-q \le m \le \ell-1$, we have

(1) For $q = 3$, we get

If $m = \ell-3, \ell-2, \ell-1$, then we have $\varphi _{\ell - 3}^{(3)}\left({{x_m} - {x_\ell }} \right)\mathop \equiv \limits^{\left({m, 0} \right)} 0$, which indicates that $\varphi _{\ell - 3}^{(3)}\left({{x_m} - {x_\ell }} \right)$ is divisible by ${{x_m} - {x_\ell }}$ for $m = \ell-3, \ell-2, \ell-1$. Therefore, $\varphi _j^{\left({3} \right)} \in {\cal D}\left({{\cal A}\left[{3} \right]} \right)$.

(2) For $q = k\; {\le \ell-3 }$, assume that $\varphi _j^{\left(k \right)} \in {\cal D}\left({{\cal A}\left[k \right]} \right)$, which implies that $\varphi _j^{\left(k \right)}\left({{x_m} - {x_\ell}} \right)$ is divisible by ${x_m} - {x_\ell}$ for $\ell-k \le m \le \ell-1$.

For $q = k + 1$, we observe that

According to the induction hypothesis and Remark 2.1, it is sufficient to prove that ${\varphi _j^{(k+1)}\left({{x_{\ell-k - 1}} - {x_\ell}} \right)}$ is divisible by ${{x_{\ell-k - 1}} - {x_\ell}}$. By using the equality (2.3), we obtain

Therefore, ${\varphi _j^{\left({k+ 1} \right)}\left({{x_{\ell-k - 1}} - {x_\ell}} \right)}$ is divisible by ${{x_{\ell-k - 1}} - {x_\ell}}$, and it follows that $\varphi _j^{\left({k+ 1} \right)} \in {\cal D}\left({{\cal A}\left[{k+1} \right]} \right)$. Consequently, we can conclude that for any $3 \le q \le \ell-2$ and $\ell-q \le j \le \ell-3$, $\varphi _j^{\left(q \right)} \in {\cal D}\left({{\cal A}\left[q \right]} \right)$. □

Lemma 2.3. The derivation $\varphi _{\ell-2}^{\left(q \right)}$ belongs to the module ${\cal D}\left({{\cal A}\left[q \right]} \right)$ for ${1 \le q \le \ell-2}$.

Proof. From Theorem 2.2, we can get the following equality for $\ell-q \le m \le \ell-1$,

(1) For $q = 1, 2$, this conclusion is straightforward to verify.

(2) For $q = k\; {\le \ell-3 }$, assume that $\varphi _{\ell-2}^{\left({k} \right)} \in {\cal D}\left({{\cal A}\left[{k} \right]} \right)$, which implies that $\varphi _{\ell-2}^{\left({k} \right)}\left({{x_m} - {x_\ell}} \right)$ is divisible by ${{x_m} - {x_\ell}}$ for $\ell-k\le m \le \ell-1$.

For $q = k + 1$, we have

By using the equality (2.4), we have

Therefore, ${\varphi _{\ell-2}^{\left({k+1} \right)}\left({{x_{\ell-k-1}} - {x_\ell}} \right)}$ is divisible by ${{x_{\ell-k-1}} - {x_\ell}}$. According to the induction hypothesis and Remark 2.1, we have $\varphi _{\ell-2}^{\left({k+1} \right)} \in {\cal D}\left({{\cal A}\left[{k+1} \right]} \right)$. Hence, we may conclude that for any $1 \le q \le \ell-2$, $\varphi _{\ell-2}^{\left(q \right)} \in {\cal D}\left({{\cal A}\left[q \right]} \right)$. □

Lemma 2.4. The derivation $\varphi _{\ell - 1}^{\left({q} \right)}$ belongs to the module ${\cal D}\left({{\cal A}\left[{ q} \right]} \right)$ for $1 \le q \le \ell - 2$.

Proof. First, from Theorem 2.2, for $\ell-q \le m \le \ell-1$, we can get

(1) For $q = 1, 2$, it is obvious that $\varphi _{\ell-1}^{\left(q \right)} \in {\cal D}\left({{\cal A}\left[q \right]} \right)$.

(2) For $q = k\; {\le \ell-3 }$, assume that $\varphi _{\ell-1}^{\left({k} \right)} \in {\cal D}\left({{\cal A}\left[{k} \right]} \right)$, which implies that $\varphi _{\ell-1}^{\left({k} \right)}\left({{x_m} - {x_\ell}} \right)$ is divisible by ${{x_m} - {x_\ell}}$ for $\ell-k\le m \le \ell-1$.

For $q = k + 1$, we can see

By using the equality (2.5), we have

Therefore, ${\varphi _{\ell-1}^{\left({k+1} \right)}\left({{x_{\ell-k- 1}} - {x_{\ell}}} \right)}$ is divisible by ${{x_{\ell-k- 1}} - {x_{\ell}}}$. According to the induction hypothesis and Remark 2.1, we have $\varphi _{\ell-1}^{\left({k+1} \right)} \in {\cal D}\left({{\cal A}\left[{k+1} \right]} \right)$. Hence, we may conclude that for any $1 \le q \le \ell-2$, $\varphi _{\ell-1}^{\left(q \right)} \in {\cal D}\left({{\cal A}\left[q \right]} \right)$. □

From the above proof, we finally conclude that $\varphi _1^{\left(q \right)}, \ldots, \varphi _{\ell - 1}^{\left(q \right)}$ belong to the module ${\cal D}\left({{\cal A}\left[{ q} \right]} \right)$.

Theorem 2.3. For $1 \le q \le \ell-2$, the derivations $\eta _1, \eta _2, \varphi _1^{\left(q \right)}, \ldots, \varphi _{\ell - 1}^{\left(q \right)}$ form a basis for ${\cal D}\left({{\cal A}\left[q \right]} \right)$.

Proof. According to Lemmas 2.2–2.4, it suffices to prove that

Let

and

be the $(q+1) \times 1$ column vectors, and define a matrix

Write ${\widetilde M_{{(q + 1)} \times {(q + 1)}}}{\rm{ : = }}\left({{M_{\left({q + 1} \right) \times \left({q - 1} \right)}}, {\gamma _1}, {\gamma _2}} \right)$, then

Thus, we obtain the following equality

Hence,

We complete the proof. □

Author contributions

Meihui Jiang: writing-original draft; Ruimei Gao: writing-review and editing, methodology and supervision. All authors have read and approved the final version of the manuscript for publication.

Use of Generative-AI tools declaration

The authors declare they have used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The work was partially supported by Science and Technology Development Plan Project of Jilin Province, China (No. 20230101186JC) and NSF of China (No. 11501051).

Conflict of interest

The authors declare no conflict of interest in this paper.