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 tensorstructured equation is investigated by generalizing results for the matrix equations case. Finally we present first numerical results.
Original language  Undefined/Unknown 

Publication status  Published  Dec 1 2011 

Cite this

APA

Standard

Harvard

Vancouver

Author

BIBTEX

RIS
@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 tensorstructured 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 = dec,
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 tensorstructured 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 tensorstructured 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 