Arnoldi Method for Large Quaternion Right Eigenvalue Problem

Abstract

In this paper, we investigate the Arnoldi method of the right eigenvalue problem of the large-scale quaternion matrices. We use the real structure-preserving rather than the quaternion or the real structure, which has limitations in dealing with large quaternion matrices, to construct algorithms. The basic quaternion Arnoldi method is proposed to get the partial Schur decomposition of the quaternion matrices. Then, we give a novel algorithm for calculating the right eigenvectors of a quaternion Schur form. Furthermore, an explicitly restarted quaternion Arnoldi method (ERQAM) is presented to solve the right eigenpairs of the quaternion matrices. Finally, we provide five numerical examples which show the efficiency and accuracy of the proposed algorithms, and illustrate that the performance of ERQAM for large low rank quaternion matrices is better than that of the already known and brand-new methods.

Appendix A: Proof of Theorem 3.1

Let $\{\mathbf {q}_1,\ldots ,\mathbf {q}_j\}$ be the orthonormal basis of the Krylov subspace $\mathcal {K}_j(A,\mathbf {v})$, ($j \le s$). If $A^{j} \mathbf {v}\notin \mathcal {K}_j(A,\mathbf {v})$, then the vector $\mathbf {q}_{j+1}$ can be constructed by the Gram−Schmidt algorithm,

$$\begin{aligned} \mathbf {y}_j= & {} A^j \mathbf {v}-\sum ^{j}_{i=1}\mathbf {q}_i\langle \mathbf {q}_i,A^j \mathbf {v}\rangle ,\\ \mathbf {q}_{j+1}= & {} \mathbf {y}_j/\Vert \mathbf {y}_j\Vert _{\mathbb {H}}, \end{aligned}$$

where $\{\mathbf {q}_1,\ldots , \mathbf {q}_j,\mathbf {q}_{j+1}\}$ is a standard orthogonal basis of $\mathcal {K}_{j+1}(A,\mathbf {v})$. Let $\mathbf {q}_1=\mathbf {v}/\Vert \mathbf {v}\Vert _{\mathbb {H}}$ and $A\mathbf {q}_1=\mathbf {q}_1 d_1+\mathbf {q}_2 d_2, d_1, d_2 \in \mathbb {H}$. Then

$$\begin{aligned} \begin{aligned} \mathcal {K}_{j+1}(A,\mathbf {v})&=\text {span}_{\mathbb {H}}\{\mathbf {v},A\mathbf {v},\ldots ,A^{j} \mathbf {v}\} \\&=\text {span}_{\mathbb {H}}\{\mathbf {q}_1,A\mathbf {q}_1,A^2 \mathbf {q}_1,\ldots ,A^j \mathbf {q}_1\}\\&=\text {span}_{\mathbb {H}}\{\mathbf {q}_1,\mathbf {q}_1 d_1+\mathbf {q}_2 d_2,A(\mathbf {q}_1 d_1+\mathbf {q}_2 d_2),\ldots ,A^{j-1}(\mathbf {q}_1 d_1+\mathbf {q}_2 d_2)\}\\&=\text {span}_{\mathbb {H}}\{\mathbf {q}_1,\mathbf {q}_2,A\mathbf {q}_2,\ldots ,A^{j-1}\mathbf {q}_2\}\\&=\ldots \\&=\text {span}_{\mathbb {H}}\{\mathbf {q}_1,\mathbf {q}_2,\mathbf {q}_3,\ldots ,\mathbf {q}_j,A\mathbf {q}_j\} .\end{aligned} \end{aligned}$$

We replace $A^j \mathbf {v}$ with $A\mathbf {q}_j$ in the Gram−Schmidt orthogonalization process, and

$$\begin{aligned} \mathbf {u}_j=A\mathbf {q}_j-\sum ^{j}_{i=1}\mathbf {q}_i\langle \mathbf {q}_i,A\mathbf {q}_j\rangle . \end{aligned}$$

(A.1)

Since s is the minimum positive integer, and $\mathcal {K}_s(A,\mathbf {v})=\mathcal {K}_m(A,\mathbf {v})$ for every $m\ge s$. We have

$$\begin{aligned} \mathbf {u}_s=\mathbf {0} \ and\ \mathbf {u}_j\ne \mathbf {0} \ for\ every\ j<s. \end{aligned}$$

When $j<s$, we can continue to extend the standard orthogonal basis by the following formula,

$$\begin{aligned} \mathbf {q}_{j+1}=\mathbf {u}_j/\Vert \mathbf {u}_j\Vert _{\mathbb {H}}. \end{aligned}$$

It follows from $\mathbf {q}_{j+1} \perp \text {span}_{\mathbb {H}}\{\mathbf {q}_1,\ldots ,\mathbf {q}_j\}$ that

$$\begin{aligned} \begin{aligned} \langle \mathbf {q}_{j+1},\mathbf {u}_j\rangle&=\mathbf {q}_{j+1}^{*} \mathbf {u}_j\\&=\mathbf {q}_{j+1}^{*}A \mathbf {q}_j -\sum ^{j}_{i=1}\mathbf {q}_{j+1}^{*}\mathbf {q}_i\langle \mathbf {q}_i,A \mathbf {q}_j\rangle \\&=\mathbf {q}_{j+1}^{*}A \mathbf {q}_j\\&=\langle \mathbf {q}_{j+1},A\mathbf {q}_j\rangle ,\end{aligned} \end{aligned}$$

