| Popis: |
А.В. Панюков, Х.З. Чалуб, Я.А. Мезал Южно-Уральский государственный университет, г. Челябинск, Российская Федерация E-mail: paniukovav@susu.ru. A.V. Panyukov, Kh.Z. Chaloob, Ya.A. Mezal South Ural State University, Chelyabinsk, Russian Federation E-mail: paniukovav@susu.ru Большинство современных математических методов решения задач естествознания, техники, экономики требуют решения линейных задач большой размерности. Для понижения вычислительной сложности используется специальная структура матриц, соответствующих этим задачам. Блочномалоранговые матрицы представляют из себя приближение с хорошей точностью плотных матриц в малопараметрическом формате. Блоки малого ранга представляются в виде произведения матриц меньшего размера. Это позволяет значительно экономить машинную память. Методы приближенной факторизации блочно-малоранговых матриц могут быть применены для приближенного решения и предобуславливания систем с плотными матрицами в задачах аэро-, гидро- и электродинамики, а также в прикладной статистике и логистике. Для построения малопараметрических представлений матриц, основанных на малоранговых аппроксимациях отдельных блоков, широко используются алгебраические методы. В данной работе рассмотрен эффективный способ аппроксимации блоков матрицы с положительными элементами матрицей единичного ранга, т. е. в виде произведения столбца на строку. Решение задачи ищется среди допустимых представлений, минимизирующих среднее значение модулей логарифмов отношения приближенного представления элемента к точному значению. Аппроксимирующая задача сведена к задаче линейного программирования, для которой двойственная задача является задачей построения циркуляции минимальной стоимости в полном двудольном графе с пропускными способностями всех дуг равными единице. Для решения полученной задачи предложен алгоритм, имеющий вычислительную сложность не более O(|I|·|J|·log(|I|·|J|)), где I – множество строк в блоке, J – множество столбцов в блоке. 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|·|J|·log(|I|·|J|)), where I is the set of rows in the block, and J is the set of columns to the block. |
