Loading...
Superfast solution of linear convolutional Volterra equations using QTT approximation
Roberts, Jason A. Savostyanov, Dmitry V. Tyrtyshnikov, Eugene E.
Roberts, Jason A.
Savostyanov, Dmitry V.
Tyrtyshnikov, Eugene E.
Advisors
Editors
Other Contributors
EPub Date
Publication Date
2014-04
Submitted Date
Collections
Files
Other Titles
Abstract
This article 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(log^2n). The results of the paper are illustrated by numerical examples.
Citation
Journal of Computational and Applied Mathematics, 2014, 260, pp. 434-448
Publisher
Elsevier
Journal
Journal of Computational and Applied Mathematics
Research Unit
DOI
10.1016/j.cam.2013.10.025
PubMed ID
PubMed Central ID
Type
Article
Language
en
Description
NOTICE: this is the author’s version of a work that was accepted for publication in Journal of Computational and Applied Mathematics. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Journal of Applied and Computational Mathematics, 260, 2014, doi: 10.1016/j.cam.2013.10.025
Series/Report no.
ISSN
0377-0427
EISSN
1879-1778
ISBN
ISMN
Gov't Doc
Test Link
Sponsors
During this work D. V. Savostyanov and E. E. Tyrtyshnikov were supported by the Leverhulme Trust to visit, stay and work at the University of Chester, as the Visiting Research Fellow and the Visiting Professor, respectively. Their work was also supported in part by RFBR grants 11-01-00549, 12-01-91333-nnio-a, 13-01-12061, and Russian Federation Government Contracts 14.740.11.0345, 14.740.11.1067, 16.740.12.0727.