Divide-and-Conquer Solver in Tensor-Train Format for d-Dimensional Time-Space Fractional Diffusion Equations

A divide-and-conquer solver coupled with Tensor-Train (TT) format is proposed for solving the d-dimensional time-space fractional diffusion equations with alternating direction implicit finite difference scheme. In contrast to the complexity and storage of divide-and-conquer solver in full storage format, which grows at least exponentially with dimension d, complexity and storage of the proposed solver are ONMlogM+rr+(d-1)r2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}\left( NM\left( \log M+r\right) \left( r+(d-1)r^2\right) \right. $$\end{document}+Nlog2N·r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left. +N\log ^2 N\cdot r \right) $$\end{document} and OMr+(d-1)r2+Nr\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}\left( M\left( r+(d-1)r^2\right) +Nr \right) $$\end{document} with acceleration by an efficient approximated Toeplitz inversion, where M, N are numbers of spatial and temporal grid points and r is the TT-ranks of related TT format data. Hence they grow slowly with dimension d if the TT-ranks r is low. For reducing the increase of TT-ranks after certain TT operations, TT rounding is performed with introduced error, which is analyzed for giving a criterion for preserving convergence rate of the numerical scheme. The accuracy and efficiency of the proposed solver is illustrated by numerical experiments with dimension d up to 20 for case of low TT-ranks initial conditions and source terms.