On IOM(q): The Incomplete Orthogonalization Method for Large Unsymmetric Linear Systems
The author investigates the incomplete orthogonalization method (\(\text{IOM} (q)\)), a truncated version of the full orthogonalization method (FOM) for solving large unsymmetric systems of linear equations. The \(\text{IOM} (q)\) method is analysed from a theoretical point of view (in exact arithmetic). The paper studies the orthogonality of the basis vectors generated by the truncated Arnoldi orthogonalization process and the relationships between the residual norms of the \(\text{IOM} (q)\) and FOM methods are established. Theoretical results are illustrated by a number of numerical experiments. In the first part, the author describes the algorithms of the restarted FOM method and its truncated version without correction \(\text{IOM} (q)\) presented by \textit{Y. Saad} [Math. Comp. 37, 105-126 (1981; Zbl 0474.65019)]. Further, basic properties of the basis generated by the incomplete orthogonalization are investigated in detail. The author gives the bounds for the loss of orthogonality and for the singular values (linear independence) of the corresponding matrix with the basis vectors in terms of the departure of the system matrix from symmetry. It is shown that if the truncation parameter \(q\) is only by two vectors less than the restart parameter \(m\) then the \(\text{IOM} (q)\) method may generate a very (arbitrarily) ill-conditioned basis for the general unsymmetric system matrix \(A\). Note that in the symmetric case, the given analysis reduces to the well-known analysis of the properties of the symmetric Lanczos process. The second part of the paper is devoted to the analysis of convergence of the \(\text{IOM} (q)\) method. A relation between the residual norms of the FOM and \(\text{IOM} (q)\) in terms of the properties of the basis generated by the truncated orthogonalization process is derived. It is shown that if the linear independence of the computed basis is lost, then \(\text{IOM} (q)\) may not behave like FOM for a general unsymmetric matrix. In summary, \(\text{IOM} (q)\) may succeed in solving the system under some restrictions, but is possibly subject to failure, no matter how the trucation parameter \(q\) is chosen for general unsymmetric systems. Moreover, \(\text{IOM} (q)\) may not behave like FOM without some assumptions even if the system matrix is nearly symmetric. Due to the mathematical equivalence between \(\text{IOM} (q)\) and \(\text{ORTHORES}(q)\), the same results are valid also for the \(\text{ORTHORES}(q)\) method. Finally, assuming additional assumptions on the system matrix a possible strategy for choosing the truncation parameter \(q\) is discussed and theoretical results are illustrated on a series of numerical examples. Numerical experiments confirm that for the given class of real problems the restarted \(\text{IOM} (q)\) method is competitive with and is more efficient than the restarted FOM in most cases. This is especially true when the system is nearly symmetric and the upper Hessenberg matrix with the orthogonalization coefficients is nonsingular within the restart cycle of the iteration process.
- scientific article; zbMATH DE number 1735425
- On IGMRES: An incomplete generalized minimal residual method for large unsymmetric linear systems
- Some recursions on Arnoldi's method and IOM for large non-Hermitian linear systems
- A few results on Arnoldi's method and IOM for large non-Hermitian linear systems
- A class of incomplete orthogonal factorization methods. I: Methods and theories
- s-Step Iterative Methods for (Non)Symmetric (In)Definite Linear Systems
- A block incomplete orthogonalization method for large nonsymmetric eigenproblems
- A Comparison of Preconditioned Nonsymmetric Krylov Methods on a Large-Scale MIMD Machine
- A Completed Theory of the Unsymmetric Lanczos Process and Related Algorithms, Part I
- A Completed Theory of the Unsymmetric Lanczos Process and Related Algorithms. Part II
- A Hybrid GMRES Algorithm for Nonsymmetric Linear Systems
- A new look at the Lanczos algorithm for solving symmetric systems of linear equations
- A Robust GMRES-Based Adaptive Polynomial Preconditioning Algorithm for Nonsymmetric Linear Systems
- A Theoretical Comparison of the Arnoldi and GMRES Algorithms
- An efficient nonsymmetric Lanczos method on parallel vector computers
- Conjugate gradient type methods for unsymmetric and inconsistent systems of linear equations
- Generalized conjugate-gradient acceleration of nonsymmetrizable iterative methods
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- GMRESR: a family of nested GMRES methods
- scientific article; zbMATH DE number 3408799 (Why is no real title available?)
- Hybrid Krylov Methods for Nonlinear Systems of Equations
- Implementation of the GMRES Method Using Householder Transformations
- Iterative Solution of Linear Equations in ODE Codes
- Krylov Subspace Methods on Supercomputers
- Necessary and Sufficient Conditions for the Existence of a Conjugate Gradient Method
- Necessary and sufficient conditions for the simplification of generalized conjugate-gradient algorithms
- Orthogonal Error Methods
- Parallelizable restarted iterative methods for nonsymmetric linear systems. part I: Theory
- Practical Use of Some Krylov Subspace Methods for Solving Indefinite and Nonsymmetric Linear Systems
- QMR: A quasi-minimal residual method for non-Hermitian linear systems
- Reduction to Tridiagonal Form and Minimal Realizations
- Some History of the Conjugate Gradient and Lanczos Algorithms: 1948–1976
- The Lanczos Biorthogonalization Algorithm and Other Oblique Projection Methods for Solving Large Unsymmetric Systems
- The principle of minimized iterations in the solution of the matrix eigenvalue problem
- Variational Iterative Methods for Nonsymmetric Systems of Linear Equations
- Variations on Arnoldi's method for computing eigenelements of large unsymmetric matrices
- On IGMRES: An incomplete generalized minimal residual method for large unsymmetric linear systems
- Some recursions on Arnoldi's method and IOM for large non-Hermitian linear systems
- A few results on Arnoldi's method and IOM for large non-Hermitian linear systems
- Incomplete minimum joint backward perturbation methods for large unsymmetric linear systems
- scientific article; zbMATH DE number 4037031 (Why is no real title available?)
- scientific article; zbMATH DE number 4128300 (Why is no real title available?)
- The convergence of Krylov subspace methods for large unsymmetric linear systems
- scientific article; zbMATH DE number 1735425 (Why is no real title available?)
- Incompletely orthogonal variable restart parameter H-IGMRES (m) algorithm
This page was built for publication: On IOM(q): The Incomplete Orthogonalization Method for Large Unsymmetric Linear Systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4220444)
