Approximation of the matrix with positive elements by the single rank matrix

A. V. Panyukov ; Kh. Z. Chaloob ; Ya. A. Mezaal

Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematika, mehanika, fizika, Tome 10 (2018) no. 2, pp. 28-36

Résumé

Most of the modern mathematical methods for solving problems of science, technology, and economics require the solution of linear problems of large dimension. To reduce the computational complexity, a special structure of matrices corresponding to these problems is used. Block-low-rank matrices represent the approximation with good accuracy of dense matrices in a low-parametric format. Blocks of small rank are represented as a product of matrices of smaller sizes. This allows you to significantly save computer memory. Approximate factorization methods for block-low-rank matrices can be used for approximate solution and preconditioning of systems with dense matrices in aero-, hydro- and electrodynamics problems, as well as in applied statistics and logistics. To build low-parametric representations of matrices based on small-rank approximations of individual blocks, algebraic methods are widely used. In this paper we consider an effective method for approximating blocks of a matrix with positive elements by a single rank matrix, i.e. in the form of a product of a column per line. The solution of the problem is sought among the admissible representations that minimize the average modulus of the logarithms of the ratio of an approximate representation of an element to the exact value. The approximating problem is reduced to the problem of linear programming, for which the dual problem is the task of building a circulation of the minimum value in a complete bipartite graph with the throughputs of all arcs equal to one. To solve this problem, we propose an algorithm that has a computational complexity of at most of $O(|I|\cdot|J|\cdot\log(|I|\cdot|J|))$, where $I$ is the set of rows in the block, and $J$ is the set of columns to the block.

Détail

Mots-clés : matrix
Keywords: low-rank approximation, linear programming, algorithm, computational complexity.

Bibliographie

[1] E.E. Tyrtyshnikov, “Mosaic-skeleton approximations”, Calcolo, 33:1 (1996), 47–57 | DOI | MR | Zbl

[2] I.V. Oseledets, A.Yu. Mikhalev, “Representation of quasi separable matrices using excluded sums and equivalent charges”, Linear Algebra Appl., 436:3 (2012), 699–708 | DOI | MR | Zbl

[3] M. Bebendorf, “Why finite element discretizations can be factored by triangular hierarchical matrices”, SIAM J. Numer. Anal., 45:4 (2007), 1472–1494 | DOI | MR | Zbl

[4] S. Börm, “Approximation of solution operators of elliptic partial differential equations by-and-matrices”, Numerische Mathematik, 115:2 (2010), 165–193 | DOI | MR | Zbl

[5] M. Bebendorf, W. Hackbusch, “Existence of H-matrix approximants to the inverse FE-matrix of elliptic operators with L$_\infty$-coefficients”, Numer. Math., 95:1 (2003), 1–28 | DOI | MR | Zbl

[6] D.A. Sushnikova, I.V. Oseledets, “Preconditioners for hierarchical matrices based on their extended sparse form”, Russian Journal of Numerical Analysis and Mathematical Modelling, 31 (2016), 29–40 | DOI | MR | Zbl

[7] G.V. Ryzhakov, A.Y. Mikhalev, D.A. Sushnikova, I.V. Oseledets, “Numerical solution of diffraction problems using large matrix compression”, 9th European Conference on Antennas and Propagation (EuCAP), 2015, 1–3

[8] J.M. Ford, I.V. Oseledets, E.E. Tyrtyshnikov, “Matrix approximations and solvers using tensor products and non-standard wavelet transforms related to irregular grids”, Rus. J. Numer. Anal. and Math. Modelling, 19:2 (2004), 185–204 | DOI | MR | Zbl

[9] Oseledets I. V., Savost'yanov D. V., Stavtsev S. L., “The use of non-linear approximation method to quickly solve the problem of sound propagation in shallow water”, Methods and technologies for solving large problems, A collection of scientific papers, IVM RAN Publ., 2004, 171–192 (in Russ.)

[10] Bashurov V. V., Buruchenko S. K., “Lagrangian computation of high velocity deep penetration”, Matem. Mod., 4:9 (1992), 37–42 (in Russ.)

[11] Ushakov A. L., “Fast Solution of the Model Problem for Poisson's Equation”, Bulletin of the South Ural State University. Series of “Mathematics. Mechanics. Physics”, 9:4 (2017), 36–42 (in Russ.)

[12] Sushnikova D. A., “Application of block low-rank matrices in Gaussian processes for regression”, Vychisl. Metody Programm., 18 (2017), 214–220 (in Russ.)

[13] A.V. Panyukov, V.A. Teleghin, “Forming of Discrete Mechanical Assembly Production Program”, Journal of Computational and Engineering Mathematics, 2015, no. 2, 57–64 | DOI | Zbl

[14] A.V. Panyukov, A.K. Bogushov, “The Spectral Statistical Method for Determining the Location Parameters of a Dipole Source of Electromagnetic Radiation”, Radiophysics and Quantum Electronics, 59 (2016), 278–288 | DOI

[15] Panyukov A. V., Tyrsin A. N., “Interrelation of weighted and generalized variants of the method of least moduli”, Izvestiya Chelyabinskogo nauchnogo tsentra, 2007, no. 1(35), 6–11 (in Russ.)

[16] A.V. Panyukov, I.A. Tetin, Ya.A. Mezal, “Linkage between wlad and glad and its applications for autoregressive analysis”, Proceedings of the 4th International Conference “Information Technologies for Intelligent Decision Making Support (ITIDS'2016)”, 2016, 224–227

[17] Lakeyev A. V., Noskov S. I., “The Least Modulus Method for the Linear Regression: the Number of Zero Approximation”, Modern Technologies System Analysis Modeling, 2012, no. 2, 48–50 (in Russ.)

[18] Yemelichev V. A., Kovalev M. M., Kravtsov M. K., Lawden G., Polytopes, graphs and optimization, Cambridge University Press, NY, USA, 1986, 344 pp. | MR