The paper presents a generalized block version of the Induced Dimension Reduction (IDR) methods in comparison with the Multi–Preconditioned Semi-Conjugate Direction (MPSCD) algorithms in Krylov subspaces with deflation and low-rank matrix approximation. General and individual orthogonality and variational properties of these two methodologies are analyzed. It is demonstrated, in particular, that for any sequence of Krylov subspaces with increasing dimensions there exists a sequence of the corresponding shrinking subspaces with decreasing dimensions. The main conclusion is that the IDR procedures, proposed by P. Sonneveld and other authors, are not an alternative to but a further development of the general principles of iterative processes in Krylov subspaces.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
P. Wesseling and P. Sonneveld, “Numerical experiments with a multiple grid and a preconditioned Lanczos type method,” Lect. Notes Math., 771, 543–562 (1980).
P. Sonneveld and M. B. Van Gijzen, “IDR(s): a family of simple and fast algorithms for solving large nonsymmetric systems of linear equations,” SIAM J. Sci. Comput., 31, No. 2, 1035–1062 (2008/09).
M. H. Gutknecht, “IDR explained,” Electron. Trans. Numer. Anal., 36, 126–148 (2009/10).
Y. Onoue, S. Fujino, and N. Nakashima, “An overview of a family of new iterative methods based on IDR theorem and its estimation,” in: Proceedings of the International Multi-Conference of Engineers and Computer Scientists, 2009, Vol. 11, IMECS, Hong Kong (2009), pp. 2129–2134.
V. Simoncini and D. B. Szyld, “Interpreting IDR as a Petrov–Galerkin method,” SIAM J. Sci. Comput., 32, No. 4, 1898–1912 (2010).
M. Tanio and M. Sugihara, “GBi-CGSTAB(s,l): IDR(s) with higher-order stabilization polynomials,” J. Comput. Appl. Math., 235, No. 3, 765–784 (2010).
G. L. Sleijpen, P. Sonneveld, and M. B. Van Gijzen, “Bi-CGStab as an induced dimension reduction method,” Appl. Numer. Math., 60, No. 11, 1100–1114 (2010).
G. L. Sleijpen and M. B. Van Gijzen, “Exploiting BiCGStab(l) strategies to induce dimension reduction,” SIAM J. Sci. Comput., 32 (5), 2687–2709 (2010).
P. Sonneveld, “On the convergence behavior of IDR(s) and related methods,” SIAM J. Sci. Comput., 34 (5), 2576–2598 (2012).
Y. Saad, Iterative Methods for Sparse Linear Systems (Second edition), Society for Industrial and Applied Mathematics (2003).
V. P. Il’in, Methods and Technologies of Finite Elements [in Russian], Izd. IVMiMG SO RAN, Novosibirsk (2007).
G. L. Sleijpen and D. R. Fokkema, “BiCGStab(l) for linear equations involving unsymmetric matrices with complex spectrum,” Electron. Trans. Numer. Anal., 1, 11–32 (1993).
V. P. Il’in, “Biconjugate direction methods in Krylov subspaces,” Sib. Zh. Ind. Mat., 11, No. 4, 47–60 (2008).
M. B. Van Gijzen, G. I. Sleijpen, and J. -P. Zemke, “Flexible and multi-shift induced dimension reduction algorithms for solving large sparse linear systems,” Numer. Linear Algebra Appl., 22, 1–25 (2014).
M. B. Van Gijzen and P. Sonneveld, “Algorithm 913: an elegant IDR(s) variant that efficiently exploits biorthogonality properties,” ACM Trans. Math. Software, 38, No. 1, 5.1–5.19 (2011).
O. Rendel, A. Rizvanolli, and J.-P. Zemke, “IDR: A new generation of Krylov subspace methods,” Linear Algebra Appl., 439, No. 4, 1040–1061 (2013).
R. Astudillo and M. B. Van Gijzen, “A restarted induced dimension reduction method to approximate eigenpairs of large unsymmetric matrices,” J. Comput. Appl. Math., 296, 24–35 (2016).
V. P. Il’in, “Methods of semiconjugate directions,” Russ. J. Numer. Anal. Math. Model., 23, No. 4, 369–387 (2008).
V. P. Il’in and E. A. Itskovich, “On the semi-conjugate direction methods with dynamic preconditioning,” J. Appl. Ind. Math., 3, No. 2, 222–233 (2009).
S. C. Eisenstat, H. C. Elman, and M. H. Schultz, “Variational iterative methods for nonsymmetric systems of linear equations,” SIAM J. Numer. Anal., 20, No. 3, 345–357 (1983).
J. Y. Yuan, G. H. Golub, R. J. Plemmons, and W. A. Cecilio, “Semi-conjugate direction methods for real positive definite systems,” BIT, 44, No. 1, 189–207 (2004).
R. Nicolaides, “Deflation of conjugate gradients with applications to boundary value problems,” SIAM J. Numer. Anal., 24, 355–365 (1987).
L. Yu. Kolotilina, “Twofold deflation preconditioning of linear algebraic systems. I. Theory,” Zap. Nauchn. Semin. POMI, 229, 95–152 (1995).
O. Coulaud, L. Giraud, P. Ramet, and X. Vasseur, Deflation and augmentation techniques in Krylov subspace methods for the solution of linear systems, INRIA, Bordeaux-Sud Ouest, France, Res. Rep. No. 8265 (2013).
M. H. Gutknecht, “Deflated and augmented Krylov subspace methods: A framework for deflated BICG and related solvers,” SIAM J. Matrix Anal. Appl., 35, No. 4, 1444–1466 (2014).
Y. L. Gurieva and V. P. Il’in, “Parallel approaches and technologies of domain decomposition methods,” Zap. Nauchn. Semin. POMI, 428, 89–106 (2014).
V. P. Il’in, “Problems of parallel solution of large systems of linear algebraic equations,” Zap. Nauchn. Semin. POMI, 439, 112–127 (2015).
R. Bridson and C. Greif, “A multipreconditioned conjugate gradient algorithm,” SIAM J. Matrix Anal. Appl., 27, No. 4, 1056–1068 (2006).
C. L. Lawson and R. J. Hanson, Solving Least Squares Problems [Russian translation], Nauka, Moscow (1986).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 453, 2016, pp. 114–130.
Rights and permissions
About this article
Cite this article
Il’in, V.P. Iterative Processes in the Krylov–Sonneveld Subspaces. J Math Sci 224, 890–899 (2017). https://doi.org/10.1007/s10958-017-3459-4
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10958-017-3459-4