Abstract
In this paper we propose an efficient algorithm to compute low-rank approximation to the solution of so-called “Laplace-like” linear systems. The idea is to transform the problem into the frequency domain, and then use cross approximation. In this case, we do not need to form explicit approximation to the inverse operator, and can approximate the solution directly, which leads to reduced complexity. We demonstrate that our method is fast and robust by using it as a solver inside Uzawa iterative method for solving the Stokes problem.
Funding source: Russian Foundation for Basic Research
Award Identifier / Grant number: 16-31-60095
Funding statement: This work was supported by the Russian Foundation for Basic Research, grant 16-31-60095.
References
[1] M. Bebendorf, Approximation of boundary element matrices, Numer. Math. 86 (2000), no. 4, 565–589. 10.1007/PL00005410Search in Google Scholar
[2] M. Benzi, G. H. Golub and J. Liesen, Numerical solution of saddle point problems, Acta Numer. 14 (2005), no. 1, 1–137. 10.1017/S0962492904000212Search in Google Scholar
[3] L. de Lathauwer, B. de Moor and J. Vandewalle, A multilinear singular value decomposition, SIAM J. Matrix Anal. Appl. 21 (2000), 1253–1278. 10.1137/S0895479896305696Search in Google Scholar
[4] S. V. Dolgov, TT-GMRES: Solution to a linear system in the structured tensor format, Russian J. Numer. Anal. Math. Modelling 28 (2013), no. 2, 149–172. 10.1515/rnam-2013-0009Search in Google Scholar
[5] S. V. Dolgov and D. V. Savostyanov, Alternating minimal energy methods for linear systems in higher dimensions, SIAM J. Sci. Comput. 36 (2014), no. 5, A2248–A2271. 10.1137/140953289Search in Google Scholar
[6] I. P. Gavrilyuk, W. Hackbusch and B. N. Khoromskij, Tensor-product approximation to the inverse and related operators in high-dimensional elliptic problems, Computing 74 (2005), no. 2, 131–157. 10.1007/s00607-004-0086-ySearch in Google Scholar
[7] S. A. Goreinov, I. V. Oseledets, D. V. Savostyanov, E. E. Tyrtyshnikov and N. L. Zamarashkin, How to find a good submatrix, Matrix Methods: Theory, Algorithms, Applications, World Scientific, Hackensack (2010), 247–256. 10.1142/9789812836021_0015Search in Google Scholar
[8] S. A. Goreinov and E. E. Tyrtyshnikov, The maximal-volume concept in approximation by low-rank matrices, Structured Matrices in Mathematics, Computer Science, and Engineering, Contemp. Math. 208, American Mathematical Society, Providence (2001), 47–51. 10.1090/conm/280/4620Search in Google Scholar
[9] L. Grasedyck, Existence and computation of low Kronecker-rank approximations for large systems in tensor product structure, Computing 72 (2004), 247–265. 10.1007/s00607-003-0037-zSearch in Google Scholar
[10] L. Grasedyck, Hierarchical singular value decomposition of tensors, SIAM J. Matrix Anal. Appl. 31 (2010), no. 4, 2029–2054. 10.1137/090764189Search in Google Scholar
[11]
W. Hackbusch and D. Braess,
Approximation of
[12] W. Hackbusch and S. Kühn, A new scheme for the tensor representation, J. Fourier Anal. Appl. 15 (2009), no. 5, 706–722. 10.1007/s00041-009-9094-9Search in Google Scholar
[13]
B. N. Khoromskij,
Structured rank-
[14]
B. N. Khoromskij,
[15] B. N. Khoromskij and V. Khoromskaia, Multigrid accelerated tensor approximation of function related multidimensional arrays, SIAM J. Sci. Comput. 31 (2009), no. 4, 3002–3026. 10.1137/080730408Search in Google Scholar
[16] B. N. Khoromskij and I. V. Oseledets, Quantics-TT collocation approximation of parameter-dependent and stochastic elliptic PDEs, Comput. Methods Appl. Math. 10 (2010), no. 4, 376–394. 10.2478/cmam-2010-0023Search in Google Scholar
[17] E. A. Muravleva, On the kernel of discrete gradient operator, Numer. Methods Prog. 9 (2008), 93–100. Search in Google Scholar
[18] E. A. Muravleva, Numerical methods based on variational inequalities for viscoplastic Bingham media, Ph.D. thesis, INM RAS, Moscow, 2010. Search in Google Scholar
[19]
I. V. Oseledets,
Approximation of
[20] I. V. Oseledets, DMRG approach to fast linear algebra in the TT–format, Comput. Methods Appl. Math. 11 (2011), no. 3, 382–393. 10.2478/cmam-2011-0021Search in Google Scholar
[21] I. V. Oseledets, Tensor-train decomposition, SIAM J. Sci. Comput. 33 (2011), no. 5, 2295–2317. 10.1137/090752286Search in Google Scholar
[22] I. V. Oseledets and S. V. Dolgov, Solution of linear systems and matrix inversion in the TT-format, SIAM J. Sci. Comput. 34 (2012), no. 5, A2718–A2739. 10.1137/110833142Search in Google Scholar
[23] I. V. Oseledets and E. A. Muravleva, Fast orthogonalization to the kernel of discrete gradient operator with application to the Stokes problem, Linear Algebra Appl. 432 (2010), no. 6, 1492–1500. 10.1016/j.laa.2009.11.010Search in Google Scholar
[24] I. V. Oseledets, D. V. Savostianov and E. E. Tyrtyshnikov, Tucker dimensionality reduction of three-dimensional arrays in linear time, SIAM J. Matrix Anal. Appl. 30 (2008), no. 3, 939–956. 10.1137/060655894Search in Google Scholar
[25] I. V. Oseledets, D. V. Savostyanov and E. E. Tyrtyshnikov, Linear algebra for tensor problems, Computing 85 (2009), no. 3, 169–188. 10.1007/s00607-009-0047-6Search in Google Scholar
[26] I. V. Oseledets and E. E. Tyrtyshnikov, TT-cross approximation for multidimensional arrays, Linear Algebra Appl. 432 (2010), no. 1, 70–88. 10.1016/j.laa.2009.07.024Search in Google Scholar
[27] E. E. Tyrtyshnikov, Incomplete cross approximation in the mosaic–skeleton method, Computing 64 (2000), no. 4, 367–380. 10.1007/s006070070031Search in Google Scholar
© 2018 Walter de Gruyter GmbH, Berlin/Boston