and

$$\begin{aligned} \mathbf {q}_{j+1}^{*}\mathbf {u}_j=\frac{\mathbf {u}_j^{*} \mathbf {u}_j}{\Vert \mathbf {u}_j\Vert _{\mathbb {H}}}=\frac{\langle \mathbf {u}_j,\mathbf {u}_j\rangle }{\Vert \mathbf {u}_j\Vert _{\mathbb {H}}}=\Vert \mathbf {u}_j\Vert _{\mathbb {H}}, \end{aligned}$$

implying

$$\begin{aligned} \Vert \mathbf {u}_j\Vert _{\mathbb {H}}=\mathbf {q}_{j+1}^{*}\mathbf {u}_j=\langle \mathbf {q}_{j+1},\mathbf {u}_j\rangle =\langle \mathbf {q}_{j+1},A\mathbf {q}_j\rangle . \end{aligned}$$

(A.2)

From (A.1), (A.2), we have

$$\begin{aligned} \begin{aligned} A\mathbf {q}_j&=\mathbf {u}_j+\sum ^{j}_{i=1}\mathbf {q}_i\langle \mathbf {q}_i,A\mathbf {q}_j\rangle \\&=\mathbf {q}_{j+1}\Vert \mathbf {u}_j\Vert _{\mathbb {H}} +\sum ^{j}_{i=1}\mathbf {q}_i\langle \mathbf {q}_i,A\mathbf {q}_j\rangle \\&=\mathbf {q}_{j+1}\langle \mathbf {q}_{j+1},\mathbf {u}_j\rangle +\sum ^{j}_{i=1}\mathbf {q}_i\langle \mathbf {q}_i,A\mathbf {q}_j\rangle \\&=\sum ^{j+1}_{i=1}\mathbf {q}_i\langle \mathbf {q}_i,A\mathbf {q}_j\rangle \\&=\sum ^{j+1}_{i=1}\mathbf {q}_i h_{ij}, \end{aligned} \end{aligned}$$

where $h_{ij}=\langle \mathbf {q}_i, A\mathbf {q}_j\rangle$$(1\le i \le j+1)$ and $h_{j+1,j}=\Vert \mathbf {u}_j\Vert _{\mathbb {H}} \in \mathbb {R}$. Then

$$\begin{aligned} A\mathbf {q}_j=\begin{pmatrix} \mathbf {q}_1&\mathbf {q}_2&\ldots&\mathbf {q}_j \end{pmatrix} \begin{pmatrix} h_{1j}\\ h_{2j}\\ \vdots \\ h_{jj} \end{pmatrix} +\mathbf {q}_{j+1}h_{j+1,j}, \end{aligned}$$

and,

$$\begin{aligned} \begin{aligned} AQ_k&=\begin{pmatrix} A\mathbf {q}_1&A\mathbf {q}_2&\ldots&A\mathbf {q}_k \end{pmatrix} \\&=\begin{pmatrix} \mathbf {q}_1&\mathbf {q}_2&\ldots&\mathbf {q}_k \end{pmatrix} \begin{pmatrix} h_{11}&{}h_{12} &{}h_{13}&{} \ldots &{} h_{1k}\\ h_{21}&{}h_{22}&{}h_{23}&{}\ldots &{} h_{2k}\\ 0 &{}h_{32}&{}\ldots &{}\ddots &{} h_{3k}\\ \vdots &{}\ddots &{}\ddots &{}\ddots &{}\vdots \\ 0&{}\ldots &{} 0&{}h_{k,k-1}&{}h_{kk} \end{pmatrix} +\begin{pmatrix} \mathbf {0}&\ldots&\mathbf {0}&\mathbf {q}_{k+1}h_{k+1,k} \end{pmatrix}\\&=Q_k H_k +\mathbf {q}_{k+1}h_{k+1,k}\mathbf {e}_{k}^{T}\\&=Q_{k+1} \tilde{H}_k, \end{aligned} \end{aligned}$$

where $Q_{k}^{*}Q_k=I_k$, and

$$\begin{aligned} \tilde{H}_k=\begin{pmatrix} H_k\\ h_{k+1,k}\mathbf {e}_{k}^{T} \end{pmatrix}=\begin{pmatrix} h_{11}&{}h_{12} &{}h_{13}&{} \ldots &{} h_{1k}\\ h_{21}&{}h_{22}&{}h_{23}&{}\ldots &{} h_{2k}\\ 0 &{}h_{32}&{}\ldots &{}\ddots &{} h_{3k}\\ \vdots &{}\ddots &{}\ddots &{}\ddots &{}\vdots \\ 0&{}\ldots &{} 0&{}h_{k,k-1}&{}h_{kk}\\ 0&{}\ldots &{}\ldots &{} 0 &{} h_{k+1,k} \end{pmatrix}. \end{aligned}$$

(A.3)