A fast and oblivious matrix compression algorithm for Volterra integral operators

DOI10.1007/S10444-021-09902-6zbMATH Open1483.65071arXiv2103.12834OpenAlexW3208376128MaRDI QIDQ824317FDOQ824317

Authors: Jürgen Dölz, Herbert Egger, Vsevolod Shashkov 

Publication date: 15 December 2021

Published in: Advances in Computational Mathematics (Search for Journal in Brave)

Abstract: The numerical solution of dynamical systems with memory requires the efficient evaluation of Volterra integral operators in an evolutionary manner. After appropriate discretisation, the basic problem can be represented as a matrix-vector product with a lower diagonal but densely populated matrix. For typical applications, like fractional diffusion or large scale dynamical systems with delay, the memory cost for storing the matrix approximations and complete history of the data then would become prohibitive for an accurate numerical approximation. For Volterra-integral operators of convolution type, the emph{fast and oblivious convolution quadrature} method of Sch"adle, Lopez-Fernandez, and Lubich allows to compute the discretized valuation with $N$ time steps in $O(NlogN)$ complexity and only requiring $O(logN)$ active memory to store a compressed version of the complete history of the data. We will show that this algorithm can be interpreted as an $mathcalH$-matrix approximation of the underlying integral operator and, consequently, a further improvement can be achieved, in principle, by resorting to $mathcal{H}^2$-matrix compression techniques. We formulate a variant of the $mathcal{H}^2$-matrix vector product for discretized Volterra integral operators that can be performed in an evolutionary and oblivious manner and requires only $O(N)$ operations and $O(logN)$ active memory. In addition to the acceleration, more general asymptotically smooth kernels can be treated and the algorithm does not require a-priori knowledge of the number of time steps. The efficiency of the proposed method is demonstrated by application to some typical test problems.

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

Recommendations

• On the design of deterministic matrices for fast recovery of Fourier compressible functions
• Compression Techniques for Boundary Integral Equations---Asymptotically Optimal Complexity Estimates
• On the Compression of Low Rank Matrices
• \(\mathcal{H}^2\)-matrix compression
• Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition
• Sparse discretization matrices for Volterra integral operators with applications to numerical differentiation
• Efficient numerical methods for non-local operators. \(\mathcal H^2\)-matrix compression, algorithms and analysis.
• A practical method for compressing sparse matrices with variant entries
• Exploiting compression in solving discretized linear systems
• Chebyshev-like compression of linear and nonlinear discretized integral operators

zbMATH Keywords

matrix compressionconvolution quadratureVolterra integral operators\(\mathscr{H}^2\)-matrices

Mathematics Subject Classification ID

Numerical linear algebra (65F99) Integral operators (45P05)

Cites Work

• Efficient numerical methods for non-local operators. \(\mathcal H^2\)-matrix compression, algorithms and analysis.
• A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
• A fast algorithm for particle simulations
• Collocation Methods for Volterra Integral and Related Functional Differential Equations
• The random walk's guide to anomalous diffusion: A fractional dynamics approach
• Convolution quadrature and discretized operational calculus. I
• Dynamics of pattern formation in lateral-inhibition type neural fields
• Vector-valued Laplace transforms and Cauchy problems
• Convolution quadrature time discretization of fractional diffusion-wave equations
• Runge-Kutta Methods for Parabolic Equations and Convolution Quadrature
• On the fast matrix multiplication in the boundary element method by panel clustering
• Convolution quadrature and discretized operational calculus. II
• Convolution quadrature revisited
• Wavelet approximation methods for pseudodifferential equations. II: Matrix compression and fast solution
• Hierarchical matrices: algorithms and analysis
• Title not available (Why is that?)
• A Spectral Order Method for Inverting Sectorial Laplace Transforms
• The Accurate Numerical Inversion of Laplace Transforms
• Rapid solution of integral equations of classical potential theory
• Multilevel matrix multiplication and fast solution of integral equations
• The black-box fast multipole method
• Fast Convolution for Nonreflecting Boundary Conditions
• Efficient representation of nonreflecting boundary conditions for the time‐dependent Schrödinger equation in two dimensions
• Fast and Oblivious Convolution Quadrature
• Fast Numerical Solution of Nonlinear Volterra Convolution Equations
• Multilevel approximation of boundary integral operators
• Rapid Evaluation of Nonreflecting Boundary Kernels for Time-Domain Wave Propagation
• Fast evaluation of nonreflecting boundary conditions for the Schrödinger equation in one dimension
• Volterra integral equations. An introduction to theory and applications
• Retarded potentials and time domain boundary integral equations. A road map
• A kernel compression scheme for fractional differential equations
• Multistep and Runge-Kutta convolution quadrature methods for coupled dynamical systems
• An improved Talbot method for numerical Laplace transform inversion
• The Laplace transform of analytic vector-valued functions (complex conditions)

Cited In (5)

• A fast, high-order numerical method for the simulation of single-excitation states in quantum optics
• A fast time domain solver for the equilibrium Dyson equation
• Adaptive, Fast, and Oblivious Convolution in Evolution Equations with Memory
• Well-posedness and simulation of weak solutions to the time-fractional Fokker-Planck equation with general forcing
• A MATLAB code for fractional differential equations based on two-step spline collocation methods

This page was built for publication: A fast and oblivious matrix compression algorithm for Volterra integral operators

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