×

Initial guesses for sequences of linear systems in a GPU-accelerated incompressible flow solver. (English) Zbl 07378161

Summary: We consider several methods for generating initial guesses when iteratively solving sequences of linear systems, showing that they can be implemented efficiently in GPU-accelerated PDE solvers, specifically solvers for incompressible flow. We propose new initial guess methods based on stabilized polynomial extrapolation and compare them to the projection method of Fischer [Comput. Methods Appl. Mech. Engrg., 163 (1998), pp. 193-204], showing that they are generally competitive with projection schemes despite requiring only half the storage and performing considerably less data movement and communication. Our implementations of these algorithms are freely available as part of the libParanumal collection of GPU-accelerated flow solvers.

MSC:

65F10 Iterative numerical methods for linear systems
65M22 Numerical solution of discretized equations for initial value and initial-boundary value problems involving PDEs

Software:

libParanumal; GitHub
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] gslib, Release 1.07, https://github.com/Nek5000/gslib, 2020.
[2] M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, Appl. Math. Ser. 55, National Bureau of Standards, 1968. · Zbl 0171.38503
[3] M. al Sayed Ali and M. Sadkane, Improved predictor schemes for large systems of linear ODEs, Electron. Trans. Numer. Anal., 39 (2012), pp. 253-270. · Zbl 1287.65055
[4] L. Bos, J.-P. Calvi, N. Levenberg, A. Sommariva, and M. Vianello, Geometric weakly admissible meshes, discrete least squares approximations and approximate Fekete points, Math. Comp., 80 (2011), pp. 1623-1638, https://doi.org/10.1090/s0025-5718-2011-02442-7. · Zbl 1228.41002
[5] L. Bos, S. De Marchi, A. Sommariva, and M. Vianello, Computing multivariate Fekete and Leja points by numerical linear algebra, SIAM J. Numer. Anal., 48 (2010), pp. 1984-1999, https://doi.org/10.1137/090779024. · Zbl 1221.41005
[6] J. P. Boyd and F. Xu, Divergence (Runge phenomenon) for least-squares polynomial approximation on an equispaced grid and mock-Chebyshev subset interpolation, Appl. Math. Comput., 210 (2009), pp. 158-168, https://doi.org/10.1016/j.amc.2008.12.087. · Zbl 1171.41004
[7] R. Brower, T. Ivanenko, A. Levi, and K. Orginos, Chronological inversion method for the Dirac matrix in hybrid Monte Carlo, Nucl. Phys. B, 484 (1997), pp. 353-374, https://doi.org/10.1016/s0550-3213(96)00579-2.
[8] N. Chalmers, A. Karakus, A. P. Austin, K. Swirydowicz, and T. Warburton, libParanumal: A Performance Portable High-Order Finite Element Library, Release 0.3.1, https://doi.org/10.5281/zenodo.4004744, 2020.
[9] N. Christensen, Efficient Projection Space Updates for the Approximation of Iterative Solutions to Linear Systems with Successive Right Hand Sides, M.S. thesis, University of Illinois at Urbana-Champaign, 2017, https://doi.org/2142/99410.
[10] M. Clemens, M. Wilke, R. Schuhmann, and T. Weiland, Subspace projection extrapolation scheme for transient field simulations, IEEE Trans. Magnetics, 40 (2004), pp. 934-937, https://doi.org/10.1109/tmag.2004.824583.
[11] M. Clemens, M. Wilke, and T. Weiland, Extrapolation strategies in numerical schemes for transient magnetic field simulations, IEEE Trans. Magnetics, 39 (2003), pp. 1171-1174, https://doi.org/10.1109/tmag.2003.810523.
[12] J. W. Daniel, W. B. Gragg, L. Kaufman, and G. W. Stewart, Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization, Math. Comp., 30 (1976), pp. 772-795, https://doi.org/10.1090/S0025-5718-1976-0431641-8. · Zbl 0345.65021
[13] L. Demanet and A. Townsend, Stable extrapolation of analytic functions, Found. Comput. Math., 19 (2018), pp. 297-331, https://doi.org/10.1007/s10208-018-9384-1. · Zbl 1410.41001
[14] M. O. Deville, P. F. Fischer, and E. H. Mund, High-Order Methods for Incompressible Fluid Flow, Cambridge University Press, Cambridge, UK, 2002. · Zbl 1007.76001
[15] P. Fischer, J. Lottes, D. Pointer, and A. Siegel, Petascale algorithms for reactor hydrodynamics, J. Phys. Conf. Ser., 125 (2008), 012076, https://doi.org/10.1088/1742-6596/125/1/012076.
[16] P. F. Fischer, Projection techniques for iterative solution of \(Ax = b\) with successive right-hand sides, Comput. Methods Appl. Mech. Engrg., 163 (1998), pp. 193-204, https://doi.org/10.1016/s0045-7825(98)00012-7. · Zbl 0960.76063
[17] R. Gandham, High Performance High-Order Numerical Methods: Applications in Ocean Modeling, Ph.D. thesis, Rice University, 2015.
[18] G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, Baltimore, 2013. · Zbl 1268.65037
[19] A. Greenbaum, Iterative Methods for Solving Linear Systems, SIAM, Philadelphia, 1997. · Zbl 0883.65022
[20] L. Grinberg and G. E. Karniadakis, Extrapolation-based acceleration of iterative solvers: Application to simulation of 3D flows, Commun. Comput. Phys., 9 (2011), pp. 607-626, https://doi.org/10.4208/cicp.301109.080410s. · Zbl 1364.52009
[21] J. M. Herbert and M. Head-Gordon, Accelerated, energy-conserving Born-Oppenheimer molecular dynamics via Fock matrix extrapolation, Phys. Chem. Chem. Phys., 7 (2005), p. 3269, https://doi.org/10.1039/b509494a.
[22] M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Stand., 49 (1952), pp. 409-436, https://doi.org/10.6028/jres.049.044. · Zbl 0048.09901
[23] D. C. Joyce, Survey of extrapolation processes in numerical analysis, SIAM Rev., 13 (1971), pp. 435-490, https://doi.org/10.1137/1013092. · Zbl 0229.65005
[24] A. Karakus, N. Chalmers, K. Świrydowicz, and T. Warburton, A GPU accelerated discontinuous Galerkin incompressible flow solver, J. Comput. Phys., 390 (2019), pp. 380-404, https://doi.org/10.1016/j.jcp.2019.04.010.
[25] G. E. Karniadakis and S. Sherwin, Spectral/hp Element Methods for Computational Fluid Dynamics, 2nd ed., Oxford University Press, Oxford, UK, 2005. · Zbl 1116.76002
[26] B. N. Parlett, The Symmetric Eigenvalue Problem, SIAM, Philadelphia, 1998. · Zbl 0885.65039
[27] G. Pitton and L. Heltai, Accelerating the iterative solution of convection-diffusion problems using singular value decomposition, Numer. Linear Algebra Appl., 26 (2018), pp. e2211 (1-24), https://doi.org/10.1002/nla.2211. · Zbl 1463.65075
[28] R. B. Platte, L. N. Trefethen, and A. B. Kuijlaars, Impossibility of fast stable approximation of analytic functions from equispaced samples, SIAM Rev., 53 (2011), pp. 308-318, https://doi.org/10.1137/090774707. · Zbl 1247.41001
[29] P. Pulay and G. Fogarasi, Fock matrix dynamics, Chem. Phys. Lett., 386 (2004), pp. 272-278, https://doi.org/10.1016/j.cplett.2004.01.069.
[30] E. A. Rakhmanov, Bounds for polynomials with a unit discrete norm, Ann. of Math. (2), 165 (2007), pp. 55-88, https://doi.org/10.4007/annals.2007.165.55. · Zbl 1124.41014
[31] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, Philadelphia, 2003. · Zbl 1031.65046
[32] Y. Saad and M. H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7 (1986), pp. 856-869, https://doi.org/10.1137/0907058. · Zbl 0599.65018
[33] K. S. Shterev, Iterative process acceleration of calculation of unsteady, viscous, compressible, and heat-conductive gas flows, Int. J. Numer. Methods Fluids, 77 (2015), pp. 108-122, https://doi.org/10.1002/fld.3979.
[34] A. Skarlatos, M. Clemens, and T. Weiland, Start vector generation for implicit Newmark time integration of the wave equation, IEEE Trans. Magnetics, 42 (2006), pp. 631-634, https://doi.org/10.1109/tmag.2006.872008.
[35] A. G. Tijhuis and P. M. Zwamborn, Marching on in anything: Solving electromagnetic field equations with a varying physical parameter, in Ultra-Wideband, Short-Pulse Electromagnetics 5, P. D. Smith and S. R. Cloude, eds., Kluwer Academic, New York, 2002, pp. 655-662, https://doi.org/10.1007/0-306-47948-6_78.
[36] L. N. Trefethen, Approximation Theory and Approximation Practice, SIAM, Philadelphia, 2013. · Zbl 1264.41001
[37] H. M. Tufo III, Algorithms for Large-Scale Parallel Simulation of Unsteady Incompressible Flows in Three-Dimensional Complex Geometries, Ph.D. thesis, Brown University, 1998.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.