A note on the preconditioned tensor splitting iterative method for solving strong $\mathcal{M}$-tensor systems

1.   Introduction

In this note, we consider the following multi-linear system

where $\mathcal {A} = (a_{i_{1}i_{2}\cdots i_{m}})$ is an order $m$ dimension $n$ tensor, $\mathbf{x}$ and $\mathbf{b}$ are $n$ dimensional vectors, and the tensor-vector product $\mathcal {A}\mathbf{x}^{m-1}$ is defined as [1]

where $x_{i}$ denotes the $i$-th component of $\mathbf{x}$. The multi-linear system (1.1) arises from a number of scientific computing and engineering applications ^[1,2,6], such as data analysis ^[10], the sparsest solutions to tensor complementarity problems ^[11], and so on.

One of the applications of the multi-linear system (1.1) is the numerical solution of the partial differential equation with Dirichlet's boundary condition

where $\triangle = \sum_{k = 1}^{d}\frac{\partial^{2}}{\partial x_{k}^{2}}$ and $\Omega = [0, 1]^{d}$. When $f(\cdot)$ is a constant function, this PDE is a nonlinear Klein-Gordon equation (see ^[9,13,14]). Just as authors studied in ^[13,14], $u\mapsto u^{\theta}\cdot\bigtriangleup u$ can also be discretized into an $m$th-order nonsingular $\mathcal {M}$-tensor

which satisfies

for $i = 1, 2, \cdots, n$, where $\mathcal{L}_{h}$ is an $m$th-order tensor $\mathcal{M}$-tensor with

The PDE in (1.3) is discretized into an $\mathcal{M}$-equation $\mathcal{L}_{h}^{(d)}\mathbf{u}^{m-1} = \mathbf{f}$. This class of multi-linear equations can be regarded as a higher-order generalization of the one discussed in ^[9,15,16].

To solve the multi-linear system (1.1), Ng, Qi and Zhou ^[12] proposed an algorithm for $\mathbf{b} = \mathbf{0}$. When $\mathcal {A}$ is a strong $\mathcal{M}$-tensor, Ding and Wei ^[9] generalized the Jacobi method, the Gauss-Seidel method and the Newton algorithm. Liu et al. ^[3] discussed the tensor splitting $\mathcal{A} = \mathcal{E}-\mathcal{F}$, and then proposed a general tensor splitting iterative method for solving the multi-linear system (1.1) as follows:

where $\mathbf{x}_{0}$ is a given initial vector and the tensor $\mathcal{T} = M(\mathcal{E})^{-1}\mathcal{F}$ is called the iterative tensor of the splitting method (see ^[3,4]). They discussed the convergence rate for the tensor splitting iterative method and showed that the spectral radius $\rho(M(\mathcal{E})^{-1}\mathcal{F})$ can be seen as an approximate convergence rate of the iteration (1.4).

For matrix splitting iterative methods, it is well known that the preconditioning technique is very important, which can be used to improve the rate of convergence of the iterative method when a suitable preconditioner is chosen ^[4,5,7]. In ^[3], Liu et al. explored preconditioning techniques for tensor splitting methods and discussed the preconditioned Gauss-Seidel type and SOR type iterative methods, and proved that the Guass-Seidel type method demonstrates faster convergence than the Jacobi method, that is to say, the spectral radius of the iterative matrix of the Guass-Seidel method is not larger than the one of the Jacobi method. Recently, Cui et al. ^[5] proposed a new preconditioner for solving $\mathcal{M}$-tensor systems and gave some comparison theorems of the preconditioned Gauss-Seidel type method. The preconditioned iterative method is to transform the original system into the preconditioned form

where the matrix $P$ is a nonsingular preconditioner. Let $P\mathcal {A} = \mathcal{E}_{P}-\mathcal{F}_{P}$ be a splitting of $P\mathcal {A}$. Then the corresponding preconditioned tensor splitting iterative method is given as follows:

The rest of this paper is organized as follows. In Section 2 we introduce some definitions and some related lemmas which will be used in the sequel. In Section 3, we first present a counter-example for existing research results and then propose a new special preconditioner. Meanwhile, we give the comparison theorems for the preconditioned Gauss-Seidel type iterative methods. The final section is the concluding remark.

2.   Preliminaries

