Gl‐QFOM and Gl‐QGMRES: Two Efficient Algorithms for Quaternion Linear Systems With Multiple Right‐Hand Sides

Tao Li, Qing‐Wen Wang, Xin‐Fang ZhangNumerical 2025 · DOI

TL;DR

This paper introduces two novel algorithms, Gl-QFOM and Gl-QGMRES, for efficiently solving systems of linear equations with quaternion matrices, particularly those with multiple right-hand sides. These methods offer significant computational advantages over existing approaches by preserving the algebraic structure of quaternion matrices, leading to faster convergence and reduced memory usage, especially for large-scale problems like image restoration.

What Problem Does This Paper Address?

Solving linear systems of equations is a fundamental problem in many scientific and engineering disciplines. When these systems involve quaternion matrices (a number system extending complex numbers), the computational challenges increase due to the non-commutative nature of quaternion multiplication. Existing methods often convert these quaternion problems into larger real-valued systems, which can be computationally expensive and memory-intensive. This paper addresses the need for efficient, structure-preserving algorithms that can directly handle quaternion linear systems, especially those with multiple right-hand sides, which are common in applications like color image processing.

Methods

The core contribution of this paper is the development of two new algorithms: the Global Quaternion Full Orthogonalization (Gl-QFOM) and the Global Quaternion Generalized Minimum Residual (Gl-QGMRES) methods. These algorithms are built upon a novel Global Quaternion Arnoldi Procedure. This procedure is designed to preserve the "Hessenberg form" of quaternion matrices during the iterative process, which is crucial for maintaining computational efficiency and stability.

Key aspects of their approach include:

  • Quaternion Krylov Subspace: They define and utilize a quaternion matrix Krylov subspace, which is a fundamental concept in iterative linear system solvers.
  • Structure Preservation: A key innovation is the development of methods that "inherit the algebraic symmetry of the real counterpart" of the quaternion matrices. This means they avoid the costly conversion to larger real systems and instead work directly with the quaternion structure.
  • Global Orthogonalization and Oblique Projections: The Gl-QFOM and Gl-QGMRES methods employ global orthogonal and oblique projections, respectively, onto the quaternion Krylov subspace. This is a standard technique in numerical linear algebra for developing iterative solvers.
  • Practical Implementations: The paper provides detailed algorithms (Algorithm 4 and Algorithm 5) that are practical implementations of Gl-QFOM and Gl-QGMRES, respectively. These algorithms are designed to be computationally efficient, saving approximately three-quarters of the theoretical costs compared to methods that operate on the real representations.

Datasets

The paper uses several standard datasets for evaluation:

  • MatrixMarket Collection: Several matrices from the MatrixMarket collection (e.g., west0067, bcspwr03, bcsstk05, ibm32, ash85, pde225, can445) are used to test the algorithms on various sizes of quaternion linear systems.
  • Color Images: The algorithms are applied to color image restoration problems, using standard color images like "Lanhua," "Hongyi," "Peppers," and "Lena." These images are blurred using different types of blurring matrices (uniform blur and atmospheric turbulence blur) to simulate real-world image degradation.

Key Insights and Ideas

  • Quaternion Structure is Key: The non-commutative nature of quaternions presents unique challenges. The paper demonstrates that by developing algorithms that respect and preserve this structure, significant computational gains can be achieved.
  • Direct Quaternion Methods Outperform Real Counterparts: For solving quaternion linear systems, directly applying algorithms designed for quaternions (like Gl-QFOM and Gl-QGMRES) is demonstrably more efficient than converting the problem to a larger real-valued system and then applying standard algorithms.
  • Image Restoration Benefits: The application to color image restoration highlights the practical utility of these algorithms. They not only achieve comparable or better restoration quality but do so with significantly less computational time and fewer iterations.
  • Arnoldi Procedure Adaptation: The successful adaptation of the Arnoldi procedure to the quaternion setting is a crucial step, enabling the construction of the necessary Krylov subspaces.

Key Results

The paper presents numerical results that strongly support the effectiveness of the proposed Gl-QFOM and Gl-QGMRES methods.

  • Efficiency: In most cases, Algorithms 4 and 5 (Gl-QFOM and Gl-QGMRES) significantly outperform traditional methods like Gl-FOM and Gl-GMRES (when applied to the real representations) in terms of both elapsed CPU time and the number of iterations required to reach a desired accuracy. For instance, in Example 5.1, the proposed algorithms often required fewer iterations and less time.
  • Image Restoration Quality: For color image restoration tasks (Examples 5.3 and 5.4), the proposed algorithms consistently achieved higher PSNR (Peak Signal-to-Noise Ratio) and SSIM (Structural Similarity Index Measure) values, indicating better restoration quality.
  • Comparison: While both Gl-QFOM and Gl-QGMRES show strong performance, Algorithm 5 (Gl-QGMRES) sometimes exhibits slightly more reliable convergence behavior in terms of curves, though Algorithm 4 (Gl-QFOM) can be slightly faster.
  • Sylvester Equation: The paper also demonstrates the applicability of these methods to solving Sylvester quaternion matrix equations, showing their versatility.

Limitations and Future Work

  • Theoretical Convergence: While numerical results are provided, the paper mentions that theoretical convergence analysis for the Sylvester equation is not presented.
  • Preconditioning: The authors suggest that future work could involve developing preconditioned versions of Gl-QFOM and Gl-QGMRES. Preconditioning is a common technique to further accelerate the convergence of iterative solvers, especially for ill-conditioned systems.
  • Broader Applications: The paper focuses on linear systems and Sylvester equations. Future research could explore the application of these quaternion algorithms to other types of quaternion matrix problems or in different application domains.

Summary updated

Abstract

ABSTRACT In this paper, we propose the global quaternion full orthogonalization (Gl‐QFOM) and global quaternion generalized minimum residual (Gl‐QGMRES) methods, which are built upon global orthogonal and oblique projections onto a quaternion matrix Krylov subspace for solving quaternion linear systems with multiple right‐hand sides. We first develop the global quaternion Arnoldi procedure to preserve the quaternion Hessenberg form during the iterations. We then establish the convergence analysis of the proposed methods and show how to apply them to solve the Sylvester quaternion matrix equation. Numerical examples are provided to illustrate the effectiveness of our methods compared with the traditional Gl‐FOM and Gl‐GMRES iterations for the real representations of the original linear systems.
BibTeX
@inproceedings{li2025glqfom,
  author = {Tao Li and Qing‐Wen Wang and Xin‐Fang Zhang},
  title = {{Gl‐QFOM and Gl‐QGMRES: Two Efficient Algorithms for Quaternion Linear Systems With Multiple Right‐Hand Sides}},
  booktitle = {Numerical},
  year = {2025},
  doi = {10.1002/nla.70008},
}
Figure