QQMR: A structure preserving quaternion quasi-minimal residual method

Li, Tao; Wang, Qing-Wen

doi:10.1090/mcom/4074

QQMR: A structure preserving quaternion quasi-minimal residual method
HTML articles powered by AMS MathViewer

by Tao Li and Qing-Wen Wang;

Math. Comp.

DOI: https://doi.org/10.1090/mcom/4074

Published electronically: February 10, 2025

HTML | PDF | Request permission

Abstract:

The quaternion biconjugate gradient (QBiCG) method, as a novel variant of quaternion Lanczos-type methods for solving the non-Hermitian quaternion linear systems, does not yield a minimization property. This means that the method possesses a rather irregular convergence behavior, which leads to numerical instability. In this paper, we propose a new structure-preserving quaternion quasi-minimal residual method based on the quaternion biconjugate orthonormalization procedure with coupled two-term recurrences, which overcomes the drawback of QBiCG. The computational cost and storage required by the proposed method are much less than the traditional QMR iterations for the real representation of quaternion linear systems. The convergence properties of which are also established. Finally, we report the numerical results to show the robustness and effectiveness of the proposed method compared with QBiCG.

References

William Rowan Hamilton, Elements of quaternions. Part 1, Cambridge Library Collection, Cambridge University Press, Cambridge, 2009. Reprint of the 1866 original; Previously published by Chelsea, New York, 1969 [MR0237284]; Edited by William Edwin Hamilton. MR 2884276, DOI 10.1017/CBO9780511707162
Fuzhen Zhang, Quaternions and matrices of quaternions, Linear Algebra Appl. 251 (1997), 21–57. MR 1421264, DOI 10.1016/0024-3795(95)00543-9
Leiba Rodman, Topics in quaternion linear algebra, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ, 2014. MR 3241695, DOI 10.1515/9781400852741
Liqun Qi, Ziyan Luo, Qing-Wen Wang, and Xinzhen Zhang, Quaternion matrix optimization: motivation and analysis, J. Optim. Theory Appl. 193 (2022), no. 1-3, 621–648. MR 4421890, DOI 10.1007/s10957-021-01906-y
Tongsong Jiang and Li Chen, An algebraic method for Schrödinger equations in quaternionic quantum mechanics, Comput. Phys. Comm. 178 (2008), no. 11, 795–799. MR 2672082, DOI 10.1016/j.cpc.2008.01.038
A. J. Davies, and B. H. J. McKellar, Observability of quantum mechanics, Phys. Rev. A 46 (1992), 3671–3675.
Özlem N. Subakan and Baba C. Vemuri, A quaternion framework for color image smoothing and segmentation, Int. J. Comput. Vis. 91 (2011), no. 3, 233–250. MR 2764520, DOI 10.1007/s11263-010-0388-9
Zhigang Jia, Michael K. Ng, and Guang-Jing Song, Robust quaternion matrix completion with applications to image inpainting, Numer. Linear Algebra Appl. 26 (2019), no. 4, e2245, 35. MR 3979957, DOI 10.1002/nla.2245
Zhigang Jia, Michael K. Ng, and Wei Wang, Color image restoration by saturation-value total variation, SIAM J. Imaging Sci. 12 (2019), no. 2, 972–1000. MR 3958767, DOI 10.1137/18M1230451
Y. Chen, Z. G. Jia, Y. Peng, Y. X. Peng, and D. Zhang, A new structure-preserving quaternion QR decomposition method for color image blind watermarking, Signal Process. 185 (2021), 108088.
Guangjing Song, Weiyang Ding, and Michael K. Ng, Low rank pure quaternion approximation for pure quaternion matrices, SIAM J. Matrix Anal. Appl. 42 (2021), no. 1, 58–82. MR 4199249, DOI 10.1137/19M1307329
Xin-Fang Zhang, Wei Ding, and Tao Li, Tensor form of GPBiCG algorithm for solving the generalized Sylvester quaternion tensor equations, J. Franklin Inst. 360 (2023), no. 9, 5929–5946. MR 4582093, DOI 10.1016/j.jfranklin.2023.04.009
D. Platnick, Quaternion calculus as a basic tool in computer graphics, Vis. Comput. 5 (1989), 2–13.
Yu Guan, Moody T. Chu, and Delin Chu, SVD-based algorithms for the best rank-1 approximation of a symmetric tensor, SIAM J. Matrix Anal. Appl. 39 (2018), no. 3, 1095–1115. MR 3820379, DOI 10.1137/17M1136699
Yu Guan and Delin Chu, Numerical computation for orthogonal low-rank approximation of tensors, SIAM J. Matrix Anal. Appl. 40 (2019), no. 3, 1047–1065. MR 4001760, DOI 10.1137/18M1208101
Steven H. Strogatz, Nonlinear dynamics and chaos, 2nd ed., Westview Press, Boulder, CO, 2015. With applications to physics, biology, chemistry, and engineering. MR 3837141
Zhigang Jia and Michael K. Ng, Structure preserving quaternion generalized minimal residual method, SIAM J. Matrix Anal. Appl. 42 (2021), no. 2, 616–634. MR 4245325, DOI 10.1137/20M133751X
Zhigang Jia, Musheng Wei, and Sitao Ling, A new structure-preserving method for quaternion Hermitian eigenvalue problems, J. Comput. Appl. Math. 239 (2013), 12–24. MR 2991955, DOI 10.1016/j.cam.2012.09.018
Zhigang Jia, Musheng Wei, Mei-Xiang Zhao, and Yong Chen, A new real structure-preserving quaternion QR algorithm, J. Comput. Appl. Math. 343 (2018), 26–48. MR 3813533, DOI 10.1016/j.cam.2018.04.019
Wenxv Ding, Zhihong Liu, Ying Li, Anli Wei, and Mingcui Zhang, New structure-preserving algorithms of Gauss-Seidel and successive over-relaxation iteration methods for quaternion linear systems, Numer. Algorithms 95 (2024), no. 3, 1309–1323. MR 4704803, DOI 10.1007/s11075-023-01609-7
S. T. Ling, Y. D. Li, B. Yang, and Z. G. Jia, Joint diagonalization for a pair of Hermitian quaternion matrices and applications to color face recognition, Signal Process. 198 (2022), 108560.
Qiaohua Liu, Sitao Ling, and Zhigang Jia, Randomized quaternion singular value decomposition for low-rank matrix approximation, SIAM J. Sci. Comput. 44 (2022), no. 2, A870–A900. MR 4410271, DOI 10.1137/21M1418319
Zhigang Jia, Michael K. Ng, and Guang-Jing Song, Lanczos method for large-scale quaternion singular value decomposition, Numer. Algorithms 82 (2019), no. 2, 699–717. MR 4003765, DOI 10.1007/s11075-018-0621-0
Marie Kubínová and Kirk M. Soodhalter, Admissible and attainable convergence behavior of block Arnoldi and GMRES, SIAM J. Matrix Anal. Appl. 41 (2020), no. 2, 464–486. MR 4083348, DOI 10.1137/19M1272469
Tao Li and Qing-Wen Wang, Structure preserving quaternion full orthogonalization method with applications, Numer. Linear Algebra Appl. 30 (2023), no. 5, Paper No. e2495, 15. MR 4637962, DOI 10.1002/nla.2495
Tao Li and Qing-Wen Wang, Structure preserving quaternion biconjugate gradient method, SIAM J. Matrix Anal. Appl. 45 (2024), no. 1, 306–326. MR 4695753, DOI 10.1137/23M1547299
Roland W. Freund and Noël M. Nachtigal, QMR: a quasi-minimal residual method for non-Hermitian linear systems, Numer. Math. 60 (1991), no. 3, 315–339. MR 1137197, DOI 10.1007/BF01385726
Roland W. Freund and Noël M. Nachtigal, An implementation of the QMR method based on coupled two-term recurrences, SIAM J. Sci. Comput. 15 (1994), no. 2, 313–337. Iterative methods in numerical linear algebra (Copper Mountain Resort, CO, 1992). MR 1261456, DOI 10.1137/0915022
Roland W. Freund and Manish Malhotra, A block QMR algorithm for non-Hermitian linear systems with multiple right-hand sides, Proceedings of the Fifth Conference of the International Linear Algebra Society (Atlanta, GA, 1995), 1997, pp. 119–157. MR 1436677, DOI 10.1016/S0024-3795(96)00529-0
Roland W. Freund and Florian Jarre, A QMR-based interior-point algorithm for solving linear programs, Math. Programming 76 (1997), no. 1, Ser. B, 183–210. Interior point methods in theory and practice (Iowa City, IA, 1994). MR 1426403, DOI 10.1016/S0025-5610(96)00039-1
Jianhua Zhang and Hua Dai, A new quasi-minimal residual method based on a biconjugate $A$-orthonormalization procedure and coupled two-term recurrences, Numer. Algorithms 70 (2015), no. 4, 875–896. MR 3428685, DOI 10.1007/s11075-015-9978-5
Cornelius Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Research Nat. Bur. Standards 45 (1950), 255–282. MR 42791, DOI 10.6028/jres.045.026
Riccardo Ghiloni, Valter Moretti, and Alessandro Perotti, Continuous slice functional calculus in quaternionic Hilbert spaces, Rev. Math. Phys. 25 (2013), no. 4, 1350006, 83. MR 3062919, DOI 10.1142/S0129055X13500062
Y. Saad, Krylov subspace methods for solving large unsymmetric linear systems, Math. Comp. 37 (1981), no. 155, 105–126. MR 616364, DOI 10.1090/S0025-5718-1981-0616364-6
Yousef Saad, Iterative methods for sparse linear systems, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003. MR 1990645, DOI 10.1137/1.9780898718003
Cornelius Lanczos, Solution of systems of linear equations by minimized-iterations, J. Research Nat. Bur. Standards 49 (1952), 33–53. MR 51583, DOI 10.6028/jres.049.006
Martin H. Gutknecht and Zdeněk Strakoš, Accuracy of two three-term and three two-term recurrences for Krylov space solvers, SIAM J. Matrix Anal. Appl. 22 (2000), no. 1, 213–229. MR 1779725, DOI 10.1137/S0895479897331862
Minghui Wang and Wenhao Ma, A structure-preserving method for the quaternion LU decomposition in quaternionic quantum theory, Comput. Phys. Commun. 184 (2013), no. 9, 2182–2186. MR 3107380, DOI 10.1016/j.cpc.2013.05.001
Ying Li, Musheng Wei, Fengxia Zhang, and Jianli Zhao, A real structure-preserving method for the quaternion LU decomposition, revisited, Calcolo 54 (2017), no. 4, 1553–1563. MR 3735827, DOI 10.1007/s10092-017-0241-4
H. M. Bücker and M. Sauren, A parallel version of the unsymmetric Lanczos algorithm and its application to QMR (no. FZJ-2015-01758), Z. Angew. Math. (1996).
Beresford N. Parlett, Derek R. Taylor, and Zhishun A. Liu, A look-ahead Lánczos algorithm for unsymmetric matrices, Math. Comp. 44 (1985), no. 169, 105–124. MR 771034, DOI 10.1090/S0025-5718-1985-0771034-2
X. Liu, Z. G. Jia, and X. Q. Jin, Flexible quaternion generalized minimal residual method for ill-posed quaternion inverse problems, Preprint arXiv:2408.03032, 2024.
Timothy A. Davis and Yifan Hu, The University of Florida sparse matrix collection, ACM Trans. Math. Software 38 (2011), no. 1, Art. 1, 25. MR 2865011, DOI 10.1145/2049662.2049663
Guanrong Chen and Tetsushi Ueta, Yet another chaotic attractor, Internat. J. Bifur. Chaos Appl. Sci. Engrg. 9 (1999), no. 7, 1465–1466. MR 1729683, DOI 10.1142/S0218127499001024
Tetsushi Ueta and Guanrong Chen, Bifurcation analysis of Chen’s equation, Internat. J. Bifur. Chaos Appl. Sci. Engrg. 10 (2000), no. 8, 1917–1931. MR 1787214, DOI 10.1142/S0218127400001183
Colin Sparrow, The Lorenz equations: bifurcations, chaos, and strange attractors, Applied Mathematical Sciences, vol. 41, Springer-Verlag, New York-Berlin, 1982. MR 681294, DOI 10.1007/978-1-4612-5767-7
Z. Wang, A. C. Bovik, and H. R. Sheikh, Image quality assessment: from error visibility to structural similarity, IEEE Trans. Image Process. 13 (2004), 600–612.
A. Bouhamidi, R. Enkhbat, and K. Jbilou, Conditional gradient Tikhonov method for a convex optimization problem in image restoration, J. Comput. Appl. Math. 255 (2014), 580–592. MR 3093444, DOI 10.1016/j.cam.2013.06.011
Jiao-fen Li, Wen Li, and Ru Huang, An efficient method for solving a matrix least squares problem over a matrix inequality constraint, Comput. Optim. Appl. 63 (2016), no. 2, 393–423. MR 3457446, DOI 10.1007/s10589-015-9783-z
A. R. Smith, Color gamut transform pairs, ACM Siggraph Comput. Graph. 12 (1978), 12–19.
A. R. Smith, Alpha and the history of digital compositing, Technical Memo 7, Microsoft Corporation, 1995.