Let $\mathbf{0}$, $O$ and $\mathcal{O}$ denote a zero vector, a zero matrix and a zero tensor, respectively. Let $\mathcal{A}$ and $\mathcal{B}$ be two tensors with the same sizes. The order $\mathcal{A}\geq\mathcal{B}(>\mathcal{B})$ means that each entry of $\mathcal{A}$ is no less than (larger than) corresponding one of $\mathcal{B}$.

For a positive integer $n$, let $\langle n\rangle = \{1, 2, \cdots, n\}$. A tensor $\mathcal{A}$ consists of $n_{1}\times\cdots\times n_{m}$ entries in the real field $\mathbb{R}$:

If $n_{1} = \cdots = n_{m} = n$, $\mathcal{A}$ is called an order $m$ dimension $n$ tensor. We denote the set of all order $m$ dimension $n$ tensors by $\mathbb{R}^{[m, n]}$. When $m = 1$, $\mathbb{R}^{[1, n]}$ is simplified as $\mathbb{R}^{n}$, which is the set of all $n$-dimension real vectors. When $m = 2$, $\mathbb{R}^{[2, n]}$ denotes the set of all $n\times n$ real matrices. Similarly, the above notions can be generalized to the complex number field $\mathbb{C}$. Let $\mathbb{R}_{+}$ be the nonnegative real field. If each entry of $\mathcal{A}$ is nonnegative, we call $\mathcal{A}$ a nonnegative tensor, and the set of all the order $m$ dimension $n$ nonnegative tensors is denoted by $\mathbb{R}_{+}^{[m, n]}$.

Let $A\in \mathbb{R}^{[2, n]}$ and $\mathcal{B}\in \mathbb{R}^{[k, n]}$. The matrix-tensor product $\mathcal{C} = A\mathcal{B}\in\mathbb{R}^{[k, n]}$ is defined by

The formular (2.1) can be written as follows (see ^[3]):

where $\mathcal{C}_{(1)}$ and $\mathcal{B}_{(1)}$ are the matrices obtained from $\mathcal{C}$ and $\mathcal{B}$ flattened along the first index (see ^[3]), For example, if $\mathcal{B} = (b_{ijk})\in\mathbb{C}^{[3, n]}$, then

Next we recall some definitions and lemmas for the completeness our presentation.

Definition 2.1. ([1]) Let $\mathcal{A}\in\mathbb{R}^{[m, n]}$. A pair $(\lambda, \mathbf{x})\in \mathbb{C}\times(\mathbb{C}\setminus 0)$ is called an eigenvalue-eigenvector (or simply eigenpair) of $\mathcal{A}$ if they satisfy the equation

where $\mathbf{x}^{[m-1]} = (x_{1}^{m-1}, \cdots, x_{n}^{m-1})^{T}$. We call $(\lambda, \mathbf{x})$ an $H$-eigenpair if both $\lambda$ and $\mathbf{x}$ are real.

Let $\rho(\mathcal{A}) = max\{|\lambda|:\lambda\in\sigma(\mathcal{A})\}$ be the spectral radius of $\mathcal{A}$, where $\sigma(\mathcal{A})$ is the set of all eigenvalue of $\mathcal{A}$. We use $\mathcal{I}_{k} = (\delta_{i_{1}\cdots i_{k}})$ to denote a unit tensor with its entries given by:

Definition 2.2. (^[6]) Let $\mathcal{A}\in\mathbb{R}^{[m, n]}$. $\mathcal{A}$ is called a $\mathcal{Z}$-tensor if its off-diagonal entries are non-positive. $\mathcal{A}$ is called an $\mathcal{M}$-tensor if there exist a nonnegative tensor $\mathcal{B}$ and a positive real number $\eta\geq\rho(\mathcal{B})$ such that

If $\eta > \rho(\mathcal{B})$, then $\mathcal{A}$ is called a strong $\mathcal{M}$-tensor.

Definition 2.3. (^[2]) Let $\mathcal{A}\in\mathbb{C}^{[m, n]}$. Then the majorization matrix $M(\mathcal{A})$ of $\mathcal{A}$ is the $n\times n$ matrix with the entries

Lemma 2.1. (^[4,8])For $\mathcal{A}\in\mathbb{R}_{+}^{[m, n]}$, the following inequalities hold:

$\mu\mathbf{x}^{[m-1]}\leq(<)\mathcal{A}\mathbf{x}^{m-1}, \mathbf{x}\geq\mathbf{0}, \mathbf{x}\neq\mathbf{0}$, implies $\mu\leq(<)\rho(\mathcal{A})$,

and

