TY - JOUR

T1 - Superfast solution of linear convolutional Volterra equations using QTT approximation

AU - Roberts, Jason A.

AU - Savostyanov, Dmitry V.

AU - Tyrtyshnikov, Eugene E.

PY - 2014/4/1

Y1 - 2014/4/1

N2 - 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.

AB - 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.

KW - Divide and conquer

KW - Fast convolution

KW - Fractional calculus

KW - Superfast Fourier transform

KW - Tensor train format

KW - Triangular Toeplitz matrix

UR - http://www.scopus.com/inward/record.url?scp=84887254232&partnerID=8YFLogxK

U2 - 10.1016/j.cam.2013.10.025

DO - 10.1016/j.cam.2013.10.025

M3 - Article

AN - SCOPUS:84887254232

VL - 260

SP - 434

EP - 448

JO - Journal of Computational and Applied Mathematics

JF - Journal of Computational and Applied Mathematics

SN - 0377-0427

ER -