Superfast solution of linear convolutional Volterra equations using QTT approximation

We address a linear fractional differential equation and develop effective solution methods using algorithms for the inversion of triangular Toeplitz matrices and the recently proposed QTT format. The inverses of such matrices can be computed by the divide and conquer and modified Bini’s algorithms,...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computational and applied mathematics 2014-04, Vol.260, p.434-448
Main Authors: Roberts, Jason A., Savostyanov, Dmitry V., Tyrtyshnikov, Eugene E.
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Computation
Divide and conquer
Fast convolution
Format
Fractional calculus
Inversions
Mathematical analysis
Mathematical models
Matrices (mathematics)
Superfast Fourier transform
Tensor train format
Triangular Toeplitz matrix
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We address a linear fractional differential equation and develop effective solution methods using algorithms for the inversion of triangular Toeplitz matrices and the recently proposed QTT format. The inverses of such matrices can be computed by the divide and conquer and modified Bini’s algorithms, for which we present the versions with the QTT approximation. We also present an efficient formula for the shift of vectors given in QTT format, which is used in the divide and conquer algorithm. As a result, we reduce the complexity of inversion from the fast Fourier level O(nlogn) to the speed of superfast Fourier transform, i.e., O(log2n). The results of the paper are illustrated by numerical examples.
ISSN:0377-0427
1879-1778
DOI:10.1016/j.cam.2013.10.025