Eugene E. Tyrtyshnikov

An efficient method is proposed for constructing a preconditioner for accelerated solution of systems of linear algebraic equations arising in solving linear inverse problems. The method relies on the properties of a low-rank approximation of the original system matrix and allows for a significant reduction in the number of iterations in iterative solution methods. Significant savings in computational resources can be achieved in the inverse problem of processing experimental data measured in a spatial domain separated from the domain of localization of the quantities to be reconstructed.

In this article, we introduce eigenvector centralities for higher-order multilayer networks and suggest to use nonnegative tensor train decomposition for fast computations of dominant eigenvectors of multi-homogeneous maps via power iterates. The analysis of the approximation error for using nonnegative tensor train instead of the original nonnegative tensor is presented.

In the article, interpolation-based and mosaic-skeleton approaches for solving the problem of the potential flow of a plate are compared. They compress a dense matrix of a linear system, arising in the collocation method on the non-uniform grid. The first method relies on Fast Fourier Transform and linear interpolation from an additional uniform grid. The second uses block low-rank approximation of a matrix. Both techniques demonstrate effectiveness in time and memory but distinguish different structures in a matrix, which affects the solution of a linear system. In our implementation, the mosaic-skeleton method solves the problem quicker than its competitor. Still, it consumes more memory, and its duration grows more significantly with an increase in the size of a system.

The question of finding the optimal location and number of sensors is important when solving applied inverse problems of remote sensing. An incorrect answer to this question can significantly affect (1) the accuracy of reconstructing the unknown parameters of the object under study, and/or (2) the computational complexity of the inverse problem being solved. The work proposes an economical algorithm that allows among all equivalent (in the sense of the computational complexity of obtaining a solution to the inverse problem) sensor configurations, to select the one that will give a more accurate result when processing experimental data. This algorithm also allows to make a conclusion about whether it is really necessary to process all the experimental data obtained in the experiment, or whether it is possible to limit ourselves to only part of them without a significant loss of accuracy in the reconstructed solution. The algorithm is based on (1) the application of the mosaic-skeleton approximation method to the matrix of the system of equations to which the inverse problem being solved is reduced, and (2) the calculation of the compression rate of the approximating matrix relative to the original dense matrix for a given permissible relative approximation error. Thus, the algorithm is a priori, that is, it does not require a preliminary search for a solution to the inverse problem for the sensor configuration under study. Moreover, if the formulas that define the elements of the system matrix are known, then the algorithm requires the calculation of not all of these elements, but only part of them.

The horizontally diagonalize and fit (HDF) method is proposed to solve the ill-posed Cauchy problem for the three-dimensional Poisson equation with data given on the part of the boundary (a continuation problem). The HDF method consists in discretization over horizontal variables and transformation of the system of differential equations to a diagonal form. This allows to uncouple the original three-dimensional continuation problem into a moderate number of one-dimensional problems in the vertical dimension. The problem size reduction can be carried taking into account the noise level, so that the number k of one-dimensional problems appears to be a regularization parameter. Our experiments show that HDF is applicable to large-scale problems and for n ≤ 2500 {n\leq 2500} is significantly more efficient than Landweber iteration.

The problem of approximation by low-rank matrices is found everywhere in computational mathematics. Traditionally, this problem is solved in the spectral or Frobenius norm, where the approximation efficiency is associated with the rate of decrease of the matrix singular values. However, recent results show that this requirement is not necessary in other norms. In this paper, a method for solving the problem of approximating by low-rank matrices in Chebyshev’s norm is proposed. It makes it possible to construct effective approximations of matrices for which singular values do not decrease in an acceptable amount time.

Tensor train model is a low-rank approximation for multidimensional data. In this article we demonstrate how it can be succesfully used for fast computation of nonnegative tensor train, nonnegative canonical and nonnegative Tucker factorizations. The proposed approaches can be incorporated in wide range of methods to solve big data problems.

Numerical integration is a classical problem emerging in many fields of science. Multivariate integration cannot be approached with classical methods due to the exponential growth of the number of quadrature nodes. We propose a method to overcome this problem. Tensor-train decomposition of a tensor approximating the integrand is constructed and used to evaluate a multivariate quadrature formula. We show how to deal with singularities in the integration domain and conduct theoretical analysis of the integration accuracy. The reference open-source implementation is provided.

Modern directions in the development of matrix methods and their applications described in the present issue are overviewed. Special attention is given to methods associated with separation of variables, special decompositions of matrices and tensors implementing this technique, related algorithms, and their applications to multidimensional problems in computational mathematics, data analysis, and machine learning.

Numerical methods for solving volume integral equations describing the problems of wave scattering by transparent obstacles are considered. The equations are approximated using the collocation method on a nonuniform grid, and the problem is reduced to solving a system of linear algebraic equations. An efficient method is proposed for the approximate multiplication of the matrix of this system by a vector, which is comparable in complexity to the method used in the case of a uniform grid. An auxiliary uniform grid is introduced, and methods of interpolation of functions and algorithms of the fast discrete Fourier transform are used. It is essential that the number of nodes of the auxiliary uniform grid is comparable to the number of nodes of the original nonuniform grid.