Abstract:
For difficult problems, in our context, problems on highly deformed meshes, the Conjugate Gradient (CG) method may converge slowly, because the linear system is very poorly conditioned, and expensive preconditioners are needed. To reduce the runtime cost, we can accelerate the convergence and sometimes improve the initial guess by `recycling' search spaces from previous linear systems solves, that is, selecting and reusing appropriate subspaces to increase the rate of convergence. However, recycling CG is expensive memory-wise, as we store a basis for the recycle space and typically also for its image under the matrix, as well as a window of CG search direction vectors to periodically update/improve the recycle space for the next linear system. On the graphic processing unit, fast memory is quite limited, and data movement is expensive. So, to reduce the memory footprint, we store all these vectors in single precision and we avoid the image of the recycle space at the cost of an extra matrix-vector product. However, this may make it difficult to converge to high accuracy (double precision accuracy). We show that this can be fixed by doing the recycling projection twice but only for a few early iterations.
This presentation brings together an interesting blend of CG and high-performance computing related topics, demonstrating how well-known algorithms need to be adapted for high performance architectures. We discuss a convergence result for CG when `recycling' an approximate invariant subspace in a sequence of linear systems and demonstrate that the convergence is not sensitive to small perturbations (such as storing the basis vectors for the space in single precision). We also discuss how to solve to double precision accuracy while using single precision intermediate results and vectors stored in single precision without iterative refinement.
Speaker’s Bio:
Eric de Sturler is a Professor of Mathematics at Virginia Tech as well as a Professor in the Computational Modeling and Data Analytics program. He was head of the Department of Mathematics from August 2018 until August 2022. Previously, he was a Professor of Computer Science at the University of Illinois at Urbana-Champaign and a senior research scientist at the Interdisciplinary Project Center for Supercomputing at the Swiss Federal Institute of Technology, Zurich (ETH Zurich). He is a Leslie Fox prizewinner. He has served as an editor for multiple journals, among others, for Applied Numerical Mathematics and for the Society for Industrial and Applied Mathematics (SIAM) Journal on Numerical Analysis, and he was the Program Director of the SIAM Activity Group on Supercomputing from 2003 to 2006. He co-chaired the 3rd SIAM Conference on Computational Science and Engineering and the 13th Institute of Electrical and Electronics Engineers (IEEE) International Conference on Computational Science and Engineering. He served on the Board of Directors of the Computing Research Association from 2014 to 2022. Professor de Sturler's research focuses on numerical analysis for large-scale computational problems with an emphasis on fast solvers for linear and nonlinear systems, inverse problems and parameter estimation, optimization and design, and high-performance computing with applications in computational mechanics, such structural optimization and computational fluid dynamics, tomography and image reconstruction, big data, computational physics, biology, and computer graphics. His research has been supported by major grants from the National Science Foundation, the U.S. Department of Energy, the National Aeronautics and Space Administration, the Air Force Office of Science Research, and Sandia National Labs.
