Superfast solution of linear convolutional Volterra equations using QTT approximation

Hdl Handle:
http://hdl.handle.net/10034/336402
Title:
Superfast solution of linear convolutional Volterra equations using QTT approximation
Authors:
Roberts, Jason A.; Savostyanov, Dmitry V.; Tyrtyshnikov, Eugene E.
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.
Affiliation:
University of Chester ; Russian Academy of Sciences / University of Chester ; Russian Academy of Sciences / Lomonosov Moscow State University
Citation:
Journal of Computational and Applied Mathematics, 2014, 260, pp. 434-448
Publisher:
Elsevier
Journal:
Journal of Computational and Applied Mathematics
Publication Date:
Apr-2014
URI:
http://hdl.handle.net/10034/336402
DOI:
10.1016/j.cam.2013.10.025
Additional Links:
http://www.journals.elsevier.com/journal-of-computational-and-applied-mathematics/
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
ISSN:
0377-0427
EISSN:
1879-1778
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.
Appears in Collections:
Mathematics

Full metadata record

DC FieldValue Language
dc.contributor.authorRoberts, Jason A.en
dc.contributor.authorSavostyanov, Dmitry V.en
dc.contributor.authorTyrtyshnikov, Eugene E.en
dc.date.accessioned2014-12-01T09:15:22Zen
dc.date.available2014-12-01T09:15:22Zen
dc.date.issued2014-04en
dc.identifier.citationJournal of Computational and Applied Mathematics, 2014, 260, pp. 434-448en
dc.identifier.issn0377-0427en
dc.identifier.doi10.1016/j.cam.2013.10.025en
dc.identifier.urihttp://hdl.handle.net/10034/336402en
dc.descriptionNOTICE: 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.025en
dc.description.abstractThis 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.en
dc.description.sponsorshipDuring 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.en
dc.language.isoenen
dc.publisherElsevieren
dc.relation.urlhttp://www.journals.elsevier.com/journal-of-computational-and-applied-mathematics/en
dc.rightsArchived with thanks to Journal of Computational and Applied Mathematicsen
dc.subjectfractional calculusen
dc.subjecttriangular Toeplitz matrixen
dc.subjectdivide and conqueren
dc.subjectTensor train formaten
dc.subjectfast convolutionen
dc.subjectsuperfast fourier transformen
dc.titleSuperfast solution of linear convolutional Volterra equations using QTT approximationen
dc.typeArticleen
dc.identifier.eissn1879-1778en
dc.contributor.departmentUniversity of Chester ; Russian Academy of Sciences / University of Chester ; Russian Academy of Sciences / Lomonosov Moscow State Universityen
dc.identifier.journalJournal of Computational and Applied Mathematicsen
This item is licensed under a Creative Commons License
Creative Commons
All Items in ChesterRep are protected by copyright, with all rights reserved, unless otherwise indicated.