Superfast solution of linear convolutional Volterra equations using QTT approximation

Jason A. Roberts, Dmitry V. Savostyanov, Eugene E. Tyrtyshnikov

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish
Pages (from-to)434-448
Number of pages15
JournalJournal of Computational and Applied Mathematics
Volume260
DOIs
Publication statusPublished - 1 Apr 2014

Keywords

  • Divide and conquer
  • Fast convolution
  • Fractional calculus
  • Superfast Fourier transform
  • Tensor train format
  • Triangular Toeplitz matrix

Fingerprint Dive into the research topics of 'Superfast solution of linear convolutional Volterra equations using QTT approximation'. Together they form a unique fingerprint.

  • Cite this