$\mathcal{A}\mathbf{x}^{m-1}\leq\nu\mathbf{x}^{[m-1]}, \mathbf{x} > \mathbf{0}$, implies $\rho(\mathcal{A})\leq\nu$.

Lemma 2.2. (^[6])Let $\mathcal{A}$ be a $\mathcal{Z}$-tensor, then $\mathcal{A}$ is a strong $\mathcal{M}$-tensor if and only if $\mathcal{A}$ is a semi-positive; that is, there exists $\mathbf{x} > 0$ with $\mathcal{A}\mathbf{x}^{m-1} > 0$.

3.   Comparison theorems

The preconditioner $P_{\boldsymbol{\alpha}}$ was introduced in ^[4] as follows:

where

and $I$ is an identity matrix, $\boldsymbol{\alpha} = (\alpha_{i})$ and $\alpha_{i}$ is a parameter, $i = 1, \cdots, n-1$.

In [5], Cui et al. considered the preconditioner with $P_{max} = I+S_{max}$, where $S_{max}$ was given by

where

Some results in ^[4,5] were given below.

Lemma 3.1. (^[4])Let $\mathcal{A}$ be a strong $\mathcal{M}$-tensor. If $\boldsymbol{\alpha} = (\alpha_{i})$ and $\alpha_{i}\in [0, 1], i = 1, 2, \cdots, n-1$, $\mathcal{A}_{\alpha} = P_{\boldsymbol{\alpha}}\mathcal{A} = \mathcal{E}_{\alpha}-\mathcal{F}_{\alpha}$ and $(\rho_{\boldsymbol{\alpha}}, \mathbf{x}_{\boldsymbol{\alpha}})$ is Perron eigenpair of $\mathcal{T}_{\boldsymbol{\alpha}} = M(\mathcal{E}_{\alpha})^{-1}\mathcal{F}_{\alpha}$, then $\mathcal{A}\mathbf{x}_{\boldsymbol{\alpha}}^{m-1}\geq 0$.

Lemma 3.2. (^[4])Let $\mathcal{A}\in\mathbb{R}^{[m, n]}$ and $\mathcal{A} = \mathcal{I}_{m}-\mathcal{L}-\mathcal{F}, \mathcal{F}\geq\mathcal{O}$, where $\mathcal{L} = L\mathcal{I}_{m}$, $-L$ is the strictly lower part of $M(\mathcal{A})$. If $\mathcal{A}$ is a strong $\mathcal{M}$-tensor, then for all $\alpha_{i}\in [0, 1], i = 1, \cdots, n-1$, $(I+S_{\alpha})\mathcal{A}$ is a strong $\mathcal{M}$-tensor.

Lemma 3.3. (^[5])Let $\mathcal{A}\in\mathbb{R}_{+}^{[m, n]}$. If $\mathcal{A}$ is a strong $\mathcal{M}$-tensor and $\mathcal{A} = \mathcal{I}_{m}-\mathcal{L}-\mathcal{F}$, where $\mathcal{L} = L\mathcal{I}_{m}$, $-L$ is the strictly lower triangle part of $M(\mathcal{A})$, then $\mathcal{A}_{max} = (I+S_{max})\mathcal{A}$ is a strong $\mathcal{M}$-tensor.

Lemma 3.4. (^[5], Lemma 3)Let $\mathcal{A}\in \mathbb{R}^{[m, n]}$ be a strong $\mathcal{M}$-tensor. For $\mathcal{A}_{max} = \mathcal{E}_{max}-\mathcal{F}_{max}$, we have the following inequality holds if

Theorem 3.1. (^[5], Theorem 4)Let $\mathcal{A}\in \mathbb{R}^{[m, n]}$ be a strong $\mathcal{M}$-tensor. For

and

under the conditions made in Lemma 3.4, there exists a positive vector $\mathbf{x}$ such that $0\leq\hat{\mathcal{A}}\mathbf{x}^{m-1}\leq\mathcal{A}_{max}\mathbf{x}^{m-1}$, then we have the following inequality holds

where $\mathcal{T}_{max} = M(\mathcal{E}_{max})^{-1}\mathcal{F}_{max}$ and $\hat{\mathcal{T}_{\alpha}} = M(\hat{\mathcal{E}_{\alpha}})^{-1}\hat{\mathcal{F}_{\alpha}}.$

We first consider a counter-example for Theorem 3.1.

Example 3.1. We consider a tensor $\mathcal{A}\in\mathbb{R}^{[3, 4]}$, where

