A fast and oblivious matrix compression algorithm for Volterra integral operators
From MaRDI portal
(Redirected from Publication:824317)
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 time steps in complexity and only requiring 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 -matrix approximation of the underlying integral operator and, consequently, a further improvement can be achieved, in principle, by resorting to -matrix compression techniques. We formulate a variant of the -matrix vector product for discretized Volterra integral operators that can be performed in an evolutionary and oblivious manner and requires only operations and 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.
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
Cites work
- scientific article; zbMATH DE number 1405264 (Why is no real title available?)
- A Spectral Order Method for Inverting Sectorial Laplace Transforms
- A fast algorithm for particle simulations
- A kernel compression scheme for fractional differential equations
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- An improved Talbot method for numerical Laplace transform inversion
- Collocation Methods for Volterra Integral and Related Functional Differential Equations
- Convolution quadrature and discretized operational calculus. I
- Convolution quadrature and discretized operational calculus. II
- Convolution quadrature revisited
- Convolution quadrature time discretization of fractional diffusion-wave equations
- Dynamics of pattern formation in lateral-inhibition type neural fields
- Efficient numerical methods for non-local operators. \(\mathcal H^2\)-matrix compression, algorithms and analysis.
- Efficient representation of nonreflecting boundary conditions for the time‐dependent Schrödinger equation in two dimensions
- Fast Convolution for Nonreflecting Boundary Conditions
- Fast Numerical Solution of Nonlinear Volterra Convolution Equations
- Fast and Oblivious Convolution Quadrature
- Fast evaluation of nonreflecting boundary conditions for the Schrödinger equation in one dimension
- Hierarchical matrices: algorithms and analysis
- Multilevel approximation of boundary integral operators
- Multilevel matrix multiplication and fast solution of integral equations
- Multistep and Runge-Kutta convolution quadrature methods for coupled dynamical systems
- On the fast matrix multiplication in the boundary element method by panel clustering
- Rapid Evaluation of Nonreflecting Boundary Kernels for Time-Domain Wave Propagation
- Rapid solution of integral equations of classical potential theory
- Retarded potentials and time domain boundary integral equations. A road map
- Runge-Kutta Methods for Parabolic Equations and Convolution Quadrature
- The Accurate Numerical Inversion of Laplace Transforms
- The Laplace transform of analytic vector-valued functions (complex conditions)
- The black-box fast multipole method
- The random walk's guide to anomalous diffusion: A fractional dynamics approach
- Vector-valued Laplace transforms and Cauchy problems
- Volterra integral equations. An introduction to theory and applications
- Wavelet approximation methods for pseudodifferential equations. II: Matrix compression and fast solution
Cited in
(5)- Adaptive, Fast, and Oblivious Convolution in Evolution Equations with Memory
- A MATLAB code for fractional differential equations based on two-step spline collocation methods
- Well-posedness and simulation of weak solutions to the time-fractional Fokker-Planck equation with general forcing
- 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
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)
