A fast direct method for block triangular Toeplitz-like with tri-diagonal block systems from time-fractional partial differential equations

Rihuan Ke, Kwok Po NG*, Hai Wei Sun

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

51 Citations (Scopus)

Abstract

In this paper, we study the block lower triangular Toeplitz-like with tri-diagonal blocks system which arises from the time-fractional partial differential equation. Existing fast numerical solver (e.g., fast approximate inversion method) cannot handle such linear system as the main diagonal blocks are different. The main contribution of this paper is to propose a fast direct method for solving this linear system, and to illustrate that the proposed method is much faster than the classical block forward substitution method for solving this linear system. Our idea is based on the divide-and-conquer strategy and together with the fast Fourier transforms for calculating Toeplitz matrix-vector multiplication. The complexity needs O(MNlog2M) arithmetic operations, where M is the number of blocks (the number of time steps) in the system and N is the size (number of spatial grid points) of each block. Numerical examples from the finite difference discretization of time-fractional partial differential equations are also given to demonstrate the efficiency of the proposed method.

Original languageEnglish
Pages (from-to)203-211
Number of pages9
JournalJournal of Computational Physics
Volume303
DOIs
Publication statusPublished - 2015

Scopus Subject Areas

  • Numerical Analysis
  • Modelling and Simulation
  • Physics and Astronomy (miscellaneous)
  • Physics and Astronomy(all)
  • Computer Science Applications
  • Computational Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Block triangular Toeplitz-like matrix
  • Direct methods
  • Divide-and-conquer strategy
  • Fast Fourier transform
  • Fractional partial differential equations

Fingerprint

Dive into the research topics of 'A fast direct method for block triangular Toeplitz-like with tri-diagonal block systems from time-fractional partial differential equations'. Together they form a unique fingerprint.

Cite this