It is easy to show that $\mathcal{A}$ is a strong $\mathcal{M}$-tensor and

From the above computation we can see that $M(\mathcal{E}_{max})^{-1}\geq M(\hat{\mathcal{E}_{\mathbf{1}}})^{-1}\geq 0$. That is, the tensor $\mathcal{A}$ satisfies the condition of the Lemma 3.4. But by computation, we have $\rho(\mathcal{T}_{max}) = 0.5896 > 0.5877 = \rho(\hat{\mathcal{T}_{\boldsymbol{\alpha}}})$. This contradicts the conclusion of the Theorem 3.1 in ^[5].

We next propose a new preconditioner $\tilde{P} = I+\tilde{S}$, where

where

Without loss of generality, we assume that each diagonal entry of the tensor $\mathcal{A}$ is 1. Let

where $\tilde{\mathcal{D}} = \tilde{D}\mathcal{I}_{m}, \tilde{\mathcal{L}} = \tilde{L}\mathcal{I}_{m}$, and $\tilde{D}, -\tilde{L}$ are the diagonal part, the strictly lower triangular part of $M(\tilde{\mathcal{A}})$. If $a_{i, i+1, \cdots, i+1}a_{i+1, i, \cdots, i}+a_{ik_{i}\cdots k_{i}}a_{k_{i}i\cdots i}\neq 1$, then $M(\tilde{\mathcal{D}}-\tilde{\mathcal{L}})^{-1}$ exists, we get the Gauss-Seidel type iteration tensor $\tilde{\mathcal{T}}$ can be defined by $M(\tilde{\mathcal{D}}-\tilde{\mathcal{L}})^{-1}\tilde{\mathcal{U}}$.

Lemma 3.5. Let $\mathcal{A}\in\mathbb{R}^{[m, n]}$ be a strong $\mathcal{M}$-tensor, then $\tilde{\mathcal{A}} = \tilde{P}\mathcal{A} = (I+\tilde{S})\mathcal{A}$ is a strong $\mathcal{M}$-tensor.

Proof. We first show that $\tilde{\mathcal{A}}$ is a $\mathcal{Z}$-tensor. Since

for $(i, i_{2}, \cdots, i_{m})\neq (i, i, \cdots, i)$, we have $\tilde{a}_{ii_{2}\cdots i_{m}}\leq 0$, that is, $\tilde{\mathcal{A}}$ is a $\mathcal{Z}$-tensor.

As $\mathcal{A}$ is a strong $\mathcal{M}$-tensor, from Lemma 2.2, there exists a positive vector $\mathbf{x}$ such that $\mathcal{A}\mathbf{x}^{m-1} > 0$. Thus, $\tilde{\mathcal{A}}\mathbf{x}^{m-1} = (I+\tilde{S})\mathcal{A}\mathbf{x}^{m-1} > 0$. That is to say, there exists a positive vector $\mathbf{x}$ such that $\tilde{\mathcal{A}}\mathbf{x}^{m-1} > 0$, Then from Lemma 2.2 again, we know that $\tilde{\mathcal{A}}$ is a strong $\mathcal{M}$-tensor.

Lemma 3.6. Let $\mathcal{A}\in\mathbb{R}^{[m, n]}$ be a strong $\mathcal{M}$-tensor, let

and

then

Proof. Let $\mathcal{A}_{max} = (a^{m}_{ii_{2}\cdots i_{m}})$ and $\tilde{\mathcal{A}} = (\tilde{a}_{ii_{2}\cdots i_{m}})$, we have

and $\tilde{a}_{ii_{2}\cdots i_{m}}$ is defined by (3.5). Since $\mathcal{A}$ is a strong $\mathcal{M}$-tensor, from Lemma 3.3 and Lemma 3.5, we know that $\mathcal{A}_{max}$ and $\tilde{\mathcal{A}}$ are strong $\mathcal{M}$-tensors. Thus we have $M(\mathcal{E}_{max})$ and $M(\tilde{\mathcal{E}})$ are nonsingular $\mathcal{M}$-matrices. Since

for $i = 1, \cdots, n-2$ and $\hat{a}_{ii_{2}\cdots i_{m}} = \tilde{a}_{ii_{2}\cdots i_{m}}$, for $i = n-1, n$, then we get $M(\tilde{\mathcal{E}})^{-1}\geq M(\mathcal{E}_{max})^{-1}$. The later inequality can be obtained from Lemma 3.4.

