Superfast solution of linear convolutional Volterra equations using QTT approximation

被引：5

作者：

Roberts, Jason A. ^{[1
]}

Savostyanov, Dmitry V. ^{[1
,2
]}

Tyrtyshnikov, Eugene E. ^{[2
,3
]}

机构：

[1] Univ Chester, Chester CH1 4BJ, Cheshire, England

[2] Russian Acad Sci, Inst Numer Math, Moscow 119333, Russia

[3] Moscow MV Lomonosov State Univ, Moscow 119991, Russia

来源：

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS | 2014年 / 260卷

关键词：

Fractional calculus; Triangular Toeplitz matrix; Divide and conquer; Tensor train format; Fast convolution; Superfast Fourier transform; FRACTIONAL CALCULUS; NEWTON ITERATION; FAST INVERSION; MATRICES; COLLOCATION; ALGORITHMS; STABILITY; VECTORS;

D O I：

10.1016/j.cam.2013.10.025

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 (n log n) to the speed of superfast Fourier transform, i.e., O (log(2) n). The results of the paper are illustrated by numerical examples. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：434 / 448

页数：15

共 43 条

[1]

[Anonymous], 2004, Lecture Notes in Mathematics

[2]

[Anonymous], 1999, FRACTIONAL DIFFERENT

[3]

Beerends R. J., 2003, Fourier and Laplace transforms

[4]

Ben-Israel A., 1966, SIAM Journal on Numerical Analysis, V3, P410, DOI DOI 10.1137/0703035