Parallel-in-time preconditioner for the sinc-Nyström systems

DOI10.1137/21M1462696zbMATH Open1497.65156arXiv2108.01700OpenAlexW4291625223MaRDI QIDQ5097599FDOQ5097599

Authors: Jun Liu, Shulin Wu 

Publication date: 25 August 2022

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Abstract: The Sinc-Nystr"{o}m method is a high-order numerical method based on Sinc basis functions for discretizing evolutionary differential equations in time. But in this method we have to solve all the time steps in one-shot (i.e. all-at-once), which results in a large-scale nonsymmetric dense system that is expensive to handle. In this paper, we propose and analyze preconditioner for such dense system arising from both the parabolic and hyperbolic PDEs. The proposed preconditioner is a low-rank perturbation of the original matrix and has two advantages. First, we show that the eigenvalues of the preconditioned system are highly clustered with some uniform bounds which are independent of the mesh parameters. Second, the preconditioner can be used parallel for all the Sinc time points via a block diagonalization procedure. Such a parallel potential owes to the fact that the eigenvector matrix of the diagonalization is well conditioned. In particular, we show that the condition number of the eigenvector matrix only mildly grows as the number of Sinc time points increases, and thus the roundoff error arising from the diagonalization procedure is controllable. The effectiveness of our proposed PinT preconditioners is verified by the observed mesh-independent convergence rates of the preconditioned GMRES in reported numerical examples.

Full work available at URL: https://arxiv.org/abs/2108.01700

Recommendations

• Fast Iterative Methods for Sinc Systems
• Time-parallel iterative solvers for parabolic evolution equations
• scientific article; zbMATH DE number 2175080
• On preconditioned iterative methods for certain time-dependent partial differential equations
• The space-time Sinc-Gallerkin method for parabolic problems

zbMATH Keywords

diagonalizationGMRESKronecker product approximationparallel-in-time preconditionersinc-Nyström method

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Preconditioners for iterative methods (65F08) Iterative numerical methods for linear systems (65F10) Finite difference and finite volume methods for ordinary differential equations (65L12) Finite difference methods for initial value and initial-boundary value problems involving PDEs (65M06) Stability and convergence of numerical methods for initial value and initial-boundary value problems involving PDEs (65M12) Error bounds for initial value and initial-boundary value problems involving PDEs (65M15) Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs (65M55) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Cites Work

• A note on parallel preconditioning for all-at-once evolutionary PDEs
• Title not available (Why is that?)
• Title not available (Why is that?)
• GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
• A ``parareal in time discretization of PDE's
• Title not available (Why is that?)
• Fourth-Order Time-Stepping for Stiff PDEs
• Circulant and skew-circulant splitting methods for Toeplitz systems.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithm 866
• IFISS: A Computational Laboratory for Investigating Incompressible Flow Problems
• Eigenvalue perturbation theory of classes of structured matrices under generic structured rank one perturbations
• The role eigenvalues play in forming GMRES residual norms with non-normal matrices
• Any Nonincreasing Convergence Curve is Possible for GMRES
• Numerical solution of integral equations by means of the sinc collocation method based on the double exponential transformation
• Proof of Stenger's conjecture on matrix \(I^{(-1)}\) of sinc methods
• 50 years of time parallel time integration
• Applying GMRES to the Helmholtz equation with shifted Laplacian preconditioning: What is the largest shift for which wavenumber-independent convergence is guaranteed?
• Parallel time integration with multigrid
• Two Formulas for Numerical Indefinite Integration
• Accuracy enhancement using spectral postprocessing for differential equations and integral equations
• Error estimates with explicit constants for sinc approximation, sinc quadrature and sinc indefinite integration
• Implicit parallel time integrators
• Parallel multistep methods for linear evolution problems
• Preconditioning
• Parallelization in time through tensor-product space-time solvers
• Toward parallel coarse grid correction for the parareal algorithm
• Solving time-periodic fractional diffusion equations via diagonalization technique and multigrid.
• Preconditioning and Iterative Solution of All-at-Once Systems for Evolutionary Partial Differential Equations
• A Direct Time Parallel Solver by Diagonalization for the Wave Equation
• Time parallelization for nonlinear problems based on diagonalization
• Sinc-Nystrom Method for Numerical Solution of One-Dimensional Cauchy Singular Integral Equation Given on a Smooth Arc in the Complex Plane
• Spectral collocation in space and time for linear PDEs
• Theoretical analysis of sinc-Nyström methods for Volterra integral equations
• Theoretical analysis of sinc-collocation methods and sinc-Nyström methods for systems of initial value problems
• Domain decomposition preconditioning for the high-frequency time-harmonic Maxwell equations with absorption
• Sinc Nyström method for singularly perturbed Love's integral equation.
• Sinc-Nyström methods for Fredholm integral equations of the second kind over infinite intervals
• Convergence analysis of a \textit{periodic-like} waveform relaxation method for initial-value problems via the diagonalization technique
• A fast block \(\alpha\)-circulant preconditoner for all-at-once systems from wave equations
• Deferred correction methods for ordinary differential equations
• A parallel-in-time two-sided preconditioning for all-at-once system from a non-local evolutionary equation with weakly singular kernel
• A well-conditioned direct pint algorithm for first- and second-order evolutionary equations
• Space-time block preconditioning for incompressible flow
• Title not available (Why is that?)
• Optimal Complex Relaxation Parameters in Multigrid for Complex-Shifted Linear Systems
• Sinc–Nyström Method for Numerical Solution of a Dominant System of Cauchy Singular Integral Equations Given on a Piecewise Smooth Contour

Cited In (7)

• Fast parallel-in-time quasi-boundary value methods for backward heat conduction problems
• A note on parallel preconditioning for all-at-once evolutionary PDEs
• On preconditioned iterative methods for certain time-dependent partial differential equations
• A ROM-accelerated parallel-in-time preconditioner for solving all-at-once systems in unsteady convection-diffusion PDEs
• Title not available (Why is that?)
• Parallel solution methods and preconditioners for evolution equations
• A novel \(\alpha\)-absolute value preconditioner for all-at-once systems from heat equations

This page was built for publication: Parallel-in-time preconditioner for the sinc-Nyström systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5097599)