Abstract
The class of -matrices allows an approximate matrix arithmetic with almost linear complexity. In the present paper, we apply the -matrix technique combined with the Kronecker tensor-product approximation (cf. [2, 20]) to represent the inverse of a discrete elliptic operator in a hypercube (0, 1)d∈ℝd in the case of a high spatial dimension d. In this data-sparse format, we also represent the operator exponential, the fractional power of an elliptic operator as well as the solution operator of the matrix Lyapunov-Sylvester equation. The complexity of our approximations can be estimated by (dn log qn), where N=nd is the discrete problem size.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Babenko, K. I.: Foundations of the numerical analysis. Moscow: Nauka 1986 (in Russian).
Beylkin, G., Mohlenkamp, M. J.: Numerical operator calculus in higher dimensions. University of Colorado, APPM preprint No. 476, August 2001.
Braess, D.: Nonlinear approximation theory. Springer 1986.
Dautray, R., Lions, J.-L.: Mathematical analysis and numerical methods for science and technology, vol. 5: Evolution problems I. Springer 1992.
Fujita, H., Saito, N., Suzuki, T.: Operator theory and numerical methods. Elsevier 2001.
Gavrilyuk, I.P.: Strongly P-positive operators and explicit representation of the solutions of initial value problems for second order differential equations in Banach space. J. Math. Anal. Appl. 236, 327–349 (1999).
Gavrilyuk, I. P., Hackbusch, W., Khoromskij, B. N.: -matrix approximation for the operator exponential with applications. Numer. Math. 92, 83–111 (2002).
Gavrilyuk, I. P., Hackbusch, W.: Khoromskij, B. N.: Data-sparse approximation to operator-valued functions of elliptic operators. Math. Comp. 73(247), 1297–1324 (2004).
Gavrilyuk, I. P., Hackbusch, W., Khoromskij, B. N.: Data-sparse approximation to a class of operator-valued functions. Math. Comp. (forthcoming).
Grasedyck, L.: Existence and computation of a low Kronecker-rank approximation to the solution of a tensor system with tensor right-hand side. Computing 70, 295–334.
Grasedyck, L., Hackbusch, W.: Construction and arithmetics of -matrices. Computing 70, 295–334 (2003).
Grasedyck, L., Hackbusch, W., Khoromskij, B. N.: Solution of large scale algebraic matrix Riccati equations by use of hierarchical matrices. Computing 70, 121–165 (2003).
Griebel, M., Knapek, S.: Optimized tensor-product approximation spaces. Constr. Approx. 16, 303–332 (2000).
Hackbusch, W.: Elliptic differential equations: Theory and numerical treatment. Berlin: Springer 1992.
Hackbusch, W.: A sparse matrix arithmetic based on -matrices. Part I: Introduction to -matrices. Computing 62, 89–108 (1999).
Hackbusch, W., Khoromskij, B. N.: A sparse -matrix arithmetic. Part II: Application to multi-dimensional problems. Computing 64, 21–47 (2000).
Hackbusch, W., Khoromskij, B. N.: Towards -matrix approximation of the linear complexity. In: Operator Theory: Advances and applications, vol. 121, (Elschner, J., Gohberg, I., Silbermann, B., eds.), pp 194–220. Basel: Birkhäuser 2001.
Hackbusch, W., Khoromskij, B. N.: Kronecker tensor-product approximation to certain matrix-valued functions in higher dimensions. Preprint 16, Max-Planck-Institut für Mathematik in den Naturwissenschaften, Leipzig 2004.
Hackbusch, W., Khoromskij, B. N., Sauter, S.: On -matrices. In: Lectures on Applied Mathematics ( Bungartz, H.-J., Hoppe, R., Zenger, C., eds.), pp. 9–30. Berlin: Springer 2000.
Hackbusch, W., Khoromskij, B. N., Tyrtyshnikov: E.: Hierarchical Kronecker tensor-product approximation. Preprint 35, Max-Planck-Institut für Mathematik in den Naturwissenschaften, Leipzig 2003.
Khoromskij, B. N.: -matrix approximation of integral operators. Lecture Notes No. 17, Max-Planck-Institut für Mathematik in den Naturwissenschaften, Leipzig 2003.
Pazy, A.: Semigroups of linear operator and applications to partial differential equations. Springer 1983.
Sheen, D., Sloan, I. H., Thomée, V.: A parallel method for time-discretization of parabolic problems based on contour integral representation and quadrature. Math. Comp. 69, 177–195 (2000).
Stenger, F.: Numerical methods based on Sinc and analytic functions. Springer 1993.
Temlyakov, V. N.: Approximation of functions with bounded mixed derivative. Proc. Steklov Inst. (1989) Math. 178(1), 275–293 (1989).
Tyrtyshnikov, E. E.: Tensor approximations of matrices generated by asymptotically smooth functions. (Russian) Mat. Sb. 194(6), 147–160 (2003) (translation in Sb. Math. 194, 941–954 2003).
Yarvin, N., Rokhlin, V.: Generalized Gaussian quadratures and singular value decompositions of integral operators. SIAM J. Sci. Comput. 20, 699–718 (1998).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gavrilyuk, I., Hackbusch, W. & Khoromskij, B. Hierarchical Tensor-Product Approximation to the Inverse and Related Operators for High-Dimensional Elliptic Problems. Computing 74, 131–157 (2005). https://doi.org/10.1007/s00607-004-0086-y
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00607-004-0086-y