Annotation of the results obtained in 2021
1. A two-mask iterative method is developed and justified for low-rank matrix completion problems with matrices which elements correspond to sparse perturbations. An original convergence theory for SVP-typed (Singular Value Projection) algorithms is proposed which results have a better agreement with numerical experiments. Two-mask algorithm was utilized for data compression of real sea-level observations in Brest region (France). In case of compress coefficient 15 the error of approximation in Chebyshev norm was less than 5%. 2. Fast iterative algorithms for completion of low rank matrices in the presence of additional information are developed and justified. Theoretical estimates are obtained for the number of elements required for successful reconstruction of low-rank matrices under assumption the additional information is available. It was proved for the first time that the number of required elements does not depend on the size of the problem, but only on the dimension of the additional information. Similar estimates were proposed for the algorithmic complexity of the proposed methods. The new algorithms were utilized for solving of the problem of distributed estimation of the data transmission channel in modern wireless communication systems. 3. An algorithm for tensorized data completion the Tucker format with low Tucker ranks is proposed and partially justified under assumption that additional information is available. The property of the bounded isometry is proved for a linear operator in the tensor completion problem in the Tucker format with low ranks in the presence of additional information. It is shown that the number of elements required to realize the property of bounded isometry does not depend on the size of the tensor, but only on the ranks of the approximation and the dimension of the additional information. 4. An algorithm for completion of tensors in the canonical polyadic format in the presence of additional information based on the theory of Bayesian estimation is proposed. The approach was applied to the tasks of image processing and compression, as well as to the task of objects’ classification represented in the terrain images. 5. A new algorithm is developed to compute actions of the phi matrix function on a vector and a software implementation of the algorithm is designed, called phiRT (available at https://team.kiam.ru/botchev/expm/). Numerical test results show superiority of our algorithm to best analogues, such as phiv and phip. The algorithm and the test results are presented in https://doi.org/10.1137/20M1375383. 6. A theoretical analysis and practical testing are carried out for our nonlinear iterative model reduction scheme. In our approach, each new iteration is obtained by a block Krylov subspace model order reduction, which provides a low-rank representation of the solution. Test results show efficiency of our approach in comparison with methods like Rosenbrock ROS2 scheme, known for its excellent performance for solving various nonlinear problems. 7. A new approach is developed for using multigrid within Krylov subspace model order reduction. The approach appears to be quite efficient for solving parabolic problems and exhibits a mesh-independent convergence. The research results are presented in \url{https://arxiv.org/abs/2107.07590} 8. Our Krylov subspace methods have been tested on parabolic problems with a strong anisotropy. Among the residual-based schemes Krylov subspace methods, the shift-and-invert methods combined with algebraic multigrid appear to be most efficient (\url{https://doi.org/10.1088/1742-6596/2028/1/012021}). 9. In 2021, we showed the possibilities of using reduced bases for solution of the parametric family of models of the irreversible aggregation process with a source and a sink terms. An important observation is following: problems of different dimensions have a common structure of their bases. It makes possible to use bases of a higher dimensionality for solving of a lower dimensional problems without additional efforts to finding their exact bases. 10. For the discrete version of Smoluchowski equations we have obtained estimates for the divergence between the solutions of different sizes. Despite the fact that the solutions of systems of different order are not close to each other, from our numerical experiments we see that the linear space corresponding to the solutions of larger system contains the solutions of the smaller ones which cannot be described by a standard error estimates. Thus, the question of the possibility of the reverse transition of bases -- from a smaller system to a larger one can be formulated. 11. The problem of the dynamics of vortex structures arising behind a streamlined body, for a particular case, is reduced to the Cauchy problem with a linear or quadratic nonlinear term. For the reduced model, a numerical method for solving the Cauchy problem is applied. The method is based on the integrator of the matrix exponential and the second-order extrapolation exponential Euler method. The study of the parameters of the reduced model is carried out for the example of the problem of flow around a gliding parachute.

 

Publications

---

Annotation of the results obtained in 2019
Approximated Singular Value projection method is developed for solution of matrix completion problem. When under bounded isometry condition on the conditions operator a theorem on the linear convergence of ASVP method is proven Adaptive procedures have been developed for recruiting ranks and choosing step lengths in gradient descent method which allow to avoid the irregular behavior of the ASVP method POD-DEIM algorithm for solving nonlinear models reduction problem is improved by means of a construction of an interpolation operator with significantly limited operator norm and an expanding the interpolation space that allow to avoid degradation of accuracy for Newton algorithm. Local optimization method based on Levenberg-Marquardt method is implemented for polynomial state space models (SSM) of nonlinear dynamic systems. Low-rank polyvariate polynomial SSM is proposed and local optimization method based on Levenberg-Marquardt method is implemented for the model. Low-rank univariate polynomial SSM and approximation method of the given nonlinear SSM by such model is studied. Connection between application scope of the approximation method and uniqueness of canonical polyadic decomposition is noted. Sufficient conditions for applicability of the approximation algorithm are obtained. Stability of the algorithm with respect to noise is studied. Local optimization method based on Levenberg-Marquardt method is implemented for low-rank univariate polynomial SSM. For applications where large systems of differentials equations have to be solved many times for various source functions, algorithms based on asymptotic splitting of the source functions are developed and tested. These algorithms allow to significantly accelerate Krylov subspace methods for this problem class. In some cases our approach yields an acceleration of a factor 10 and more, compared to modern standard time integration methods. Problem classes are distinguished for which low rank representations of the source functions can be generalized from one to many dimensions of the parameter space. An approach based on block Krylov subspace methods is proposed where low rank representations with respect to additional parameters preserve the representation form. For multidimensional parameter spaces, different block Krylov subspaces with a bounded block size can be built. A new restarting algorithm is developed for Krylov subspace matrix exponential model reduction methods. The approach, called residual-time (RT) restarting, is simple in implementation, yet often appears to be quite efficient. For matrices whose numerical range lies in the complex right halfplane, the RT restarted Krylov subspace methods are guaranteed to converge for any restart length. We plan to apply the RT restarting in the vortex dynamics problems and other problems where matrix structure and dimension prevent an efficient use of rational Krylov subspace methods. The RT restarting is implemented within the expmARPACK software package, version 2.0.1, \url{https://team.kiam.ru/botchev/expm/}. In 2019, the possibility of tensorized representation of solutions of the kinetic equations of Smoluchowski aggregation for several classes of kinetic coefficients was demonstrated. We proposed algorithms for calculating the Smoluchowski operator in the QTT format, and numerical solutions are obtained for systems of aggregation equations using up to a trillion kinetic equations. In addition, a practical algorithm based on the use of the POD (Proper Orthogonal Decomposition) method for constructing reduced basis of aggregation equations is proposed. The new method allows one to obtain low-parametric representations of the time-dependent solutions of the aggregation equations. We have developed a new method for model reduction in application to solving of dynamic systems for particular case of dynamics of vortex stuctures. The developed method is based on search of the solution over Krylov space. It leads to reduction of dimensionality of the considered problem and provokes decrease of computational cost for solving the Cauchy problem for a large time-intervals. The developed approach is applied by expmARPACK package for case study about reshuffle of vortex rings.

 

Publications

---

Annotation of the results obtained in 2020
1. The study of minimal linear spaces admitting the convergence the reduced Newton method without degradation of accuracy in the DEIM algorithm is provided. 2. A method is proposed for constructing of interpolation operators in the DEIM algorithm with a higher degree of reliability than previously known. 3. It is proved that the interpolation projectors constructed on the principle of maximum volume (generalized maximum volume), outperforms interpolation projectors based Gaussian elimination with pivoting. 4. An effective method for selecting of initial points in the reduced Newton method is proposed. 5. A tensor completion algorithm for tensors of small Tucker ranks is developed. Theorems on the linear convergence of the method in a particular cases are proved. 6. A sparse solver is proposed for tensorized models with an extremely large number of parameters. 7. A "greedy" algorithm for determining the size of the parameters of complex tensorized models is proposed. 8. For linear evolutionary large scale problems with constant source functions, new restarting algorithms are constructed for model reduction Krylov subspace methods (\url{https://arxiv.org/abs/1912.02643}, \url{https://arxiv.org/abs/2010.08494}). They compare well with other well known methods, such as EXPOKIT (\url{https://www.maths.uq.edu.au/expokit/}) and phip (\url{http://www1.maths.leeds.ac.uk/~jitse/software.html}). 9. Our model reduction Krylov subspace methods are tested on linear nonsteady advection-diffusion problems with various nonconstant source functions (\url{https://arxiv.org/abs/2010.04756}). The results show high efficiency of our approach based on the block Krylov subspaces. 10. Some first preliminary tests are carried out for solving nonlinear Burgers equations within our model reduction framework. The tests show the expected decrease in the number of inner linear iterations with the outer iteration number. 11. For a wide class of non-stationary problems, an algorithm for constructing a subspace (characterized by its basis) is proposed based on the POD method known in the literature. In the proposed algorithm, the basis is constructed by successively approximating the solution on small `` windows '' into which the entire considered time interval is divided. In this case, the desired time T is not initially included in the algorithm, but is discovered by the algorithm itself based on the observed approximation accuracy. The algorithm was tested using the example of aggregation equations with a source of monomers and a sink of particles. For a class of problems with Brownian kernels and cyclic solutions, the fundamental possibility of `` recognizing '' such cyclic solutions, constructing a low-dimensional basis for approximating the complete solution of the problem in time with the final possibility of accelerating the computation time several times without significant loss of accuracy of numerical solutions of the reduced model is demonstrated. 12. A reduced model for solving the problem of vortex structure dynamics arising behind the streamlined body is proposed. The reduced problem deals with solving the nonlinear Cauchy problem with parametrically defined non linearity. The parameters of the reduced model are studied for the case of flow around the gliding parachute.

 

Publications

---