Extend ADI to tensor structured equations

T. Mach, J. Saak

Research output: Working paper

Abstract

We present a generalization of the alternating direction implicit (ADI) iteration to higher dimensional problems. We solve equations of the form $ I otimes ots otimes I otimes A_1 + I otimes ots otimes I otimes A_2 otimes I + dots + A_d otimes I otimes ots otimes I $vec$(X) = $vec$(B)$, with $B$ given in the tensor train format. The solution $X$ is computed in the tensor train format, too. The accuracy of $X$ depends exponentially on the local rank of $X$ and on the rank of $B$. To prove this we generalize a result for right hand sides of low Kronecker rank to low tensor train rank. Further we give a convergence proof for the generalized ADI iteration in the single shift case and show first ideas for more sophisticated shift strategies. The conditioning of tensor-structured equation is investigated by generalizing results for the matrix equations case. Finally we present first numerical results.
Original languageUndefined/Unknown
Publication statusPublished - Dec 1 2011

Cite this

Mach, T., & Saak, J. (2011). Extend ADI to tensor structured equations.

Extend ADI to tensor structured equations. / Mach, T.; Saak, J.

2011.

Research output: Working paper

Mach T, Saak J. Extend ADI to tensor structured equations. 2011 Dec 1.
Mach, T. ; Saak, J. / Extend ADI to tensor structured equations. 2011.
@techreport{6d166077d2274fa69802243b6466bc12,
title = "Extend ADI to tensor structured equations",
abstract = "We present a generalization of the alternating direction implicit (ADI) iteration to higher dimensional problems. We solve equations of the form $ I otimes ots otimes I otimes A_1 + I otimes ots otimes I otimes A_2 otimes I + dots + A_d otimes I otimes ots otimes I $vec$(X) = $vec$(B)$, with $B$ given in the tensor train format. The solution $X$ is computed in the tensor train format, too. The accuracy of $X$ depends exponentially on the local rank of $X$ and on the rank of $B$. To prove this we generalize a result for right hand sides of low Kronecker rank to low tensor train rank. Further we give a convergence proof for the generalized ADI iteration in the single shift case and show first ideas for more sophisticated shift strategies. The conditioning of tensor-structured equation is investigated by generalizing results for the matrix equations case. Finally we present first numerical results.",
author = "T. Mach and J. Saak",
year = "2011",
month = "12",
day = "1",
language = "Undefined/Unknown",
type = "WorkingPaper",

}

TY - UNPB

T1 - Extend ADI to tensor structured equations

AU - Mach, T.

AU - Saak, J.

PY - 2011/12/1

Y1 - 2011/12/1

N2 - We present a generalization of the alternating direction implicit (ADI) iteration to higher dimensional problems. We solve equations of the form $ I otimes ots otimes I otimes A_1 + I otimes ots otimes I otimes A_2 otimes I + dots + A_d otimes I otimes ots otimes I $vec$(X) = $vec$(B)$, with $B$ given in the tensor train format. The solution $X$ is computed in the tensor train format, too. The accuracy of $X$ depends exponentially on the local rank of $X$ and on the rank of $B$. To prove this we generalize a result for right hand sides of low Kronecker rank to low tensor train rank. Further we give a convergence proof for the generalized ADI iteration in the single shift case and show first ideas for more sophisticated shift strategies. The conditioning of tensor-structured equation is investigated by generalizing results for the matrix equations case. Finally we present first numerical results.

AB - We present a generalization of the alternating direction implicit (ADI) iteration to higher dimensional problems. We solve equations of the form $ I otimes ots otimes I otimes A_1 + I otimes ots otimes I otimes A_2 otimes I + dots + A_d otimes I otimes ots otimes I $vec$(X) = $vec$(B)$, with $B$ given in the tensor train format. The solution $X$ is computed in the tensor train format, too. The accuracy of $X$ depends exponentially on the local rank of $X$ and on the rank of $B$. To prove this we generalize a result for right hand sides of low Kronecker rank to low tensor train rank. Further we give a convergence proof for the generalized ADI iteration in the single shift case and show first ideas for more sophisticated shift strategies. The conditioning of tensor-structured equation is investigated by generalizing results for the matrix equations case. Finally we present first numerical results.

M3 - Working paper

BT - Extend ADI to tensor structured equations

ER -