Registered Data

[02327] Stability of Numerical Linear Algebra Algorithms

  • Session Date & Time :
    • 02327 (1/2) : 3E (Aug.23, 17:40-19:20)
    • 02327 (2/2) : 4C (Aug.24, 13:20-15:00)
  • 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
  • Speakers Info :
    • Kensuke Aihara (Tokyo City University)
    • Froilán Martínez Dopico (Universidad Carlos III de Madrid)
    • Keiichi Morikuni (University of Tsukuba)
    • Theo Mary (Sorbonne Université)
    • Stephen Thomas (National Renewable Energy Laboratory)
    • Miroslav Rozložník (Czech Academy of Sciences)
    • Hassane Sadok (University of the Littoral Opal Coast)
    • Yusaku Yamamoto (The University of Electro-Communications)
  • Talks in Minisymposium :
    • [02706] Gauss-Seidel (MGS) - Jacobi (CGS) GMRES with Rank-1 Perturbation Smoothers
      • 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.
    • [02742] Cross-interactive residual smoothing for block Lanczos-type methods for solving linear systems with multiple right-hand sides
      • 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.
    • [02923] A projection method for singular eigenvalue problems of linear matrix pencils
      • 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.
    • [03008] Computing the matrix sign function with the double exponential formula
      • 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.
    • [03257] Backward stability in rational eigenvalue problems solved via linearization
      • 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.
    • [03899] Mixed Precision Strategies for Preconditioned Restarted GMRES
      • Author(s) :
        • Theo Mary (Sorbonne Université, CNRS, LIP6)
        • Alfredo Buttari (Université de Toulouse, CNRS, IRIT)
        • Nicholas J Higham (The University of Manchester)
        • Bastien Vieublé (The University of Manchester)
      • Abstract : The GMRES method, along with its flexible variants, is one of the most popular algorithms to solve large sparse linear systems. In its 40-year history, many different mixed precision strategies for GMRES have been proposed. Yet, there is no consensus on which of these strategies works best, nor even a good understanding of their numerical behavior. The goal of this work is to develop a systematic error analysis of (preconditioned, restarted, possibly flexible) GMRES in a framework as generic as possible, that encompasses existing strategies and reveals new opportunities.
    • [04236] Numerical stability of block classical Gram-Schmidt process
      • 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.
    • [05049] Improving convergence and stability of Krylov subspace methods for solving linear systems
      • 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.