Theorem 3.2. Let $\mathcal{A}$ be a strong $\mathcal{M}$-tensor. For $\hat{\mathcal{A}}_{\mathbf{1}} = \mathcal{E}_{\mathbf{1}}-\mathcal{F}_{\mathbf{1}}$ and $\tilde{\mathcal{A}} = \tilde{\mathcal{E}}-\tilde{\mathcal{F}}$, let $\hat{\mathcal{T}_{\mathbf{1}}} = M(\mathcal{E}_{\mathbf{1}})^{-1}\mathcal{F}_{\mathbf{1}}$ and $\tilde{\mathcal{T}} = M(\tilde{\mathcal{E}})^{-1}\tilde{\mathcal{F}}$, then we have

Proof. From Lemma 3.1, we know there exists a positive Perron vector $\mathbf{x}$ of $\hat{\mathcal{T}_{\mathbf{1}}}$ such that $\mathcal{A}\mathbf{x}^{m-1}\geq \mathbf{0}$. Thus we have $\hat{\mathcal{A}}_{\mathbf{1}}\mathbf{x}^{m-1} = (I+\hat{S}_{\boldsymbol{1}})\mathcal{A}\mathbf{x}^{m-1}\geq\mathbf{0}$. Notice that

This means that $\tilde{\mathcal{A}}\mathbf{x}^{m-1}\geq\hat{\mathcal{A}}_{\mathbf{1}}\mathbf{x}^{m-1}\geq \mathbf{0}$. From Lemma 3.6, we have $M(\tilde{\mathcal{E}})^{-1}\geq M(\mathcal{E}_{\mathbf{1}})^{-1}\geq O$. Hence, we have

Since

Then, we obtain

By Lemma 2.1, we have $\rho(M(\tilde{\mathcal{E}})^{-1}\tilde{\mathcal{F}})\leq\rho(M(\mathcal{E}_{\mathbf{1}})^{-1}\mathcal{F}_{\mathbf{1}})$, i.e. $\rho(\tilde{\mathcal{T}})\leq\rho(\hat{\mathcal{T}_{\mathbf{1}}})$.

Remark 3.1. We consider the Example 3.1, it is easy to show that

That is, $M(\tilde{\mathcal{E}})^{-1}\geq M(\mathcal{E}_{\mathbf{1}})^{-1}$, by computation, we have $\rho(\hat{\mathcal{T}_{\mathbf{1}}}) = 0.5877$, and its corresponding Perron vector

Hence, according to Theorem 3.2, we have $\rho(\tilde{\mathcal{T}}) = 0.5816 < 0.5877 = \rho(\hat{\mathcal{T}_{\mathbf{1}}})$.

Theorem 3.3. Let $\mathcal{A}$ be a strong $\mathcal{M}$-tensor. For $\mathcal{A}_{max} = \mathcal{E}_{max}-\mathcal{F}_{max}$ and $\tilde{\mathcal{A}} = \tilde{\mathcal{E}}-\tilde{\mathcal{F}}$, let

and

If there exists a positive Perron vector $\mathbf{x}$ of $\mathcal{T}_{max}$ such as $\mathcal{A}\mathbf{x}^{m-1}\geq \mathbf{0}$. then we have

Proof. The proof is similar to those in Theorem 3.2, here we omit it.

Example 3.2. We consider the tensor $\mathcal{A}\in\mathbb{R}^{[3, 3]}$ in ^[5], where

We can show that $\mathcal{A}$ is a strong $\mathcal{M}$-tensor. Let $\alpha = (\alpha_{1}, \alpha_{2}) = (1, 1)$, we get:

From the above we can see that

By computation, we have

4.   Conclusions

In this paper, we present a new preconditioner $I+\tilde{S}$ for solving multi-linear sysyems and give new comparison results between two different preconditioned tensor splitting iterative methods. Comparison theorems show that the spectral radius of the proposed preconditioner is less than those of the preconditioners in ^[5]. We present two numerical experiments to validate the effectiveness of the proposed preconditioner.

Acknowledgments

The authors gratefully thank to the Referee for the constructive comments and recommendations which definitely help to improve the readability and quality of the paper. This work was supported by the Exploration project of Zhejiang Natural Science Foundation (No. LQ20G010004) and Ningbo Natural Science Foundation (No. 2021J179).

Conflict of interest

The authors declare that there are no conflicts of interest regarding the publication of this paper.