Search
Close
Search
Advanced Search
Search Menu
AI Discovery Assistant

Abstract

Linear systems with a tensor product structure arise naturally when considering the discretization of Laplace-type differential equations or, more generally, multidimensional operators with separable coefficients. In this work, we focus on the numerical solution of linear systems of the form
$$ \begin{align*} & \left(I\otimes \dots\otimes I \otimes A_1+\dots + A_d\otimes I \otimes\dots \otimes I\right)x=b, \end{align*}$$
where the matrices |$A_{t}\in \mathbb R^{n\times n}$| are symmetric positive definite and belong to the class of hierarchically semiseparable matrices. We propose and analyze a nested divide-and-conquer scheme, based on the technology of low-rank updates, which attains the quasi-optimal computational cost |$\mathcal {O}(n^{d}\log (n))$|⁠. Our theoretical analysis highlights the role of inexactness in the nested calls of our algorithm and provides worst case estimates for the amplification of the residual norm. The performances are validated on 2D and 3D case studies.
tensor equation, Sylvester equation, divide and conquer, rational approximation
© The Author(s) 2023. Published by Oxford University Press on behalf of the Institute of Mathematics and its Applications. All rights reserved.
This article is published and distributed under the terms of the Oxford University Press, Standard Journals Publication Model (https://dbpia.nl.go.kr/journals/pages/open_access/funder_policies/chorus/standard_publication_model)
Issue Section:
Articles
You do not currently have access to this article.
Download all slides