Registered Data
[02327] Stability of Numerical Linear Algebra Algorithms
- Session Time & Room :
- Type : Proposal of Minisymposium
- Abstract : The stability of numerical linear algebra algorithms is a key component in large-scale and delicate computations such as solutions of linear systems of equations, eigenvalue problems, and matrix function computations. These computations in common require efficient but stable orthogonalization techniques. Understanding their numerical behaviors is thus equally important as their parallel efficiency. Recent low-synchronization and mixed-precision algorithms do improve parallel scaling while maintaining numerical stability when using next-generation high-performance computers. This minisymposium will foster interactions between new results of error analyses and new algorithmic innovations, and so will contribute to communication inside and beyond these two communities.
- Organizer(s) : Keiichi Morikuni, Miroslav Rozložník
- Classification : 65F10, 65F25, 65F60, 65F35, 65Y05
- Minisymposium Program :
- 02327 (1/2) : 3E @E508 [Chair: Keiichi Morikuni]
- [02923] A projection method for singular eigenvalue problems of linear matrix pencils
- Format : Talk at Waseda University
- Author(s) :
- Keiichi Morikuni (University of Tsukuba)
- Akira Imakura (University of Tsukuba)
- Abstract : Complex moments consisting of matrix resolvents filter out undesired eigencomponents and extract the desired ones from a pseudo-random matrix. This study extends a projection method using complex moments for regular eigenproblems to the singular nonsquare case. We establish conditions such that the method gives all finite eigenvalues in a prescribed region in the complex plane and the corresponding eigenvectors. Numerical experiments show that the new method is more robust and efficient than previous methods.
- [03257] Backward stability in rational eigenvalue problems solved via linearization
- Format : Talk at Waseda University
- Author(s) :
- Froilán Martínez Dopico (Universidad Carlos III de Madrid)
- María del Carmen Quintana (Aalto University )
- Paul Van Dooren (Université catholique de Louvain)
- Abstract : The numerical solution of nonlinear eigenvalue problems has attracted a lot of attention from the Numerical Linear Algebra community in the last twenty years. Among these problems, rational eigenvalue problems are particularly relevant because they appear directly in many applications and because they are often used to approximate other more general nonlinear eigenvalue problems. One of the most reliable methods for solving numerically rational eigenvalue problems is via linearizations. In this talk we present recent results on the backward stability of this approach.
- [03008] Computing the matrix sign function with the double exponential formula
- Format : Talk at Waseda University
- Author(s) :
- Tomoya Miyashita (The University of Electro-Communications)
- Shuhei Kudo (The University of Electro-Communications)
- Yusaku Yamamoto (The University of Electro-Communications)
- Abstract : Matrix sign function plays an important role in many scientific computations. There are various methods for computing the matrix sign function, such as Newton’s method, the Schur method, and methods based on integral representation. Among them, the integral-based methods are suitable for parallelization because the calculation at each sample point is independent. In this talk, we focus on the integral-based method using the double exponential (DE) formula recently proposed by Nakaya and Tanaka and evaluate its numerical accuracy and parallel performance on the Fugaku computer. We also show a new theoretical upper bound on its discretization and truncation errors.
- 02327 (2/2) : 4C @E508 [Chair: Miroslav Rozložník]
- [04236] Numerical stability of block classical Gram-Schmidt process
- Format : Talk at Waseda University
- Author(s) :
- Miroslav Rozloznik (Czech Academy of Sciences)
- Erin Claire Carson (Charles University)
- Kathryn Lund (Charles University)
- Abstract : The block version of the classical Gram--Schmidt (BCGS) method is often employed to efficiently compute orthogonal bases for Krylov subspace methods and eigenvalue solvers, but a rigorous proof of its stability behavior has not yet been established. It is shown that the usual implementation of BCGS can lose orthogonality at a rate worse than $O(\varepsilon) \kappa^{2}(X)$, where $X$ is the input matrix and $\varepsilon$ is the unit roundoff. A useful intermediate quantity denoted as the Cholesky residual is given special attention and, along with a block generalization of the Pythagorean theorem, this quantity is used to develop more stable variants of BCGS. These variants are proven to have at most $O(\varepsilon) \kappa^2(X)$ loss of orthogonality with relatively relaxed conditions on the intrablock orthogonalization routine satisfied by the most commonly used algorithms. A variety of numerical examples illustrate the theoretical bounds.
- [02742] Cross-interactive residual smoothing for block Lanczos-type methods for solving linear systems with multiple right-hand sides
- Format : Talk at Waseda University
- Author(s) :
- Kensuke Aihara (Tokyo City University)
- Akira Imakura (University of Tsukuba)
- Keiichi Morikuni (University of Tsukuba)
- Abstract : Block Lanczos-type methods often exhibit large oscillations in the residual norms, leading to a large residual gap and a loss of attainable accuracy of the approximations. Cross-interactive residual smoothing $(\text{CIRS})$ was recently developed for the standard/global Lanczos-type methods to obtain smooth convergence behavior and reduce the residual gap. We therefore extend CIRS to the block version. Rounding error analysis and numerical experiments demonstrate the effectiveness of the presented approach.
- [02706] Gauss-Seidel (MGS) - Jacobi (CGS) GMRES with Rank-1 Perturbation Smoothers
- Format : Online Talk on Zoom
- Author(s) :
- Stephen Thomas (Advanced Micro Devices)
- Miro Rozloznik (Czech Academy of Science)
- Erin Carson (Charles University)
- Abstract : We introduce a low-synch GMRES algorithm based on Gauss-Seidel (MGS) and Jacobi (CGS) iterations. The correction matrix $T = (I + L)^{-1}$ for the projector $P = I - QTQ^T$ is a rank-1 perturbation, and results in low backward error. These ideas are applied to AMG. The smoother performs a triangular solve and subsequent iterations apply Jacobi or $(I - uv^T)r_k$, $u = L_{k,1:k-1}$ and $v = e_k$. GMRES convergence remains the same with this iterative refinement.
- [05049] Improving convergence and stability of Krylov subspace methods for solving linear systems
- Format : Talk at Waseda University
- Author(s) :
- hassane sadok (université du Littoral Cote d OPale)
- Abstract : Krylov subspace methods are widely used for the iterative solution of a large variety of linear systems of equations with one or several right hand sides or for solving nonsymmetric eigenvalue problems.
The purpose of this talk is to compare several variants of the implementation of Krylov subspace methods, including GMRES, QMR, and CMRH methods. These schemes are based on the two-sided Gram-Schmidt process methods and differ in their use of the inner product \(
\) where \(P=I- C C^+\) is a projector. We provide a unified description of the methods discussed and derive new expressions and bounds for the residual errors.